AS October 2020 Q1

EdexcelCurrent spec9 marksFlows in Networks

Figure 1: capacitated directed network from S to T with capacities and a feasible flow (in circles): SA 15 (15), SB 29 (26), SC 23 (y), AD 18 (15), AB 7 (0), BC 14 (x), BE 12 (10), BF 17 (7), CF 26 (23), DE 13 (10), DT 8 (5), FE 12 (12), ET 37 (32), FT 18 (18); cuts C1 and C2 shown as dashed lines — 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)

(i) Find the value of \(x\).

(ii) Find the value of \(y\). (2)

(b) List the saturated arcs. (1)

Two cuts, \(C_1\) and \(C_2\), are shown in Figure 1.

(i) \(C_1\)

(ii) \(C_2\) (2)

(d) Write down a flow-augmenting route, using the arc CF, that increases the flow by two units. (1)

Given that the flow through the network is increased by two units using the route found in (d),

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

Scheme	Marks	AO
(i) \((x =)\ 9\)	B1	1.1b
(ii) \((y =)\ 14\)	B1	1.1b
	(2)

Scheme	Marks	AO
SA, FE, FT	B1	1.1b
	(1)

Scheme	Marks	AO
(i) Value of cut \(C_1 = 18 + 12 + 17 + 26 = 73\)	B1	1.1b
(ii) Value of cut \(C_2 = 18 + 37 + 17 + 26 = 98\)	B1	1.1b
	(2)

Scheme	Marks	AO
e.g. SCFBET, SBCFBET	B1	1.1b
	(1)

Mark scheme (e)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identification of cut through SA, AB, BE, FE and FT Value of flow = 57 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) – if the cut is only given in terms of the capacity of the arcs (rather than in terms of the nodes at each end) then M1 only in this part

A1: Use appropriate process of finding a minimum cut – cut and value correct

A1: Correct deduction that the flow is maximal