D2 June 2015 Q4

Figure 1: capacitated network from S to T through A, B, C, D, E, F and G with two cuts C1 and C2 — Figure 1

Figure 1 shows a capacitated network. The capacity of each arc is shown on the arc. Two cuts C\(_1\) and C\(_2\) are shown.

(a) Find the capacity of each of the two cuts. (2)

Given that one of these two cuts is a minimum cut,

(b) write down the maximum possible flow through the network. (1)

Given that the network now has a maximal flow from S to T,

(d) Explain why arcs GF and GT cannot both be saturated. (1)

Given that arcs EC, AD and DF are saturated and that there is no flow along arc GF,

(e) determine a maximum flow pattern for this network and draw it on Diagram 1 in the answer book. You do not need to use the labelling procedure to determine the maximum flow. (2)

Scheme	Marks
\(C_1 = 45,\ C_2 = 73\)	B1 B1
	(2)

Scheme	Marks
45	B1ft
	(1)

Scheme	Marks
20	B1
	(1)

Mark scheme (d)

Scheme	Marks
The maximum capacity of the arcs flowing into G is 21 and so both GF and GT cannot be full to capacity as the capacity of the arcs flowing out of G is 26	B1
	(1)

Notes

d1B1: CAO – argument must be numerical in nature (as a minimum accept 26 > 21 (oe))

Maximum flow pattern of 45 — Mark scheme (e)