Final Module Assessment

Mark Scheme: In sections A and B, each whole question (meaning question 1 not ques- tion 1(a)) is worth 2 marks. In section C, each question is worth 4 marks.

 

Part A

1. Let G be the graph with vertex set V = {a, b, c, d} and edge set E = {ab, ac, bc}.

 

(a) Draw a picture of G.

(b) Write down the degree of each vertex of G.

(c) Write down the adjacency matrix A of G.

(d) Calculate the matrix A2 .

(e) What do the diagonal entries of A2 correspond to?

 

2. If possible, define graphs with the following properties. If not, explain why.

 

(a) A graph with 5 vertices: 3 vertices of degree 2 and the other 2 of degree 1. (b) A graph with 5 vertices: 4 vertices of degree 4 and the other 1 of degree 3.

(c) A graph with 6 vertices: 4 vertices of degree 2 and the other 2 of degree 1.

 

3. Recall that a tree is a connected graph with no cycles. List all non-isomorphic trees with exactly 6 vertices.

4. Given a graph G and a vertex v1 of G, recall that we can find all the vertices con- nected to v1 with the following connectedness algorithm:

(a) let X1 = {v1 };

(b) for i  > 1, let Xi be the set of the vertices that are neighbours of the ver- tices in Xi -1 , but have not appeared yet in any of X1, . . . , Xi -1 ;

(c) stop as soon as Xi  = a; the list of vertices connected to v1 is X1 u . . . u Xi .

Use this procedure to write the list of all the vertices connected to v1 in the

graph with adjacency matrix shown below.

Determine the connected components of the graph.

 

╱0   0   0   0   1   1   0   0   0   0   0   0、

． 0   0   1   1   0   0   0   0   0   0   0   0 ．

． 0   1   0   1   0   0   0   0   0   0   0   0 ．

．                                                           ．

． 0   1   1   0   0   0   0   0   0   1   0   1 ．

． 1   0   0   0   0   1   1   1   0   0   0   0 ．

．                                                           ．

．  1   0   0   0    1   0   0   0   0   0   0   0  ．

．                                                                     ．

．                                                           ．

．                                                           ．

． 0   0   0   0    1   0   0   0    1   0   0   0  ．

．                                                                     ．

．                                                           ．

．                                                           ．

． 0   0   0    1   0   0   0   0   0   0    1   0  ．

．                                                                     ．

．                                                           ．

．0   0   0   1   0   0   0   0   0   0   1   0．

5. A graph G  =  (V, E) is a bipartite graph if we can write V  =  V1  u V2 with   V1 and V2 non-empty, with no vertices in common, and no edge has endpoints both in V1 or both in V2 .

Recall that a cycle oflength k is a path v0v1 . . . vk -1vk with v0  = vk and with no other vertex repeating.

Let G be a bipartite graph as above. Prove that:

 

(a) EveV1 deg(v) = EveV2 deg(v) = |E|, and

(b) there are no cycles of G of odd length.

 

Hint: use induction for the first, and proofby contradiction for the second.

 

 

Part B

 

The questions in this part concern the weighted graph G shown on the next page.

 

6. Use Kruskal’s algorithm to find a minimal connector and state its weight.

7. Use Dijsktra’s algorithm to find path of minimal weight (and state its weight):

 

(a) From a to h.

(b) From c to g.

 

 

 

 

The graph G:

 

 

e

h

 

 

Weights for G:

 

 

 

 

 

 

Part C

 

Weight

14 13 16 11 6 17 2 18