Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MTH6105: Algorithmic Graph Theory
Duration: 2 hours
Apart from this page, you are not permitted to read the contents of this
question paper until instructed to do so by an invigilator.
You should attempt ALL questions. Marks available are shown next to the
questions.
Only non-programmable calculators that have been approved from the
college list of non-programmable calculators are permitted in this
examination. Please state on your answer book the name and type of
machine used.
Complete all rough work in the answer book and cross through any work that is not to
be assessed.
Possession of unauthorised material at any time when under examination conditions is
an assessment offence and can lead to expulsion from QMUL. Check now to ensure you
do not have any unauthorised notes, mobile phones, smartwatches or unauthorised
electronic devices on your person. If you do, raise your hand and give them to an
invigilator immediately.
It is also an offence to have any writing of any kind on your person, including on your
body. If you are found to have hidden unauthorised material elsewhere, including
toilets and cloakrooms, it will be treated as being found in your possession.
Unauthorised material found on your mobile phone or other electronic device will be
considered the same as being in possession of paper notes. A mobile phone that causes
a disruption in the exam is also an assessment offence.
Exam papers must not be removed from the examination room.
Examiners: F. Fischer, J. Ward
c© Queen Mary University of London (2020) Turn Over
Page 2 MTH6105 (2020)
Question 1 [27 marks].
(a) Explain what it means for a graph G to be a tree. [2]
(b) State the tree induction lemma. [3]
(c) Using the tree induction lemma or otherwise, prove that |E(T )| = |V (T )| − 1 for
every tree T . [5]
(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) = {v1, v2, v3, v4, v5, v6, v7},
E(G) = {v1v2, v1v3, v2v3, v2v4, v2v5, v3v5, v3v6, v4v5, v5v6} and
w(v1v2) = 1, w(v1v3) = 4, w(v2v3) = 4
w(v2v4) = 2, w(v2v5) = 3, w(v3v5) = 4
w(v3v6) = 1, w(v4v5) = 1, w(v5v6) = 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]
c© Queen Mary University of London (2020)
MTH6105 (2020) Page 3
Question 2 [23 marks].
(a) Define the concept of an s−t-path in a graph G. [3]
(b) Explain what it means for a path to be a shortest s−t-path in a network (G,w). [2]
Recall that Dijkstra’s algorithm, when applied to a network (G,w) starting from
s ∈ V (G), constructs a spanning tree T of the connected component of G containing s.
Consider the network (G,w) given by the following drawing, where each edge e ∈ E(G)
is labeled by its weight w(e).
v1
v4
v6 v7
v5
v3v26 1
1
1
7
7
1
1
2
4
4
(c) Apply Dijkstra’s algorithm to the network starting from vertex v1. Give V (T ) and
E(T ) after each iteration of the algorithm. [10]
(d) Give a shortest v1−v7-path in (G,w). What is the length of this path? [4]
(e) Give an asymptotic upper bound on the running time of Dijkstra’s algorithm
when it is applied to an arbitrary network (G,w). Justify your answer and state
whether the algorithm is an efficient algorithm. [4]
c© Queen Mary University of London (2020) Turn Over
Page 4 MTH6105 (2020)
Question 3 [27 marks]. Assume that seven roundabouts r1 to r7 are connected by
ten one-way streets as shown in the following illustration.
r1 r7
r2 r5
r4
r3 r6
The following table lists for each street the maximum number of cars that can travel
along the street per second.
street r1r2 r1r3 r2r4 r2r5 r3r4 r3r6 r4r5 r4r6 r5r7 r6r7
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 r1r2 r1r3 r2r4 r2r5 r3r4 r3r6 r4r5 r4r6 r5r7 r6r7
current number
of cars per second
4 5 3 1 3 2 3 3 4 5
(b) Let f : A(D)→ R 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 f is a r1−r7-flow for the network (D, c) and give its size. [5]
(c) Draw the residual network for network (D, c) and flow f . [6]
(d) Using the residual network or otherwise, find a maximum r1−r7-flow for (D, c).
Explain your reasoning. [4]
(e) Argue that the flow you have found is indeed a maximum r1−r7-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 r2 to r4 is temporarily reduced from 3 to 1. What does this mean for
the maximum amount of traffic that can flow from r1 to r7? Explain your
reasoning. [3]
(g) Assume instead that road improvement works could increase the capacity of the
street from r2 to r4. Would this increase the maximum amount of traffic that can
flow from r1 to r7? Explain your reasoning. [3]
c© Queen Mary University of London (2020)
MTH6105 (2020) Page 5
Question 4 [23 marks].
(a) Explain what it means for a graph G to be bipartite. [2]
(b) Prove that every tree is a bipartite graph. You may use any result from the
lecture notes without proof. [3]
(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. [4]
(i) 1 2 3
4 5 6
(ii)
4
7 8
5
2
31
6 9
(d) Define the concept of a matching M of a graph G. [2]
(e) State Hall’s theorem concerning the existence of matching that saturates one side
of a bipartite graph. [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 X X X
Bob X X X
Cynthia X X
Dmitiri X X
Erica X X
Faiz 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. [8]