A2 October 2021 Q5

EdexcelCurrent spec16 marksFlows in Networks

Figure 1: capacitated directed network with lower and upper capacities: SA (4, 10), AB (5, 8), SB (7, 11), SC (3, 8), SD (10, 18), BC (2, 5), BE (12, 17), BG (0, 8), EC (4, 8), DC (5, 10), DF (3, 6), DT (0, 2), CF (18, 22), EF (0, 4), EG (2, 5), GF (1, 4), ET (3, 7), FT (20, 30), GT (1, 5); cuts C1 and C2 shown as dashed lines — Figure 1

Figure 1 shows a capacitated, directed network. The network represents a system of pipes through which fluid can flow.

The weights on the arcs show the lower and upper capacities for the corresponding pipes, in litres per second.

(a) Calculate the capacity of

(i) cut \(C_1\)

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

(b) Using only the capacities of cuts \(C_1\) and \(C_2\), state what can be deduced about the maximum flow through the system. (1)

Figure 2: initial flow through the same network: SA 5, AB 5, SB 11, SC 6, SD 14, BC 2, BE 12, BG 2, EC 6, DC 6, DF 6, DT 2, CF 20, EF 0, EG 2, GF 2, ET 4, FT 28, GT 2 — Figure 2

Figure 2 shows an initial flow through the same network.

(d) By entering values along \(BC\), \(CF\) and \(DT\), complete the labelling procedure on Diagram 1 below. (2)

Diagram 1: the network with excess capacities and potential backflows marked by arrows on each arc, except arcs BC, CF and DT which have empty arrows — Diagram 1

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

(f) Use your answer to (e) to find a maximum flow pattern for this system of pipes and draw it on Diagram 2 below. (1)

Diagram 2: the network with vertices S, A, B, C, D, E, F, G and T and its directed arcs, without values — Diagram 2

(g) Prove that the answer to (f) is optimal. (3)

A vertex restriction is now applied to \(B\) so that no more than 16 litres per second can flow through it.

(h)

(i) Complete Diagram 3 below to show this restriction.

(ii) State the value of the maximum flow with this restriction. (3)

Diagram 3: the network with vertex B and its arcs omitted: SA (4, 10), SC (3, 8), SD (10, 18), EC (4, 8), DC (5, 10), DF (3, 6), DT (0, 2), CF (18, 22), EF (0, 4), EG (2, 5), GF (1, 4), ET (3, 7), FT (20, 30), GT (1, 5) — Diagram 3

Scheme	Marks	AO
(i) \(C_1 = 8 + 11 + 8 + 10 + 6 + 2 = 45\) (ii) \(C_2 = 8 + 17 - 4 - 0 - 1 + 30 + 2 = 52\)	B1 B1	1.1b 1.1b
	(2)

Mark scheme (b)

Scheme	Marks	AO
Deduces the maximum possible flow is \(\leqslant 45\) litres per second	B1ft	2.2a
	(1)

Notes

B1ft: Deduced from their least value given in (a) - must include ‘less than or equal to’ (oe)

Scheme	Marks	AO
Initial flow = 36	B1	1.1b
	(1)

Labelling on arcs: BC excess capacity 3, backflow 0; CF excess capacity 2, backflow 2; DT excess capacity 0, backflow 2 — Mark scheme (d)

Scheme	Marks	AO
	M1 A1	1.1b 1.1b
	(2)

Mark scheme (e)

Scheme	Marks	AO
e.g., SABGT – 2, SCFT – 2, SDCET – 2, SABET – 1 e.g., SABGT – 3, SCFT – 2, SDCET – 2	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: One flow augmenting route found from S to T

A1: Two correct routes + flow values

A1: cso – increasing the flow by 7

Scheme	Marks	AO
e.g.	B1	2.2a
	(1)

Mark scheme (g)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identification of cut through AB, SB, BC, EC, CF, DF and DT Value of flow = 43 Therefore 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)

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

A1: Correct deduction that the flow is maximal

Vertex B split into B IN and B OUT: arcs A to B IN (5,8) and S to B IN (7,11), arc B IN to B OUT (0,16), arcs B OUT to G (0,8), B OUT to C (2,5) and B OUT to E (12,17) — Mark scheme (h)