AS June 2022 Q2

EdexcelCurrent spec9 marksFlows in Networks

Figure 1: capacitated directed network from S to T with capacities and a feasible flow (in circles): SA 32 (27), SD 23 (23), AB 18 (18), AC 13 (9), BE 10 (10), BF 6 (2), BC 6 (6), CF 12 (10), CG 13 (10), DC 8 (5), DG 16 (8), DT 10 (10), FE 19 (16), GF 5 (4), GE 5 (5), GH 6 (6), GT 3 (3), EH 37 (31), HT 42 (37); cuts C1 and C2 shown as dashed curves — Figure 1

Figure 1 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent a feasible flow from S to T.

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

(b) List the eight saturated arcs. (1)

(d) Find the capacity of

(i) cut \(C_1\)

(ii) cut \(C_2\) (2)

(e) Write down a flow-augmenting route that increases the flow by three units. (1)

Given that the flow through the network is increased by three units,

(f) prove that this new flow is maximal. (3)

Scheme	Marks	AO
50	B1	1.1b
	(1)

Scheme	Marks	AO
Saturated arcs: AB, BC, SD, BE, DT, GE, GH and GT	B1	1.1b
	(1)

Mark scheme (c)

Scheme	Marks	AO
e.g., the capacity of arc EH is 37. The three arcs that flow into E are BE, FE and GE. The total capacity of these three arcs is 10 + 19 + 5 = 34 and as 37 > 34, EH cannot be full to capacity.	B1	2.4
	(1)

Notes

B1: Correct reasoning for why EH cannot be full to capacity (e.g., EH has capacity 37 but the total capacity of the arcs that flow into E is only 34 so EH cannot be full to capacity). Must be numerical.

Scheme	Marks	AO
(i) Value of cut \(C_1\) = 10 + 6 + 6 + 13 + 23 = 58	B1	1.1b
(ii) Value of cut \(C_2\) = 37 + 6 + 12 + 13 + 23 = 91	B1	1.1b
	(2)

Scheme	Marks	AO
e.g. SACBFEHT	B1	1.1b
	(1)

Mark scheme (f)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identification of cut through BE, FE, GE, GH, GT, DT Value of flow = 53 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 cut shown on the diagram

A1: Use appropriate process of finding a minimum cut – cut (BE, FE, GE, GH, GT, DT) and value of flow through the network stated correctly (53)

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