Flows in Networks

Topic

A2 June 2025 Q4

EdexcelCurrent spec11 marksFlows in Networks

Figure 2: capacitated directed network with (lower, upper) capacities: SA (20, 40), SB (16, 35), SC (2, 33), AB (0, 11), AD (5, 12), AE (6, 13), CB (3, 19), CF (2, 6), BD (3, 16), GB (2, 9), BF (13, 27), DE (2, 15), DG (20, 25), GE (2, 6), GF (3, 5), GT (0, 2), ET (20, 29), FT (31, 43); cuts C1 and C2 shown as dashed lines — Figure 2

Figure 2 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 3: the same network labelled with excess capacities and potential backflows on arrows either side of each arc — Figure 3

A scientist monitors the system of pipes in which a fluid now flows from the source, S, to the sink, T.

The scientist initialises the labelling procedure for this system. The excess and potential backflows for this are shown on the arrows either side of each arc in Figure 3.

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

(e) Use your answer to part (d) to find a maximum flow pattern for this system of pipes and draw it on Diagram 1 in the answer book. (1)

Diagram 1: the directed network with no flow values — Diagram 1

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

Scheme	Marks	AO
\(C_1\,(= 40 + 35 + 19 + 6) = 100\)	B1	1.1b
\(C_2\,(= 13 + 12 + 16 - 2 - 3 + 43) = 79\)	B1	1.1b
	(2)

Mark scheme (b)

Scheme	Marks	AO
Deduces the maximum possible flow is \(\leqslant 79\) 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 = 58	B1	1.1b
	(1)

Mark scheme (d)

Scheme	Marks	AO
e.g. SAET – 4, SADET – 2, SBGFT – 2, SCFT – 1	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 9

Note possible flow augmenting routes are only _ADET + 2 _AET + 4 _BGFT + 2 _CFT + 1 where _ represents either S, SB, SC or SCB

(SADGFT + 2 is also valid but this prevents DET being increased)

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

Mark scheme (f)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identification of cut through AE, AD, BD, DG, GE, GT, GF, BF and CF Value of flow = 67 Therefore it follows that flow is maximal	M1 A1 A1	2.1 3.1a 2.2a
	(3)
	(11 marks)

Notes

M1: Construct argument based on max-flow min-cut theorem (e.g. attempt to find a cut through saturated arcs) (A valid cut through saturated arcs must either be listed or drawn)

May be drawn on either diagram or listed as arcs or set notation {S, A, B, C, G}{D, E, F, T}

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

A1: Correct deduction that the flow is maximal – must see all 4 words max flow min cut and conclusion - dependent on previous A mark

AS June 2025 Q2

EdexcelCurrent spec11 marksFlows in Networks

Figure 1: capacitated directed network from S to T with capacities and a feasible flow (in circles): SA 70 (63), SB 48 (44), AC 31 (31), AD 45 (32), CD 8 (0), CG 39 (31), BD 20 (20), DG 20 (20), DF 36 (32), BE 24 (24), EF 6 (6), FG 21 (21), FT 14 (14), FH 6 (3), EH 30 (18), GT 80 (72), HT 25 (21); 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 two conditions satisfied by a feasible flow. (2)

(b) List the seven saturated arcs in Figure 1. (1)

(i) cut \(C_1\)

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

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

(e) Use the answer to part (d) to draw the resulting flow pattern on Diagram 1 in the answer book. (2)

Diagram 1: the directed network of Figure 1 with no capacities or flows — Diagram 1

(f) Prove that the answer to part (e) is a maximum flow. (3)

Mark scheme (a)

Scheme	Marks	AO
On every arc actual flow cannot exceed capacity. Total flow into a vertex equals total flow out of the vertex for all vertices apart from the source and the sink.	B1 B1	1.2 1.2
	(2)

Notes

a1B1: Either condition.

a2B1: Both conditions (condone no mention of source and sink).

Scheme	Marks	AO
AC, BD, BE, DG, EF, FG, FT	B1	1.1b
	(1)

