COMPUTER SCIENCE TRIPOS Part IA – 2015 – Paper 1
Algorithms (TMS)
(a) State the Max-Flow Min-Cut Theorem. [2 marks]
(b) For an arbitrary integer k ≥ 1, give an example of a flow network with at most
five vertices on which the basic Ford-Fulkerson method takes at least k steps to
terminate. [4 marks]
(c) Consider the following flow network G:
Given an initial flow f with f(s, u) = f(u, w) = f(w, t) = 2, perform one
iteration of Ford-Fulkerson; that is, draw the residual graph Gf , specify an
augmenting path in Gf , and update the flow f. Is this new flow a maximum
flow? Justify your answer. [5 marks]
(d) Given an undirected, connected graph G = (V, E), the edge-connectivity of G
is the size of a smallest set of edges X ⊆ E so that the graph G0 = (V, E \ X)
becomes disconnected.
(i) Describe an algorithm that computes the edge-connectivity of G, and
analyse its runtime and correctness. [7 marks]
(ii) Extend your algorithm so that it also returns a set X satisfying the
conditions above. [2 marks]