D2 June 2014 (R) Q5

EdexcelOld spec13 marksFlows in Networks

Figure 1: capacitated directed network with sources S1, S2 and sinks T1, T2 through A, B, C, D and E with capacities and initial flows — 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) (3)

(i) Add a supersource, S, and a supersink, T, and corresponding arcs to Diagrams 1 and 2, in the answer book.

(ii) Enter the flow value and appropriate capacity on each of the arcs you have added to Diagram 1.

(b) Complete the initialisation of the labelling procedure on Diagram 2 by entering values along the new arcs from S and T, and along AB, AD and DT\(_2\). (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 3 in the answer book. (2)

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

Scheme	Marks
	M1 A1 A1
	(3)

Scheme	Marks
	M1 A1
	(2)

Mark scheme (c)

Scheme	Marks
E.g. SS\(_2\)BET\(_2\)T – 13 SS\(_2\)BADT\(_2\)T – 3 SS\(_2\)BADET\(_2\)T – 5	M1 A1 A1 A1
	(4)

Notes

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

c1A1: Flow increased by at least 3.

c2A1: A second correct flow route of value at least 5 and value correct.

c3A1: CSO Flow increased by 21 and no more.

E.g. maximal flow pattern of 102 with the cut drawn — Mark scheme (d)

Scheme	Marks
	M1 A1
	(2)

Mark scheme (e)

Scheme	Marks
The cut through AT\(_1\), DT\(_1\), DT\(_2\), DE, BE, CB and S\(_2\)C has value 102	DB1
Value of the flow is 102 so by max flow – min cut theorem flow is maximal	DB1
	(2)
	13 marks

Notes

e1DB1: Must have attempted (d) - at least one number on all but one arc, and made an attempt at a cut, either drawn or stated.

e2DB1: CSO - (d) fully correct (showing a correct flow of 102) and a correct cut. Must refer to max flow-min cut theorem – all four words.