D2 June 2013 (R) Q6

EdexcelOld spec13 marksFlows in Networks

Figure 1: capacitated directed network on A, B, C, D, E, F, G, H and I 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) On Diagram 1 and Diagram 2 in the answer book, add a supersource S and a supersink T. On Diagram 1, show the minimum capacities of the arcs you have added. (2)

(c) Complete the initialisation of the labelling procedure on Diagram 2 in the answer book by entering values on the arcs to S and T and on arcs CD, DE, DG, FG, FI and GI. (3)

(d) Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. (3)

(e) Show your maximum flow on Diagram 3 in the answer book. (2)

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

Scheme	Marks
Initial flow = 93	B1
	(1)

Mark scheme (b)

Scheme	Marks
Adds supersource S plus arcs SA(49) and SB(57)	M1
Adds supersink T plus arcs HT(20) and IT(85)	A1
	(2)

Notes

b1M1: All relevant arcs added OR all arcs and numbers from supersource OR from supersink correct.

b1A1: CAO all arcs and numbers correct.

Scheme	Marks
	M1 A1 A1
	(3)

Mark scheme (d)

Scheme	Marks
E.g. SACDGIT – 2 and SACDGFIT – 3	M1 A1
Maximum flow = 98	A1
	(3)

Notes

d1M1: One valid flow augmenting route (from S to T) found and a value stated.

d1A1: Flow increased by 5 and no more.

d2A1: CAO 98 (allow if seen in (f) but must be clearly labelled as the maximum flow)

Examples of flow augmenting routes:

SACDGFIT (3), SACDGIT (2)
SBEDGFIT (3), SBEDGIT (2)
SBEDGFIT (3), SACDGIT (2)
SACDGFIT (3), SBEDGIT (2)

Maximum flow pattern with the minimum cut drawn through CH, CF, DF, FG and GI — Mark scheme (e)

Scheme	Marks
E.g.	M1 A1
	(2)

Mark scheme (f)

Scheme	Marks
Max flow = min cut, cut through CH, CF, DF, FG, GI	M1 A1
	(2)
	13 marks

Notes

f1M1: Must have attempted (e) and made an attempt at a cut.

f1A1: cut correct – may be drawn. Must have shown a correct flow of 98 in (e). Refer to max flow-min cut theorem all four words.