Scheme	Marks	AO
(i) \(C_1 = (31 + 45 + 20 + 6 + 25 =)\ 127\)	B1	1.1b
(ii) \(C_2 = (80 + 8 + 45 + 48 =)\ 181\)	B1	1.1b
	(2)

Scheme	Marks	AO
SADFEHT	B1	1.1b
	(1)

resulting flow: SA 67, SB 44, AC 31, AD 36, CD 0, CG 31, BD 20, DG 20, DF 36, BE 24, EF 2, FG 21, FT 14, FH 3, EH 22, GT 72, HT 25 — Mark scheme (e)

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

Mark scheme (f)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identifies cut through, AC, DC, DG, DF, BE or AC, CD, DG, FG, FT, HT capacity = 111 Value of flow =111 Therefore flow is maximal.	M1 A1 A1	2.1 3.1a 2.2a
	(3)
	(11 marks)

Notes

f1M1: Construct argument based on max-flow min-cut theorem so attempt to find a cut through saturated arcs (either stated or drawn).

f1A1: Use appropriate process for finding minimum cut, with cut and value correct.

f2A1: Correct deduction that flow is maximal. Must state value of the flow and see all 4 words max flow min cut and conclusion

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)

Scheme	Marks	AO
(i)	B1	3.3
(ii) maximum flow = 33	B1ft	2.2a
	(2)
	(10 marks)

AS June 2024 Q1

EdexcelCurrent spec8 marksFlows in Networks

Figure 1: capacitated directed network from S to T with capacities and a feasible flow (in circles): SA 42 (39), SB 37 (16), SC 35 (35), AE 26 (24), AB 21 (15), BF 18 (12), BD 24 (19), CD 21 (16), CG 19 (19), DJ 17 (17), DG 18 (18), FE 15 (0), EH 24 (24), FH 19 (18), JF 19 (6), JH 12 (6), GJ 14 (11), JK 10 (10), GK 26 (26), HT 48 (48), JT 27 (6), KT 40 (36); 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) State the value of this flow. (1)

(b) Explain why arcs CD and CG cannot both be saturated. (1)

(i) cut \(C_1\)

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

(d) Write down a flow augmenting route of weight 6 which saturates BF. (1)

The flow augmenting route in part (d) is applied to give an increased flow.

(e) Prove that this increased flow is maximal. (3)

Scheme	Marks	AO
Initial Flow = 90	B1	1.1b
	(1)

Mark scheme (b)

Scheme	Marks	AO
The maximum flow into C is 35. Maximum flow in CD is 21 and maximum flow in CG is 19. 35 < 21 + 19 and therefore CD and CG cannot both be saturated	B1	2.4
	(1)

Notes

B1: CAO (as a minimum accept: max inflow to C = 35 and max outflow = 40 and 35 <40)

Scheme	Marks	AO
(i) 26+18+24+21+19 = 108 (ii) 24+19+17+14+40 = 114	B1 B1	1.1b 1.1b
	(2)

Scheme	Marks	AO
SBFJT (+6)	B1	1.1b
	(1)

Mark scheme (e)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identification of cut through EH EF BF DJ DG and CG Capacity of cut = 96 Therefore it follows that flow is maximal	M1 A1 A1	2.1 3.1a 2.2a
	(3)
	(8 marks)

Notes

M1: Construct argument based on max-flow min-cut theorem (e.g. attempt to find a cut through saturated arcs) Cut must be drawn or listed as arcs not values (condone omission of EF for M1 only)

A1: Use appropriate process of finding a minimum cut (both cut and value correct)

A1: Correct deduction that the flow is maximal (dependent on previous A mark) (must use all four words Max Flow = Min Cut)

AS June 2023 Q2

EdexcelCurrent spec9 marksFlows in Networks

Figure 1: network from S to T with excess capacity and potential backflow on the arrows either side of each arc: SA 7, 18; SB 0, 15; SC 5, 39; AD 0, 18; AB 4, 0; BD 2, 32; EB 1, 17; CE 6, 21; CF 0, 18; ED 0, 9; DG 0, 31; DH 7, 28; EG 0, 8; GH 4, 36; GJ 2, 3; FE 2, 13; FJ 5, 5; HT 8, 64; JT 0, 8 — Figure 1

