A2 June 2024 Q1

EdexcelCurrent spec10 marksFlows in Networks

Figure 1: capacitated directed network with capacities and initial flows (in circles): SA 13 (x), SB 12 (12), SC 15 (10), AE 2 (2), AD 15 (8), BD 19 (7), BC 7 (5), CD 12 (y), CF 11 (8), DE 13 (13), DT 5 (5), DF 10 (4), EF 4 (4), ET 17 (11), FT 16 (16); cut C1 shown as a dashed line — Figure 1

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

(a)

(i) State the value of \(x\)

(ii) State the value of \(y\) (2)

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

(d) Find, by inspection, a flow-augmenting route to increase the flow by four units.
You must state your route. (1)

The flow-augmenting route from (d) is used to increase the flow from S to T.

(e) Prove that the flow is now maximal. (3)

A vertex restriction is now applied so that no more than 12 litres per second can flow through E.

(f)

(i) Complete Diagram 1 in the answer book to show this restriction.

(ii) State the value of the maximum flow through the network with this restriction. (2)

Diagram 1: the network with vertices S, A, B, C, D, F and T and their arcs and capacities, with vertex E and its arcs omitted — Diagram 1

Scheme	Marks	AO
(i) \(x = 10\)	B1	1.1b
(ii) \(y = 7\)	B1	1.1b
	(2)

Scheme	Marks	AO
32	B1	1.1b
	(1)

Scheme	Marks	AO
Cut \(C_1\,(= 13 + 12 + 12 + 11) = 48\)	B1	1.1b
	(1)

Scheme	Marks	AO
SCDFET	B1	1.1b
	(1)

Mark scheme (e)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identification of cut through AE, DE, DT, EF and FT Value of flow = 36 It follows that flow is maximal	M1 A1 A1	2.1 3.1a 2.2a
	(3)

Notes

M1: Construct argument based on max-flow min-cut theorem (e.g. attempt to find a cut through saturated arcs). The cut may be drawn or stated in terms of arcs but not as nodes. (Note the only saturated arc not in the cut is SB)

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

dA1: Must have stated the value of the flow and correct deduction that the flow is maximal. Must use max flow = min cut all 4 words dependent on previous A mark so M1 A0 A1 is not possible

Vertex E split into E_IN and E_OUT: arcs A to E_IN (2) and D to E_IN (13), arc E_IN to E_OUT (12), arcs E_OUT to F (4) and E_OUT to T (17) — Mark scheme (f)