D2 June 2016 Q2

Figure 1: capacitated directed network of pipes from S to T through A, B, C, D, E and F with capacities, initial flows and cuts C1 and C2 — Figure 1

Figure 1 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent an initial flow.

(a) List the saturated arcs. (2)

(b) State the value of the initial flow. (1)

(d) By inspection, find a flow-augmenting route to increase the flow by three units. You must state your route. (1)

(e) Prove that the new flow is maximal. (2)

Scheme	Marks
Saturated arcs: SB, SC, AE, DT, FT	M1 A1
	(2)

Scheme	Marks
59	B1
	(1)

Scheme	Marks
\(C_1 = 72\), \(C_2 = 86\)	B1 B1
	(2)

Scheme	Marks
SABCFET	B1
	(1)

Mark scheme (e)

Scheme	Marks
The cut through DT, AE and CF (or DT, AE, BC and SC) has a value 62	M1
Value of the flow is 62, so by max flow – min cut theorem, flow is maximal	A1
	(2)
	8 marks

Notes

e1M1: The arcs of the correct cut stated or a correct cut drawn on their diagram in the answer book – please check carefully for this

e1A1: Must have stated the (maximum) flow as 62 and a conclusion based on the max flow min cut theorem - they must use all four words, ‘max’, ‘flow’, ‘min’, ‘cut’ in their conclusion