A2 June 2022 Q4

EdexcelCurrent spec9 marksFlows in Networks

Figure 1: capacitated directed network with capacities and initial flows (in circles): SA 33 (29), SB 41 (41), SC 30 (25), AE 20 (20), AB 14 (9), CB 12 (10), BE 22 (22), BG 30 (30), BF 14 (14), DB 6 (6), CD 17 (15), DF 8 (5), DT 4 (4), EG 53 (42), FT 24 (19), GT 75 (72); cuts C1 and C2 shown as dashed lines — Figure 1

Figure 1 shows a capacitated, directed network of pipes. The uncircled number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent an initial flow.

(a) List the saturated arcs. (1)

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

(d) State the capacity of cut \(C_1\) and the capacity of cut \(C_2\) (2)

(e) By inspection find one flow-augmenting route to increase the flow by three units.
You must state your route. (1)

(f) Prove that, once the flow-augmenting route found in part (e) has been applied, the flow is maximal. (3)

Scheme	Marks	AO
AE, BE, BF, BG, DB, DT, SB	B1	1.1b
	(1)

Scheme	Marks	AO
95	B1	1.1b
	(1)

Mark scheme (c)

Scheme	Marks	AO
The maximum feasible flow into F is 22 (from BF and DF) but the maximum feasible flow out of F is 24 so therefore FT cannot be full to capacity	B1	2.4
	(1)

Notes

B1: Correct reasoning – argument must be numerical in nature (e.g. as a minimum comparison of 22 with 24)

Scheme	Marks	AO
\(C_1\,(= 33 + 41 + 30) = 104\) \(C_2\,(= 53 + 30 + 14 + 0 + 17) = 114\)	B1 B1	1.1b 1.1b
	(2)

Scheme	Marks	AO
SABDFT	B1	1.1b
	(1)

Mark scheme (f)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identification of cut through AE, BE, BG, BF, DF and DT, Value of cut = 98, Value of flow = 98 Therefore it follows that flow is maximal	M1 A1 A1	2.1 3.1a 2.2a
	(3)
	(9 marks)

Notes

M1: Construct argument based on max-flow min-cut theorem (e.g. attempt to find a cut through saturated arcs – must contain source on one side and sink on the other). Allow a cut drawn on the diagram (need not be the correct one)

A1: Use appropriate process of finding a minimum cut – AE, BE, BG, BF, DF and DT plus value correct and value of flow through the network stated correctly (98)

A1: Correct deduction that the flow is maximal – must use all four words ‘maximum’, ‘flow’, ‘minimum’ and ‘cut’ (allow abbreviations for maximum and minimum) dependent on previous A1.