An engineer monitors a system of pipes through which a fluid flows from the source, S, to the sink, T.

The engineer initialises the labelling procedure for this system, and the excess capacities and potential backflows are shown on the arrows either side of each arc, as shown in Figure 1.

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

(b) Obtain the capacity of the cut that passes through the arcs SA, SB, CE, FE and FJ. (1)

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

(d) Use your answer to (c) to draw a maximum flow pattern on Diagram 1 in the answer book. (1)

Diagram 1: the directed network of Figure 1 with no values on the arcs — Diagram 1

(e) Prove that the answer to (d) is optimal. (3)

Scheme	Marks	AO
72	B1	1.1b
	(1)

Scheme	Marks	AO
Value of cut = 25 + 15 + 27 + 15 + 10 = 92	B1	1.1b
	(1)

Mark scheme (c)

Scheme	Marks	AO
e.g. SCEFJGHT – 3; SABDHT – 2 SCEFJGHT – 3; SCEBDHT – 1; SABDHT – 1 SABEFJGHT – 3; SABDHT – 2	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: One correct flow augmenting route found from S to T (so any routes that contain SB, BA, AD, CF, ED, EG, DG or JT are incorrect routes) - a ‘correct’ route is one in which the flow through the system can be increased

A1: Two correct routes (ignoring numerical value of the flow for this mark)

A1: cso – increasing the flow by 5 (and no more) – so at least two routes with corresponding correct values stated

maximum flow pattern: SA 20, SB 15, SC 42, AD 18, AB 2, BD 34, EB 17, ED 9, CE 24, CF 18, DG 31, DH 30, EG 8, GH 39, GJ 0, FE 10, FJ 8, HT 69, JT 8 — Mark scheme (d)

Scheme	Marks	AO
e.g. (based on the first example in (c))	B1	1.1b
	(1)

Mark scheme (e)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identification of cut through AD, BD, ED, EG, GJ and JT Value of flow = 77 Therefore it follows that flow is optimal	M1 A1 A1	2.1 3.1a 2.2a
	(3)
	(9 marks)

Notes

M1: Construct an argument based on max-flow min-cut theorem (e.g. attempt to find a cut (but not the one through SA, SB, CE, FE, FJ) through saturated arcs – must contain source on one side and sink on the other) – allow cut shown on the Diagram 1 in the answer book – this mark is dependent on an attempt at part (d) (so values on all but two arcs)

A1: Use appropriate process of finding a minimum cut – cut (AD, BD, ED, EG, GJ, JT) and the value of the flow through the network stated correctly (77)

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 and the B mark in (d)

A2 June 2023 Q1

EdexcelCurrent spec7 marksFlows in Networks

Figure 1: capacitated directed network with capacities and flows (in circles): SA 26 (20), SB 17 (15), SC 21 (19), AF 17 (12), AD 8 (8), BD 5 (5), BC 17 (10), CD 11 (11), CE 18 (18), DF 6 (2), DE 29 (22), FE 4 (4), FT 10 (10), ET 52 (44); 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 that pipe. The numbers in circles represent a feasible flow from S to T.

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

(b) Find the capacity of cut \(C_1\) and the capacity of cut \(C_2\) (2)

(d) Prove that, once the flow-augmenting route found in (c) has been applied, the flow is now maximal. (3)

Scheme	Marks	AO
54	B1	1.1b
	(1)

Scheme	Marks	AO
\(C_1\,(= 17 + 8 + 17 + 11 + 18) = 71\) \(C_2\,(= 17 + 6 + 29 + 17 + 21) = 90\)	B1 B1	1.1b 1.1b
	(2)

Scheme	Marks	AO
SAFDET	B1	1.1b
	(1)

