math 401 test 3

Question 1

the size of the vertex set |V| is called the ? of G

Answer 1

order

Question 2

G is a multigraph if

Answer 2

there are some repeated edges {xi, xj} (called a multiple edge) for i=/=j in E

Question 3

G is a general graph if

Answer 3

we further allow a multigraph to have {xi, xi} (called a loop) in E

Question 4

how to count the degree of a vertex with a loop

Answer 4

the loop counts twice for degree (but only once for edge)

Question 5

Σd(vi) from i to n =

Answer 5

2|E|

Question 6

Handshake problem: prove that the number of people that shake hands an odd number of times is even

Answer 6

Σd(vi) of the odd’s + Σd(vi) of the even’s must be = 2|E|. Since Σd(vi) of the evens will be even, the Σd(vi) of the odds must be even as well

Question 7

Two general graphs are called isomorphic provided that

Answer 7

|V| = |V’| and |E| = |E’|

Question 8

Let G be a (general) graph. G’ is a (general) subgraph of G if

Answer 8

V’⊆V and E’⊆E

Question 9

G’ is a spanning (general) subgraph of G if

Answer 9

V’ = V and E’ ⊆ E

Question 10

G’ is a (general) subgraph induced by V’ if

Answer 10

any edge of G with both end-vertices in V’ is also an edge of G’

Question 11

A walk is closed if

Answer 11

you return to the starting vertex

Question 12

A walk is open if

Answer 12

you do not return to the starting vertex

Question 13

A trail is

Answer 13

a walk with distinct edges

Question 14

A closed trail is

Answer 14

a closed walk with distinct edges

Question 15

A path is

Answer 15

a walk with distinct vertices

Question 16

A cycle is

Answer 16

a closed walk with distinct vertices

Question 17

A general graph is called connected provided that, for each pair of vertices x and y, there is

Answer 17

a walk joining x and y

Question 18

Let G and G’ be two general graphs. Then the following are necessary conditions for G and G’ to be isomorphic

Answer 18

1. if G is a graph, so is G’
2. G and G’ have the same number of components
3. if G has a cycle equal to some length k, so does G’
4. if G has an (induced) general subgraph that is a complete graph Km, so does G’

Question 19

The adjacency matrix is an n x n array such that

Answer 19

the entry aij in row i and column j equals teh number of edges joining xi and xj

Question 20

An open Eulerian trail is

Answer 20

an open trail which contains each edge of a graph G exactly once

Question 21

a closed Eulerian trail is

Answer 21

a closed trail which contains each edge of G exactly once

Question 22

Let G be a connected general graph. G has a closed Eulerian trail if and only if

Answer 22

the degree of each vertex of G is even

Question 23

Let G be a connected general graph. G has an open Eulerian trail if and only if

Answer 23

G has exactly two vertices of odd degree

Question 24

Let G be a connected graph and suppose that the number of vertices of G with odd degree is m>0. Then the edges of G can be partitioned into ? trails. It is impossible to partition the edges of G into fewer than ? open trails.

Answer 24

m/2

Question 25

A Hamiltonian chain is

Answer 25

a chain connecting all vertices of G

Question 26

A Hamiltonian cycle is a

Answer 26

cycle containing all vertices of G

Question 27

A connected graph with a ? does not have a Hamiltonian cycle

Answer 27

bridge

Question 28

Let G be a graph with order n>=3. a) If the sum of degrees of any two non-adjacent vertices is at least n, then G has a Hamiltonian ? b) If the sum of degrees of any two non-adjacent vertices is at least n-1, then G has a Hamiltonian ?

Answer 28

a) cycle | b) chain

Question 29

Let G = (V,E) be a multigraph. G is called bipartite provided the vertex set V can be

Answer 29

partitioned into two subsets X and Y such that each edge of G has one vertex in X and one vertex in Y (X and Y is called a bi-partition of G)

Question 30

A multigraph is bipartite if and only if

Answer 30

each of its cycles has even length

Question 31

Let G be a bipartite graph with bi-partition X, Y. If |X| =/= |Y|, then G (has a/has no) Hamiltonian cycle. If |X| = |Y|, then G (has a/has no) Hamiltonian chain connecting two vertices in X or Y. If |X| = |Y|+1, then G (has a/has no) Hamiltonian chain connecting one vertex in X and a vertex in Y

Answer 31

has no for all

Question 32

a tree is

Answer 32

a connected graph that becomes disconnected upon the removal of any edge (each edge of a tree is a bridge)

Question 33

A connected graph of order n is a tree if and only if

Answer 33

it has exactly n-1 edges and no cycle

Question 34

Let G be a connected graph and a be an edge of G. Then a is a bridge if and only if

Answer 34

no cycle in G contains a

Question 35

A graph G is a tree if and only if every pair of distinct vertices x and y are joined by

Answer 35

a unique chain

Question 36

A spanning tree is

Answer 36

a tree containing all vertices of G

Question 37

Every connected graph has a

Answer 37

spanning tree

Question 38

Let T be a spanning tree of a connected graph G. Let a be an edge of G which is not an edge of T. Then there is an edge b of T such that

Answer 38

the graph T' obtained from T by inserting a and deleting b is also a spanning tree of G

Question 39

Let G = (V, E) be a graph. A proper coloring of G is

Answer 39

an assignment of a color to each vertex of G in such a way that adjacent vertices are assigned different colors

Question 40

If a color is chosen from a set of k-colors, then the vertex-coloring is called

