D2 June 2019 Q6

EdexcelOld spec14 marksFlows in Networks

Figure 1: capacitated directed network with sources S1, S2, S3 and sinks T1, T2 through A to F, 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)

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

(3)

(c) Complete the initialisation of the labelling procedure on Diagram 2 in the answer book by entering values along the new arcs from S to T, and along arcs S₁B and AT₁ (2)

(d) 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)

(e) Draw a maximal flow pattern on Diagram 3 in the answer book. (2)

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

Scheme	Marks
Initial flow = 86	B1
	(1)

Supersource arcs SS1 43 (37), SS2 39 (31), SS3 28 (18); supersink arcs T1T 51 (41), T2T 54 (45) — Mark scheme (b)

Scheme	Marks
	M1 A1 A1
	(3)

Scheme	Marks
	M1 A1
	(2)

Mark scheme (d)

Scheme

Marks

E.g.	or
SS₁AT₁T – 3	SS₁AT₁T – 3
SS₁BDT₁T – 3	SS₁BDT₁T – 3
SS₂CET₂T – 2	SS₂BET₂T – 1
SS₃CFT₂T – 4	SS₂CET₂T – 1
	SS₃CFT₂T – 4

M1A1
A1
A1

(4)

Notes

(The printed mark scheme runs these two alternative lists of routes together on the page; they are set out here as two columns. Each list increases the flow by 12.)

d1M1: One valid flow augmenting route found and a value stated

d1A1: A second correct flow route

d2A1: Three correct flow routes with correct value stated

d3A1: CSO flow increased by 12 and no more

Maximal flow pattern of 98 with a cut through S1A, BD, DE, ET2, EF, CF and S3F — Mark scheme (e)

Scheme	Marks
	M1 A1
	(2)

Mark scheme (f)

Scheme	Marks
The cut through S₁A, BD, DE, ET₂, EF, CF and S₃F has value of 98	DB1
Value of the flow is 98 so by max flow – min cut theorem flow is maximal	DB1
	(2)
	14 marks

Notes

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

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