Mark scheme (d)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identification of cut through FT, FE, DF, AD, BD, CD and CE Value of flow = 56 Therefore it follows that flow is maximal	M1 A1 A1	2.1 3.1a 2.2a
	(3)
	(7 marks)

Notes

M1: Construct argument based on max-flow min-cut theorem (e.g. attempt to find a cut through 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). If cut not drawn, must list arcs not values.

A1: Use appropriate process of finding a minimum cut – FT, FE, DF, AD, BD, CD and CE plus value correct and value of flow through the network stated correctly (56)

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

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.

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)

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)

A2 October 2020 Q5

EdexcelCurrent spec10 marksFlows in Networks

Figure 2: capacitated directed network with arcs (lower, upper): AD (5, 8), CA (4, 8), BA (1, 6), CB (1, 1), CD (4, 6), CE (2, 3), CF (3, 6), BF (0, 4), DE (1, 2), DG (5, 7), EG (0, 2), EH (5, 7), EJ (3, 7), FE (4, 6), FJ (2, 5), JH (4, 5), HG (6, 10); a dashed cut C1 crosses BF, CB, CA, CD, DE, EG and HG — Figure 2

Figure 2 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 capacities and upper capacities for the corresponding pipes, in litres per second.

(a) State the source node. (1)

(b) Explain why the sink node must be G. (1)

(d) Assuming that a feasible flow exists,

(i) explain why arc JH must be at its upper capacity,

(ii) explain why arcs AD and CD must be at their lower capacities. (2)

(e) Use Diagram 1 below to show a flow of 18 litres per second through the system. (2)

Diagram 1: the same directed network with vertices A to J and no weights — Diagram 1

(f) Prove that the answer to (e) is the maximum flow through the system. (3)

Mark scheme (d)

Scheme	Marks	AO
(i) Arc JH must be at its upper capacity of 5 as the two arcs that flow into J (EJ and FJ) have a lower capacity of \(2 + 3 = 5\)	B1	2.4
(ii) Arcs AD and CD must be at the lower capacities (which in total is 9) as the only two arcs (DG and DE) that flow out of D have a total upper capacity of \(7 + 2 = 9\)	B1	2.4
	(2)

Notes

(d)(i) B1: correct explanation that JH must be at its upper capacity (must refer to arcs EJ and FJ)

(d)(ii) B1: correct explanation that AD and CD must be at their lower capacities (must refer to arcs DG and DE)

Diagram 1 with flows: AD 5, CA 4, BA 1, CB 1, CD 4, CE 3, CF 6, BF 0, DE 2, DG 7, EG 1, EH 5, EJ 3, FE 4, FJ 2, JH 5, HG 10 — Mark scheme (e)

Mark scheme (f)

Scheme	Marks	AO
Use of max-flow min-cut theorem	M1	2.1
Identification of cut through DG, DE, CE, CF, CB, BA with a capacity of 18 and value of flow = 18	A1	3.1a
Therefore it follows that flow is maximal	A1	2.2a
	(3)
	(10 marks)

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

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)

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

A2 June 2019 Q6

EdexcelCurrent spec8 marksFlows in Networks

Figure 2: capacitated directed network from S to T with arcs (lower, upper): SA (7, 9), SC (8, 11), SB (13, 17), CA (3, 5), AE (10, 12), CE (2, 4), BC (0, 4), CG (5, 7), CF (3, 6), BF (3, 5), BD (4, 7), EH (5, 8), EG (3, 5), GH (10, 14), HT (17, 20), GT (4, 7), FG (5, 6), FT (6, 8), DF (1, 2), DT (4, 4); dashed cuts C1 (through SA, SC, BC, BF, BD) and C2 (through EH, EG, CE, CA, SC, BC, BF, DF, DT) — Figure 2

Figure 2 shows a capacitated, directed network. The network represents a system of pipes through which fluid flows from a source, S, to a sink, T.

The numbers \((l, u)\) on each arc represent, in litres per second, the lower capacity, \(l\), and the upper capacity, \(u\), of the corresponding pipe.

Two cuts \(C_1\) and \(C_2\) are shown.

