Question 1  [27 marks].

(d) Explain what it means for a tree T to be a spanning tree of a graph G, and what       it means for a tree T to be a minimum spanning tree of a network (G. w).          [3]

Now consider the network (G. w) such that V (G) = {u1 . u2 . u3 . u4 . u5 . u6 . u7 }, E(G) = {u1u2 . u1u3 . u2u3 . u2u4 . u2u5 . u3u5 . u3u6 . u4u5 . u5u6 } and

w(u1u2 ) = 1.

w(u2u4 ) = 2.

w(u3u6 ) = 1.

w(u1u3 ) = 4.

w(u2u5 ) = 3.

w(u4u5 ) = 1.

w(u2u3 ) = 4

w(u3u5 ) = 4

w(u5u6 ) = 3-

(e) Use Kruskal’s algorithm to determine a minimum spanning tree of this network.

Explain clearly what the algorithm is doing and draw the minimum spanning tree. [10]

(f)  Show that the spanning tree found in the previous part of the question is the

unique minimum spanning tree of the network (G. w). You may use any result

from the lecture notes without proof.                                                                           [4]

Question 2  [23 marks].

(a) Define the concept of an t −o-path in a graph G.                                                        [3] (b) Explain what it means for a path to be a shortest t −o-path in a network (G. w).   [2]

Recall that Dijkstra’s algorithm, when applied to a network (G. w) starting from

t ∈ V (G), constructs a spanning tree T of the connected component of G containing t. Consider the network (G. w) given by the following drawing, where each edge e ∈ E(G) is labeled by its weight w(e).

4

u1               6          u2           1             u3

7

1

1

4

4

7

(c) Apply Dijkstra’s algorithm to the network starting from vertex u1 . Give V (T) and

E(T) after each iteration of the algorithm.

[10]

Question 3  [27 marks].

Assume that seven roundabouts s1  to s7  are connected by

ten one-way streets as shown in the following illustration.

2

5

1 

3

The following table lists for each street the maximum number of cars that can travel along the street per second.

street                         s1s2     s1s3     s2s4     s2s5     s3s4     s3s6     s4s5     s4s6     s5s7     s6s7

maximum number of cars per second

6       5       3       2       4       3       3       3       4       7

(a) Let (D. c) be the directed network in which each arc e ∈ A(D) represents a street

and the capacity c(e) is equal to the maximum number of cars that can travel

along the street. Draw this network.                                                                            [2]

Assume now that the average number of cars per second currently traveling along each street is being measured as follows.

street                         s1s2     s1s3     s2s4     s2s5     s3s4     s3s6     s4s5     s4s6     s5s7     s6s7

current number    of cars per second

4       5       3       1       3       2       3       3       4       5

(b) Let r : A(D) → 政 be the function that maps each arc of the network to the

number of cars that currently travel along the street represented by the arc. Show

that r is a s1 −s7-flow for the network (D. c) and give its size.

(c) Draw the residual network for network (D. c) and flow r .

(d) Using the residual network or otherwise, find a maximum s1 −s7-flow for (D. c). Explain your reasoning.

[5] [6]

[4]

(e) Argue that the flow you have found is indeed a maximum s1 −s7-flow. In doing so,

you may use any result from the lecture notes without proof.                                     [4]

(f) Assume that due to an accident, the number of cars that can travel along the

street from s2  to s4  is temporarily reduced from 3 to 1. What does this mean for the maximum amount of traffic that can flow from s1  to s7 ? Explain your

reasoning.                                                                                                                      [3]

(g) Assume instead that road improvement works could increase the capacity of the

street from s2  to s4 . Would this increase the maximum amount of traffic that can        flow from s1  to s7 ? Explain your reasoning.                                                                 [3]

Question 4  [23 marks].

(a) Explain what it means for a graph G to be bipartite.

(b) Prove that every tree is a bipartite graph. You may use any result from the

lecture notes without proof.

(c) For each of the following graphs, state whether the graph is bipartite or not.         Justify your answer. In your justification, you may use any result from the lecture notes without proof.

2

5

(ii)

3

4

6

8

[2]

(e)  State Hall’s theorem concerning the existence of matching that saturates one side

[4]

(f) You are scheduling a set of job interviews, each lasting one hour. There are six     candidates – Alice, Bob, Cynthia, Dmitiri, Erica, and Faiz – and six time slots      starting at 1pm, 2pm, 3pm, 4pm, 5pm, and 6pm. Not all candidates are available in every time slot, and the time slots where each candidate is available are marked with X in the following table.

1pm   2pm   3pm   4pm   5pm   6pm

Alice     Bob      Cynthia Dmitiri

Erica Faiz

X

X

X

X

X

X

X

X

X

X

X

X

X

X       X

Your objective is to assign each candidate an interview time such that              (i) candidates are only interviewed at times when they are available and (ii) no two candidates are interviewed at the same time. Find such an assignment, or explain why no such assignment exists.