D2 June 2013 Q3

EdexcelOld spec10 marksFlows in Networks

Figure 1: capacitated directed network from S to T through A to I, with capacities, initial flows in circles, and cut C1 — Figure 1

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

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

(b) State the capacity of cut C\(_1\). (1)

The labelling procedure has been used and the result drawn on Diagram 1 in the answer book.

(c) Use Diagram 1 to find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. (4)

(d) Draw a maximum flow pattern on Diagram 2 in your answer book. (2)

(e) Prove that the flow shown in (d) is maximal. (2)

Scheme	Marks
Initial flow = 44	B1
	(1)

Scheme	Marks
Value of cut = 12+7+4+10+2+5+31 = 71	B1
	(1)

Mark scheme (c)

Scheme	Marks
e.g. SACFHT – 3; SADGIT – 4; SBEDFHT – 2 e.g. SACFHT – 3; SADFHT – 2; SADGIT – 2; SBEDGIT - 2	M1 A1; A1; A1
	(4)

Notes

c1M1 One valid flow augmenting route found and a value stated.

c1A1 Flow increased by at least 2

c2A1 A second correct flow route (and value at least 2) correct

c3A1 CSO Flow increased by 9 and no more.

Guidance for 3(c)
SA +7 SB +2 AC +3 AD +4 BD none BE + 2
ED + 2 CH none CF +3 EG none EI none
(DF+2 DG+2 FH +5 FT none FI none GI +4 HT +5 IT +4)

Scheme	Marks
e.g.	M1 A1
	(2)

Mark scheme (e)

Scheme	Marks
Maximum flow=minimum cut e.g. cut through CH, CF, AD, BD, DE, EG and EI	DM1 A1
	(2)
	(10 marks)

Notes

e1DM1 Must have attempted (d) and made an attempt at a cut.

e1A1 cut correct – may be drawn. Refer to max flow-min cut theorem all four words (alternative cut: CH, CF, AD, BD, BE).