D2 June 2014 Q5

EdexcelOld spec11 marksFlows in Networks

Figure 1: capacitated directed network from S to T through A, B, C, D, E and F 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) 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 SC, AB, CE, DE and DT. (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 the answer book. (2)

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

Scheme	Marks
Initial flow = 62	B1
	(1)

Initialisation of the labelling procedure on SC, AB, CE, DE and DT — Mark scheme (b)

Scheme	Marks
	M1 A1
	(2)

Mark scheme (c)

Scheme

Marks

E.g.

SCEDT – 3	SCBADT 2	SCEADT 2	SBADT 2
SCEADT – 3	SBCEDT 3	SCEDT 3	SBCEDT 1
SBADT – 2	SCEADT 3	SBCEADT 1	SCEDT 2
		SBADT 2	SCEADT 3

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 correct.

c3A1: CSO Flow increased by 8 and no more.

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

Scheme	Marks
	M1 A1
	(2)

Mark scheme (e)

Scheme	Marks
The cut through SA, AB, AE, DE, ET and FT has value 70	DB1
Value of the flow is 70 so by max flow – min cut theorem flow is maximal	DB1
	(2)
	11 marks

Notes

e1DB1: Must have attempted (d) - at least one number on all but one arc, and either drawn or stated a cut. Cut may be drawn on any diagram.

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