D2 June 2012 Q6

EdexcelOld spec11 marksFlows in Networks

Figure 1: capacitated directed network from S to T through A to F, with capacities and initial flows in circles — 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) Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along SB, BD, CF and FT. (2)

(c) Hence use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. (4)

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

(e) Prove that your flow is maximal. (2)

Scheme	Marks
Initial flow = 46	B1
	(1)

Scheme	Marks
	M1 A1
	(2)

Mark scheme (c)

Scheme	Marks
E.g. SBDET – flow 3 SBCFT – flow 2	1M1 1A1 2M1 2A1
	(4)

Notes

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

c1A1 Flow increased by at least 2

c2M1 A second correct flow route and value correct.

c2A1 CSO Flow increased by 5 and no more.

Scheme	Marks
	M1 A1
	(2)

Mark scheme (e)

Scheme	Marks
(The value of the flow is 51). The cut through DT, DE, BE, BF, CB and SC has value 51 By max flow-min cut theorem flow is maximal	M1 A1cso
	(2)
	(11 marks)

Notes

e1M1 Must have attempted (d) - at least one number on all but one arc, and made an attempt at a cut, condone one missing arc if listed. (Accept sum of arcs as evidence of cut here only.)

e1A1CSO For (d) and (e) Cut and (d) correct, Cut may be drawn. Must refer to max flow-min cut theorem three words out of four.