The figure above shows a capacitated, directed network. The capacity of each arc is shown on each arc. The numbers in circles represent an initial flow from \(S\) to \(T\).
Two cuts \(C_1\) and \(C_2\) are shown on the figure.
(a) Write down the capacity of each of the two cuts and the value of the initial flow. (3)
(b) Complete the initialisation of the labelling procedure on the diagram below by entering values along arcs \(AC\), \(CD\), \(DE\) and \(DT\). (2)
(c) Hence use the labelling procedure to find a maximal flow through the network. You must list each flow-augmenting path you use, together with its flow. (5)
(d) Show your maximal flow pattern on a diagram. (2)
(e) Prove that your flow is maximal. (2)
Mark scheme (a)
Scheme
Marks
\(C_1 = 103,\quad C_2 = 177,\quad\) flow = 76
B1, B1, B1
(3)
Mark scheme (b)
Scheme
Marks
M1 A1
(2)
Mark scheme (c)
Scheme
Marks
e.g. \(S\,B\,C\,D\,T - 6\) \(S\,B\,C\,D\,E\,T - 1\) \(S\,B\,A\,C\,D\,E\,T - 15\)
