AS June 2023 Q2

EdexcelCurrent spec9 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, 18; SB 0, 15; SC 5, 39; AD 0, 18; AB 4, 0; BD 2, 32; EB 1, 17; CE 6, 21; CF 0, 18; ED 0, 9; DG 0, 31; DH 7, 28; EG 0, 8; GH 4, 36; GJ 2, 3; FE 2, 13; FJ 5, 5; HT 8, 64; JT 0, 8 — Figure 1

An engineer monitors a system of pipes through which a fluid flows from the source, S, to the sink, T.

The engineer 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) Obtain the capacity of the cut that passes through the arcs SA, SB, CE, FE and FJ. (1)

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

(d) Use your answer to (c) to draw a maximum flow pattern on Diagram 1 in the answer book. (1)

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

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

Scheme	Marks	AO
72	B1	1.1b
	(1)

Scheme	Marks	AO
Value of cut = 25 + 15 + 27 + 15 + 10 = 92	B1	1.1b
	(1)

Mark scheme (c)

Scheme	Marks	AO
e.g. SCEFJGHT – 3; SABDHT – 2 SCEFJGHT – 3; SCEBDHT – 1; SABDHT – 1 SABEFJGHT – 3; SABDHT – 2	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: One correct flow augmenting route found from S to T (so any routes that contain SB, BA, AD, CF, ED, EG, DG or JT are incorrect routes) - a ‘correct’ route is one in which the flow through the system can be increased

A1: Two correct routes (ignoring numerical value of the flow for this mark)

A1: cso – increasing the flow by 5 (and no more) – so at least two routes with corresponding correct values stated

maximum flow pattern: SA 20, SB 15, SC 42, AD 18, AB 2, BD 34, EB 17, ED 9, CE 24, CF 18, DG 31, DH 30, EG 8, GH 39, GJ 0, FE 10, FJ 8, HT 69, JT 8 — Mark scheme (d)

Scheme	Marks	AO
e.g. (based on the first example in (c))	B1	1.1b
	(1)

Mark scheme (e)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identification of cut through AD, BD, ED, EG, GJ and JT Value of flow = 77 Therefore it follows that flow is optimal	M1 A1 A1	2.1 3.1a 2.2a
	(3)
	(9 marks)

Notes

M1: Construct an argument based on max-flow min-cut theorem (e.g. attempt to find a cut (but not the one through SA, SB, CE, FE, FJ) through saturated arcs – must contain source on one side and sink on the other) – allow cut shown on the Diagram 1 in the answer book – this mark is dependent on an attempt at part (d) (so values on all but two arcs)

A1: Use appropriate process of finding a minimum cut – cut (AD, BD, ED, EG, GJ, JT) and the value of the flow through the network stated correctly (77)

A1: Correct deduction that the flow is maximal – must use all four words ‘maximum’, ‘flow’, ‘minimum’ and ‘cut’ (allow abbreviations for maximum and minimum) – dep on first A mark and the B mark in (d)