Answer 40

a k-coloring, whether or not all k colors are used

Question 41

If G has a k-coloring, it is said to be

Answer 41

k-colorable

Question 42

The smallest k, such that G is k-colorable, is called

Answer 42

the chromatic number of G X(G)

Question 43

Let G be a graph of order n>=1. Then X(G) <= ?

Answer 43

n

Question 44

X(G) = n if and only if

Answer 44

G = Kn

Question 45

X(G) = 1 if and only if

Answer 45

G is a null graph Nn (a graph with no edges)

Question 46

Let G be a graph and let H be a subgraph of G. Then X(G) ? X(H).

Answer 46

>=

Question 47

If G has a subgraph equal to a complete graph Kp of order p, then X(G) ? p

Answer 47

>=

Question 48

Let G be a graph of order n and let q be the largest order of an induced subgraph equal to Nq. Then X(G) >=

Answer 48

ceil (n/q)

Question 49

A graph is called planar provided that

Answer 49

it can be represented by a drawing in the plane such that two edges-curves intersect only at vertex-points

Question 50

Let G' be a plan representation of G. Then any two edges can only intersect at ?

Answer 50

the vertices

Question 51

Let G' be a planar graph with n vertices, e edges, and r regions. Let the number of edges bordering the regions be, respectively, f1, f2, ..., fr. Then Σfi from i to r =

Answer 51

= 2e = Σd(v) for each vertex in V

Question 52

Euler's formula: Let G be a connected planar graph with n vertices, e edges, and r regions. Then

Answer 52

r - e + n = 2

Question 53

Let G be a connected planar graph. Then G has a vertex v such that deg(v) <= ?

Answer 53

5

Question 54

Let G be a planar graph. Then |E| <= ?

Answer 54

3n-6

Question 55

Let G be a bipartite planar graph. Then |E| <= ?

Answer 55

2n-4

Question 56

Algorithm for a closed Eulerian trail starting with a1 = {x0, x1} ∈ E

Answer 56

1. put i=1 2. put W = {x0, x1} 3. put F = {a1} 4. while xi =/= x0 do (i) locate an edge a,i+1 = {xi, x,i+1} not in F (ii) put x,i+1 in W (x,i+1 may already be in W) (iii) put a,i+1 in F (iv) i++ and go back to 1

Question 57

algorithm for spanning tree: let G be a connected graph of order n

Answer 57

(i) set F = E (ii) while there is an edge F such that a is not a bridge of G = (V, F), set F = F - {a} the terminal graph T = (V, F) is a spanning tree of G

Question 58

BF-algorithm to grow a BSF-tree rooted at u (let u be any vertex)

Answer 58

1. put i=1, U={u}, D(u) = 0, bf(u) = 1, F = Ø, and T = (U, F) 2. if there is no edge in U that joins a vertex x in U to a vertex y in V-U, then stop. Otherwise, determine if there is an edge a = {x,y} with x in U and y in V-U such that x has the smallest breadth-first number bf(x) and do (i) put bf(y) = i+1 (ii) put D(y) = D(x)+1 (iii) Set U = U ∪ {y} and F = F ∪ {a} (iv) put T = (U, F) (v) i++ and go back to 2

Question 59

DF-algorithm to grow a DFS-tree rooted at u (let u be any vertex)

Answer 59

1. put i=1, U = {u}, df(u) = 1, F = Ø, and T = (U, F) 2. if there is no edge in G that joins a vertex x in U to a vertex y in V-U then stop. Otherwise, determine an edge a = {x, y} with x in U and y in V-U such that x has the largest depth-first number df(x) and do (i) put df(y) = i+1 (ii) set U = U ∪ {y} and F = F ∪ {a} (iii) Put T = (U, F) (iv) i++ and go back to 2

Question 60

Algorithm for a distance-tree for u (Dijkstra's algorithm): Let G = (V, E) be a graph of order n and let u be any vertex

Answer 60

1. put i=1, U = {u}, D(u)=0, F=Ø, and T=(U,F) 2. if there is no edge in G that joins a vertex x in U to a vertex y in V-U then stop. Otherwise, determine an edge a = {x, y} with x in U and y in V-U such that D(x) + c{x,y} is as small as possible and do (i) set U = U ∪ {y} and F = F ∪ {a} (ii) Put D(y) = D(x) + c{x,y} and go back to 2

Question 61

Greedy algorithm for a minimum weight spanning tree (Kruskal's algorithm): Let G=(V,E) be a weighted connected graph of order n with weight function c

Answer 61

1. put F = Ø 2. while there exists an edge a not in F such that F ∪ {a} does not contain the edges of a cycle of G, determine such an edge a with minimum weight and set F = F ∪ {a} 3. put T = (U,F)

Question 62

Prim's algorithm for a minimum weight spanning tree: Let G=(V,E) be a graph of order n with weight function c and let u be any vertex

Answer 62

1. put i=1, U1 = {u}, F1 = Ø, and T1 = (U1, F1) 2. for i = 2, 3, ..., n-1, do the following (i) locate an edge ai = {x, y}of smallest weight such that x is in Ui and y is in V-Ui (ii) Put U,i+1 = Ui ∪ {y}, F,i+1 = Fi ∪ {ai}, and T,i+1 = (U,i+1 , F,i+1) (iii) increase i to i+1 3. output T,n-1 = (U,n-1 , F,n-1) where U,n-1 = V