(a) Find the capacity of

(i) cut \(C_1\)

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

(b) Explain why the arcs AE and CE cannot be at their upper capacities simultaneously. (1)

(d) Hence determine a minimum feasible flow and a maximum feasible flow through the system. You must draw these feasible flows on the diagrams below and give reasons to justify your answer. You should not apply the labelling procedure to find these flows. (4)

Blank copy of the network for the minimum feasible flow — Minimum feasible flow

Blank copy of the network for the maximum feasible flow — Maximum feasible flow

Mark scheme (b)

Scheme	Marks	AO
If AE and CE were both full to capacity then \(12 + 4 = 16\) litres per second would flow though E but the maximum capacity of the two arcs out of E (EH and EG) is only \(8 + 5 = 13\) so AE and CE cannot both be full to capacity	1B1	2.4
	(1)

Notes

1B1: Calculates maximum capacity entering E and compares with maximum capacity leaving E. Concludes that maximum capacity into E exceeds maximum capacity out of E.
Condone statements such as ‘flow into E \(= 12 + 4 < 13\) which is the flow out of E’.

Mark scheme (c)

Scheme	Marks	AO
The minimum flow through the arcs AE, CE, CG, FG, FT and DT (which provides a cut for the network) is \(10 + 2 + 5 + 5 + 6 + 4 = 32\) so a minimum of 32 must be flowing through the system so 31 is not possible.	1B1	2.4
	(1)

Notes

1B1: valid reason why the flow in the network cannot be 31 litres per second.

Note: If smallest of \(C_1\) and \(C_2\) in a) is less than 31 then DO NOT allow this mark for deducing that ‘31 > {smallest of answers from a} hence, flow of 31 is not possible’.

Minimum flow of 32: SA 7, SC 10, SB 15, CA 3, AE 10, CE 2, BC 4, CG 5, CF 4, BF 5, BD 6, EH 7, EG 5, GH 11, HT 18, GT 4, FG 5, FT 6, DF 2, DT 4 — Mark scheme (d)

Maximum flow of 34: SA 8, SC 11, SB 15, CA 3, AE 11, CE 2, BC 4, CG 6, CF 4, BF 5, BD 6, EH 8, EG 5, GH 11, HT 19, GT 5, FG 5, FT 6, DF 2, DT 4 — Mark scheme (d)

AS June 2019 Q3

EdexcelCurrent spec10 marksFlows in Networks

Figure 1: network from S to T with excess capacity and potential backflow on the arrows either side of each arc: SA 7, 24; SB 4, 21; AC 14, 18; AD 4, 6; BD 0, 4; BE 5, 17; CH 0, 11; CF 2, 7; DF 2, 3; DE 6, 2; DG 6, 5; FH 5, 3; FT 0, 5; FJ 0, 2; EG 0, 7; EJ 0, 12; GJ 6, 12; HT 19, 14; JT 7, 26 — Figure 1

Alexa is monitoring a system of pipes through which fluid can flow from the source, S, to the sink, T. Currently, fluid is flowing through the system from S to T.

Alexa initialises the labelling procedure for this system, and the excess capacities and potential backflows are shown on the arrows either side of each arc, as shown in Figure 1.

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

(b) Explain why arcs DF and DG can never both be full to capacity. (1)

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

(e) Use your answers to part (d) to find a maximum flow pattern for this system of pipes and draw it on Diagram 1 in the answer book. (1)

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

Mark scheme (b)

Scheme	Marks	AO
e.g. the total capacity of arcs DF and DG is 5 + 11 = 16. The capacity of the two arcs leading into D are 10 (from AD) and 4 (from BD) giving a total capacity into D of 14. As 14 < 16 arcs DF and DG cannot both be full to capacity	B1	2.4
	(1)

Notes

B1: CAO (as a minimum accept mention that the max flow into D is 14 and max flow out of D is 16 together with comparison of these two values – (node) D must be mentioned)

Mark scheme (d)

