Quiz 1 Prep

Question 1

the elements of a set can be any sort of (possibly abstract) object, e.g.

Answer 1

vectors, words, shapes, sets themselves

Question 2

subsets: formally a set R is included in a set S (or R is a subset of S), denoted R ⊆ S, if and only if

Answer 2

every element of R is an element of S (for all x, if x ∈ R then x ∈ S)

Question 3

equality of sets: two sets S_1, S_2 are said to be equal, denoted S_1 = S_2, if and only if

Answer 3

S_1 ⊆ S_2 and S_2 ⊆ S_1 (S_1 and S_2 have exactly the same elements)

Question 4

if R is not a subset of S (denoted R ⊄ S), then

Answer 4

there is at least one element of R that is NOT an element of S

Question 5

the empty set: the empty set, denoted ∅ (or {})m is the unique set that does not contain any elements. as a result, the empty set is technically

Answer 5

a subset of every set

Question 6

power sets: given a set S, the power set of S, denoted P(S) is the collection of all subsets of S, i.e.

Answer 6

P(S) = {all subsets of S} (including the empty set)

Question 7

cardinality: for a finite set S, the cardinality of S, denoted |S| (or #S), is the number of the (unique) elements in S, e.g.

Answer 7

|0| = 0, |{0}| = 1

Question 8

Suppose S is a set for which |S|= n. Using plain language, briefly explain why |P(S)| should be a power of 2.

Answer 8

Suppose we want to construct a subset of S. For each element of S, we have 2 choices: include or exclude. Therefore, we can construct 2^n subsets.

Question 9

union: given sets A and B, the union of A with B, denoted A U B, is the set of all elements that belong to either A or B (or both), i.e.

Answer 9

x ∈ A U B if and only if x ∈ A or x ∈ B (or both)

Question 10

intersection: given sets A and B, the intersection of A with B, denoted A ∩ B, is the set of all elements that belong to both A and B, i.e.

Answer 10

x ∈ A ∩ B iff x ∈ A and x ∈ B

Question 11

set difference: given two sets A and B, the difference of B within A (or A minus B) denoted A \ B (or A - B), is the set of all elements in A that are not in B, i.e.

Answer 11

x ∈ A \ B iff x ∈ A and x ∉ B

Question 12

complements: given a set A, the complement of A, denoted A^c (or A bar or -A), is the set of all elements in the local universe set U that are not in A, i.e.

Answer 12

x ∈ A^c iff x ∈ U \ A

Question 13

disjoint sets: two sets A and B are said to be disjoint if

Answer 13

A ∩ B = 0

Question 14

partitions: given a set X, a (finite) partition of X is a collection of mutually disjoint non-empty sets S_1, S_2, … , S_n whose union is X, i.e.

Answer 14

S_i ∩ S_j = 0 for all i ≠ j and S_1 U S_2 U … U S_n = X

Question 15

set builder notation: if S is a set, we can define a subset R ⊆ S by

Answer 15

R = {x ∈ U | x ∈ A or x ∈ B}

Question 16

cartesian product: in calculus, you saw that R^2 = { (x, y) | x, y ∈ R }. R^2 is an example of a Cartesian product of two sets. In general, given sets A and B, the Cartesian product is the set

Answer 16

A x B = { (a, b) | a ∈ A and b ∈ B}

Question 17

graphs: a graph G consists of a set of vertices (or nodes) V and a set of edges (or links) E, and we write G = (V, E). Here, an edge is an unordered pair of vertices (v_1v_2) and, intuitively, models

Answer 17

a “link” or “connection” between v_1 and v_2

Question 18

simple graph

Answer 18

no multi-edges or loops

Question 19

multigraph

Answer 19

multi-edges

Question 20

pseudograph

Answer 20

loop

Question 21

Without doing any calculations, explain why the sum of the degrees of all vertices must be an even number.

Answer 21

sum of the degrees = 2|E| (even). In adding the degrees of all the vertices, we count every edge exactly twice (each edge has 2 endpoints), so the sum of all degrees = 2 x (# edges) (even)

Question 22

directed graphs: a directed graph, or digraph, is a graph G = (V, A), where A is its arc set. Here, an arc is an ordered pair of vertices. For example, the arc (ab) represents

Answer 22

the directed edge from a to b (here (ab) ≠ (ba))

Question 23

in-degree and out-degree: for a digraph, the in-degree of a vertex v, deg_in(v) or deg^-(v), is

the out-degree of a vertex v, deg_out(v) or deg^+(v), is

Answer 23

deg_in(v) = (# arcs that end in v)
deg_out(v) = (# arcs that start at v)

Question 24

order: the order of a graph G = (V, E) is the

Answer 24

number of vertices in G, i.e. |V|

Question 25

degree: the degree of a vertex v, denoted deg(v), is the

Answer 25

number of edges in G that have v as an endpoint, i.e. the number of edges incident to v. loops count twice

Question 26

injections: a function f: A → B is an injection (1-1) if

Answer 26

f(x_1) ≠ f(x_2) whenever x_1 ≠ x_2

Question 27

surjections: a function f: A → B is a surjection (onto) if

Answer 27

for every y ∈ B, there is x ∈ A with f(x) = y

Question 28

bijections: a function f: A → B is a bijection if

Answer 28

it is both an injection and a surjection

Question 29

isomorphic graphs: two graphs, G_1 = (V_1, E_1) and G_2 = (V_2, E_2), are isomorphic if there is a bijection f: V_1 → V_2 such that

Answer 29

(a, b) ∈ E_1 if and only if (f(a)f(b)) ∈ E_2 (roughly, f provides a pairing of the vertices between G_1 and G_2 that preserves the structure of the graph)

Question 30

isomorphic graph properties: suppose G_1 and G_2 are isomorphic graphs. then, any of the following properties that one graph has, the other must also have; that is, if G_1 _________ then so too must G_2 (where n, m, and k are non-negative integers)

Answer 30

• is connected
• has n vertices
• has m edges
• has m vertices of degree k
• has a cycle of length k
• has an Eulerian circuit
• has a Hamiltonian circuit

Question 31

adjacency matrix: given a graph G with n vertices, the adjacency matrix A for the graph is the matrix for which a_ij =

Answer 31

edges from v_i to v_j (direction only matters for digraphs)

Question 32

for an undirected graph, a_ij =

Answer 32

a_ji

Question 33

walk: a walk in a graph G is

Answer 33

a sequence of vertices so that there is an edge between consecutive vertices (possibly repeating vertices and/or edges)

Question 34

trail: a trail in a graph G is

Answer 34

a walk with no repeated edge

Question 35

path: a path in a graph G is

Answer 35

a trail with no repeated vertex (trail implies no repeated edge too)

Question 36

length: the length of a walk (or path) is

Answer 36

the number of edges (counting repetitions) in the walk or path

Question 37

distance: the distance between vertices a and b in a graph G is

Answer 37

the length of the shortest path (no repeated edges/vertices) between a and b (if there is no path between them, then the distance between them is ∞)

Question 38

connected graphs and connected components: a graph G is said to be connected if

Answer 38

there is a path (no repeated vertex/edge) between any pair of distinct vertices

Question 39

a connected component (or component) of G = (V, E) is a connected subgraph of G that is not part of any larger connected subgraph. the components of G

Answer 39

partition the vertex set

Question 40

circuits and cycles: a circuit in a graph G is a closed trail (no repeated edges), i.e.

Answer 40

a trail (no repeated edges) that starts and ends at the same vertex

Question 41

a cycle is a

Answer 41

closed path (no repeated vertices or edges), i.e. a path that starts and ends at the same vertex

Question 42

eulerian circuits and trails: an eulerian circuit (or trail - no repeated edges) is a circuit (or trail) that contains

Answer 42

every edge and every vertex of G (contains each edge exactly once and can repeat vertices)

Question 43

eulerian graph

Answer 43

a graph that has an eulerian circuit is said to be

Question 44

semi-eulerian

Answer 44

a graph that does not contain an eulerian circuit but contains an eulerian trail

Question 45

a graph G is eulerian if and only if
1. _____
2. _____

Answer 45

1. G is connected
2. all vertices are of even degree

Question 46

a graph G is semi-eulerian if and only if
1. ____
2. ____

Answer 46

1. G is connected
2. exactly 2 vertices have odd degree

Question 47

eulerization: given a connected graph G = (V, E), an eulerization of G is a graph G’ = (V,E’) so that:
1. ____
2. ____

Answer 47

1. G’ is obtained by duplicating edges in G
2. every vertex of G’ is of even degree

NOTE: we often want to find an eulerization that minimizes the number (or cost/weight) of additional edges added

Question 48

hamiltonian cycles and paths

Answer 48

a cycle (or path) - no repeated vertices in a graph G that contains EVERY vertex of G is called a Hamiltonian cycle (Hamiltonian path)
contains every vertex exactly once

Question 49

hamiltonian graph

Answer 49

any graph that contains a Hamiltonian cycle

Question 50

properties of hamiltonian graphs: if G is Hamiltonian, then
1. ____
2. ____
3. ____
4. ____
5. ____

Answer 50

1. G must be connected
2. no vertex of G can have degree less than 2
3. G cannot contain a cut-vertex, i.e. cannot have a vertex whose removal disconnects the graph
4. if G contains a vertex v of degree 2, then both edges incident to v must be included in the Hamiltonian cycle
5. if two edges incident to a vertex v must be included in the cycle, then no other edge incident to it can be used in the cycle (otherwise v would be repeated)

Question 51

k-colouring

Answer 51

a proper k-colouring of a graph G is an assignment of colours to vertices of G such that no adjacent vertices have the same colour and exactly k colours are used

Question 52

chromatic number: the chromatic number x(G) of a graph is the

Answer 52

smallest value of k for which G has a proper k-colouring

Question 53

clique

Answer 53

when a complete graph appears as a subgraph within a larger graph

Question 54

basic strategies for vertex colouring:
1. begin with vertices of ____
2. identify locations where colours are forced rather than chosen, e.g. subgraphs consisting of ____
3. when the previous two have been exhausted, ____

Answer 54

1. high degree
2. odd cycles, wheel graphs, cliques
3. colour remaining vertices while trying to avoid using new colours