AS June 2019 Q3

EdexcelCurrent spec10 marksFlows in Networks

Figure 1: network from S to T with excess capacity and potential backflow on the arrows either side of each arc: SA 7, 24; SB 4, 21; AC 14, 18; AD 4, 6; BD 0, 4; BE 5, 17; CH 0, 11; CF 2, 7; DF 2, 3; DE 6, 2; DG 6, 5; FH 5, 3; FT 0, 5; FJ 0, 2; EG 0, 7; EJ 0, 12; GJ 6, 12; HT 19, 14; JT 7, 26 — Figure 1

Alexa is monitoring a system of pipes through which fluid can flow from the source, S, to the sink, T. Currently, fluid is flowing through the system from S to T.

Alexa initialises the labelling procedure for this system, and the excess capacities and potential backflows are shown on the arrows either side of each arc, as shown in Figure 1.

(a) State the value of the initial flow. (1)

(b) Explain why arcs DF and DG can never both be full to capacity. (1)

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

(e) Use your answers to part (d) to find a maximum flow pattern for this system of pipes and draw it on Diagram 1 in the answer book. (1)

Diagram 1: the directed network of Figure 1 with no values on the arcs — Diagram 1

(f) Prove that the answer to part (e) is optimal. (3)

Scheme	Marks	AO
45	B1	1.1b
	(1)

Mark scheme (b)

Scheme	Marks	AO
e.g. the total capacity of arcs DF and DG is 5 + 11 = 16. The capacity of the two arcs leading into D are 10 (from AD) and 4 (from BD) giving a total capacity into D of 14. As 14 < 16 arcs DF and DG cannot both be full to capacity	B1	2.4
	(1)

Notes

B1: CAO (as a minimum accept mention that the max flow into D is 14 and max flow out of D is 16 together with comparison of these two values – (node) D must be mentioned)

Scheme	Marks	AO
Value of cut = 32 + 10 + 4 + 7 + 12 = 65	B1	1.1b
	(1)

Mark scheme (d)

Scheme	Marks	AO
e.g. SACFHT – 2; SADGJT – 4; SBEDFHT – 2 e.g. SACFHT – 2; SADGJT – 2; SADFHT – 2; SBEDGJT – 2 e.g. SACFHT – 2; SADGJT –4; SBEDGJT – 2	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: One correct flow augmenting route found from S to T + flow value or two correct routes

A1: Two correct routes + correct flow values

A1: CSO – increasing the flow by 8 only

maximum flow pattern: SA 30, SB 23, AC 20, AD 10, BD 4, BE 19, CH 11, CF 9, DF 5, DE 0, DG 9, FH 7, FT 5, FJ 2, EG 7, EJ 12, GJ 16, HT 18, JT 30 — Mark scheme (e)

Scheme	Marks	AO
e.g. Alternative: DG 11, GJ 18, JT 32 DF 3, FH 5, HT 16	B1	1.1b
	(1)

Mark scheme (f)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identification of cut through CH, CF, AD, BD, DE, EG and EJ Value of flow = 53 Therefore by the max-flow min-cut theorem it follows that flow is maximal	M1 A1 A1	2.1 3.1a 2.2a
	(3)
	(10 marks)

Notes

M1: Construct the start of an argument based on the max-flow min-cut theorem (that is an attempt to find a genuine cut together with the value of either their cut or flow (but not re-iterating the cut given in (c) – AC, AD, BD, DE, EG, EJ))

A1: Use appropriate process of finding a minimum cut – must see correct cut + value correct (accept ‘53’ and the cut either stated or drawn on either diagram)

A1: Correct deduction that the flow is maximal by stating ‘maximum flow (equal to) minimum cut’ – dependent on previous A mark and the correct flow in (e)