Scheme	Marks	AO
e.g. SACFHT – 2; SADGJT – 4; SBEDFHT – 2 e.g. SACFHT – 2; SADGJT – 2; SADFHT – 2; SBEDGJT – 2 e.g. SACFHT – 2; SADGJT –4; SBEDGJT – 2	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: One correct flow augmenting route found from S to T + flow value or two correct routes

A1: Two correct routes + correct flow values

A1: CSO – increasing the flow by 8 only

maximum flow pattern: SA 30, SB 23, AC 20, AD 10, BD 4, BE 19, CH 11, CF 9, DF 5, DE 0, DG 9, FH 7, FT 5, FJ 2, EG 7, EJ 12, GJ 16, HT 18, JT 30 — Mark scheme (e)

Mark scheme (f)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identification of cut through CH, CF, AD, BD, DE, EG and EJ Value of flow = 53 Therefore by the max-flow min-cut theorem it follows that flow is maximal	M1 A1 A1	2.1 3.1a 2.2a
	(3)
	(10 marks)

Notes

M1: Construct the start of an argument based on the max-flow min-cut theorem (that is an attempt to find a genuine cut together with the value of either their cut or flow (but not re-iterating the cut given in (c) – AC, AD, BD, DE, EG, EJ))

A1: Use appropriate process of finding a minimum cut – must see correct cut + value correct (accept ‘53’ and the cut either stated or drawn on either diagram)

A1: Correct deduction that the flow is maximal by stating ‘maximum flow (equal to) minimum cut’ – dependent on previous A mark and the correct flow in (e)

AS June 2018 Q3

EdexcelCurrent spec10 marksFlows in Networks

Figure 1: directed network from S to T with capacities: SB 130, BA 40, BE 100, BC 60, AD 65, ED 10, ET 15, DT 75, EF 25, FE 30, CF 30, FT 85; cuts C1 and C2 shown as dashed lines — Figure 1

Figure 1 models the flow of fluid through a system of pipes from a source, S, to a sink, T.
The weights on the arcs show the capacities of the corresponding pipes in litres per minute.
Two cuts \(C_1\) and \(C_2\) are shown.

(a) Find 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 possible flow through the system. (1)

(c) On Diagram 1 in the answer book, show how a flow of 120 litres per minute from S to T can be achieved. You do not need to apply the labelling procedure to find this flow. (2)

(d) Prove that 120 litres per minute is the maximum possible flow through the system. (2)

A new pipe is planned from S to A. Let the capacity of this pipe be \(x\) litres per minute.

(e) Find, in terms of \(x\) where necessary, the maximum possible flow through the new system. (3)

Mark scheme (b)

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

Notes

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

flow of 120: SB 120, BA 40, BE 50, BC 30, AD 40, ED 10, ET 15, DT 50, EF 25, FE 0, CF 30, FT 55 — Mark scheme (c)

Mark scheme (d)

Scheme	Marks	AO
Cut through arcs BA, ED, ET, EF (twice), CF	B1	3.1a
Maximum flow = minimum cut Flow = 120, Cut = 120 therefore flow of 120 is optimal	B1	2.1
	(2)

Notes

B1: finds a correct cut through saturated arcs directed from S to T

B1: correct mathematical argument that the maximum flow is 120 - dependent on correct cut and correct flow in (c) – must state ‘maximum flow = minimum cut’

Mark scheme (e)

Scheme	Marks	AO
\(0 \lt x \leqslant 25, \qquad\) flow is \(120 + x\) \(x \gt 25, \qquad\qquad\ \ \) flow is \(145\)	M1 A1 A1	3.1a 2.2a 2.3
	(3)
	(10 marks)

Notes

M1: understanding that the flow through the system will be different depending on the possible values of \(x\) (this could be shown by either of the flows being stated correctly or by consideration of the critical value of \(x = 25\))

A1: correct deduction of both possible flows: \(120 + x\) and 145

A1: correct argument (in terms of the correct inequalities) for when the flow is valid for \(120 + x\) and 145

SC in (e) – award M1A1 for one correct flow and interval