Flows in networks Decision 2

Papers
A level Paper 4D; AS Paper 2 (option 28)
Level
AS and A level
Spec
D2.3.1, D2.3.2, D2.3.3, D2.3.4, D2.3.5
Booklet
Nothing is given.
Since 2018
78 question parts, 137 marks

Notes, worked examples and practice for this topic are being written by our tutors. The past-paper questions below are ready now: work each one on paper, then open the mark scheme and the examiner's comment.

Past-paper questions

Print this topic as a pack questions first, then the mark schemes

Tap a question to zoom it. Mark scheme and examiner's comment open under each question.
June 2025 · AS Paper 2 (Decision 2) · Q2(a) 2 marks
2. C1 C C2 31 31 A G 31 39 72 80 T F S 32 36 14 14 44 48 B H C1 C2 18 30 24 24 E 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)
June 2025 · AS Paper 2 (Decision 2) · Q2(b) 1 mark
(b) List the seven saturated arcs in Figure 1. (1)
June 2025 · AS Paper 2 (Decision 2) · Q2(c) 2 marks
(c) Find the capacity of (i) cut C1 (ii) cut C2 (2)
June 2025 · AS Paper 2 (Decision 2) · Q2(d) 1 mark
(d) Write down a flow-augmenting route that increases the flow by four units. (1)
June 2025 · AS Paper 2 (Decision 2) · Q2(e) 2 marks
(e) Use the answer to part (d) to draw the resulting flow pattern on Diagram 1 in the answer book. (2)
June 2025 · AS Paper 2 (Decision 2) · Q2(f) 3 marks
(f) Prove that the answer to part (e) is a maximum flow. (3)
June 2025 · Paper 4D (Decision 2) · Q4(a) 2 marks
4. C2 C1 A (6, 13) E (5, 12) (20, 40) (2, 15) (0, 11) (3, 16) (16, 35) (2, 6) S (20, 25) (2, 9) (20, 29) B (13, 27) G (0, 2) (2, 33) (3, 19) (3, 5) C (2, 6) F (31, 43) T C1 C2 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 C1 (ii) cut C2 (2)
June 2025 · Paper 4D (Decision 2) · Q4(b) 1 mark
(b) Using only the capacities of cuts C1 and C2 , state what can be deduced about the maximum flow through the system. (1)
June 2025 · Paper 4D (Decision 2) · Q4(c) 1 mark
A E S B G C F T 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. (c) State the value of the initial flow. (1)
June 2025 · Paper 4D (Decision 2) · Q4(d) 3 marks
(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)
June 2025 · Paper 4D (Decision 2) · Q4(e) 1 mark
(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)
June 2025 · Paper 4D (Decision 2) · Q4(f) 3 marks
(f) Prove that the answer to part (e) is optimal. (3)
June 2024 · AS Paper 2 (Decision 2) · Q1(a) 1 mark
1. C1 C2 E A H B F S T J C G K C1 C2 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)
June 2024 · AS Paper 2 (Decision 2) · Q1(b) 1 mark
(b) Explain why arcs CD and CG cannot both be saturated. (1)
June 2024 · AS Paper 2 (Decision 2) · Q1(c) 2 marks
(c) Find the capacity of (i) cut C1 (ii) cut C2 (2)
June 2024 · AS Paper 2 (Decision 2) · Q1(d) 1 mark
(d) Write down a flow augmenting route of weight 6 which saturates BF. (1)
June 2024 · AS Paper 2 (Decision 2) · Q1(e) 3 marks
The flow augmenting route in part (d) is applied to give an increased flow. (e) Prove that this increased flow is maximal. (3)
June 2024 · Paper 4D (Decision 2) · Q1(a) 2 marks
1. C1 2 2 A E 17 11 15 8 x 12 12 19 7 5 5 B S T 15 10 y 16 16 C F 11 8 C1 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)
June 2024 · Paper 4D (Decision 2) · Q1(b) 1 mark
(b) State the value of the initial flow. (1)
June 2024 · Paper 4D (Decision 2) · Q1(c) 1 mark
(c) State the capacity of cut C1 (1)
June 2024 · Paper 4D (Decision 2) · Q1(d) 1 mark
(d) Find, by inspection, a flow‑augmenting route to increase the flow by four units. You must state your route. (1)
June 2024 · Paper 4D (Decision 2) · Q1(e) 3 marks
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)
June 2024 · Paper 4D (Decision 2) · Q1(f) 2 marks
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)
June 2023 · AS Paper 2 (Decision 2) · Q2(a) 1 mark
2. A H S G B J E C F 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)
June 2023 · AS Paper 2 (Decision 2) · Q2(b) 1 mark
(b) Obtain the capacity of the cut that passes through the arcs SA, SB, CE, FE and FJ. (1)
June 2023 · AS Paper 2 (Decision 2) · Q2(c) 3 marks
(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)
June 2023 · AS Paper 2 (Decision 2) · Q2(d) 1 mark
(d) Use your answer to (c) to draw a maximum flow pattern on Diagram 1 in the answer book. (1)
June 2023 · AS Paper 2 (Decision 2) · Q2(e) 3 marks
(e) Prove that the answer to (d) is optimal. (3)
June 2023 · Paper 4D (Decision 2) · Q1(a) 1 mark
1. C1 C2 A F 17 15 B S T C E C2 C1 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)
June 2023 · Paper 4D (Decision 2) · Q1(b) 2 marks
(b) Find the capacity of cut C1 and the capacity of cut C2 (2)
June 2023 · Paper 4D (Decision 2) · Q1(c) 1 mark
(c) By inspection, find a flow-augmenting route to increase the flow by two units. You must state your route. (1)
June 2023 · Paper 4D (Decision 2) · Q1(d) 3 marks
(d) Prove that, once the flow-augmenting route found in (c) has been applied, the flow is now maximal. (3)
June 2022 · AS Paper 2 (Decision 2) · Q2(a) 1 mark
2. C2 C1 E F B H A C G S T C2 C1 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)
June 2022 · AS Paper 2 (Decision 2) · Q2(b) 1 mark
(b) List the eight saturated arcs. (1)
June 2022 · AS Paper 2 (Decision 2) · Q2(c) 1 mark
(c) Explain why arc EH can never be full to capacity. (1)
June 2022 · AS Paper 2 (Decision 2) · Q2(d) 2 marks
(d) Find the capacity of (i) cut C1 (ii) cut C2 (2)
June 2022 · AS Paper 2 (Decision 2) · Q2(e) 1 mark
(e) Write down a flow‑augmenting route that increases the flow by three units. (1)
June 2022 · AS Paper 2 (Decision 2) · Q2(f) 3 marks
Given that the flow through the network is increased by three units, (f) prove that this new flow is maximal. (3)
June 2022 · Paper 4D (Decision 2) · Q4(a) 1 mark
4. C1 A E C2 B S G F C C1 C2 T 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)
June 2022 · Paper 4D (Decision 2) · Q4(b) 1 mark
(b) State the value of the initial flow. (1)
June 2022 · Paper 4D (Decision 2) · Q4(c) 1 mark
(c) Explain why arc FT cannot be full to capacity. (1)
June 2022 · Paper 4D (Decision 2) · Q4(d) 2 marks
(d) State the capacity of cut C1 and the capacity of cut C2 (2)
June 2022 · Paper 4D (Decision 2) · Q4(e) 1 mark
(e) By inspection find one flow‑augmenting route to increase the flow by three units. You must state your route. (1)
June 2022 · Paper 4D (Decision 2) · Q4(f) 3 marks
(f) Prove that, once the flow‑augmenting route found in part (e) has been applied, the flow is maximal. (3)
Nov 2021 · Paper 4D (Decision 2) · Q5(a) 2 marks
5. C2 C1 (5, 8) B A (0, 8) G (2, 5) (7, 11) (12, 17) (2, 5) E (4, 10) (4, 8) (3, 8) C S (1, 4) (0, 4) (1, 5) (3, 7) (10, 18) (18, 22) (5, 10) (3, 6) F (20, 30) (0, 2) T C1 C2 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 C1 (ii) cut C2 (2)
Nov 2021 · Paper 4D (Decision 2) · Q5(b) 1 mark
(b) Using only the capacities of cuts C1 and C2 , state what can be deduced about the maximum flow through the system. (1)
Nov 2021 · Paper 4D (Decision 2) · Q5(c) 1 mark
B A G E S C F T Figure 2 Figure 2 shows an initial flow through the same network. (c) State the value of the initial flow. (1)
Nov 2021 · Paper 4D (Decision 2) · Q5(d) 2 marks
(d) By entering values along BC, CF and DT, complete the labelling procedure on Diagram 1 in the answer book. (2)
Nov 2021 · Paper 4D (Decision 2) · Q5(e) 3 marks
(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)
Nov 2021 · Paper 4D (Decision 2) · Q5(f) 1 mark
(f) Use your answer to (e) to find a maximum flow pattern for this system of pipes and draw it on Diagram 2 in the answer book. (1)
Nov 2021 · Paper 4D (Decision 2) · Q5(g) 3 marks
(g) Prove that the answer to (f) is optimal. (3)
Nov 2021 · Paper 4D (Decision 2) · Q5(h) 3 marks
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 in the answer book to show this restriction. (ii) State the value of the maximum flow with this restriction. (3)
Oct 2020 · AS Paper 2 (Decision 2) · Q1(a) 2 marks
1. C2 C1 18 15 A 15 15 13 10 12 10 E 29 26 T S 37 32 B x y 18 18 C F 26 23 C1 C2 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)
Oct 2020 · AS Paper 2 (Decision 2) · Q1(b) 1 mark
(b) List the saturated arcs. (1)
Oct 2020 · AS Paper 2 (Decision 2) · Q1(c) 2 marks
Two cuts, C1 and C2, are shown in Figure 1. (c) Find the capacity of (i) C1 (ii) C2 (2)
Oct 2020 · AS Paper 2 (Decision 2) · Q1(d) 1 mark
(d) Write down a flow‑augmenting route, using the arc CF, that increases the flow by two units. (1)
Oct 2020 · AS Paper 2 (Decision 2) · Q1(e) 3 marks
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)
Oct 2020 · Paper 4D (Decision 2) · Q5(a) 1 mark
5. (5, 8) (5, 7) A G C1 (4, 8) (1, 2) (4, 6) (6, 10) (0, 2) C (1, 6) (5, 7) (2, 3) H E (3, 6) (1, 1) (3, 7) (4, 6) (4, 5) B (0, 4) J F (2, 5) C1 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)
Oct 2020 · Paper 4D (Decision 2) · Q5(b) 1 mark
(b) Explain why the sink node must be G. (1)
Oct 2020 · Paper 4D (Decision 2) · Q5(c) 1 mark
(c) Calculate the capacity of the cut C1 (1)
Oct 2020 · Paper 4D (Decision 2) · Q5(d) 2 marks
(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)
Oct 2020 · Paper 4D (Decision 2) · Q5(e) 2 marks
(e) Use Diagram 1 in the answer book to show a flow of 18 litres per second through the system. (2)
Oct 2020 · Paper 4D (Decision 2) · Q5(f) 3 marks
(f) Prove that the answer to (e) is the maximum flow through the system. (3)
June 2019 · AS Paper 2 (Decision 2) · Q3(a) 1 mark
3. C H A F 7 24 T S 2 6 0 4 7 26 G B E J 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)
June 2019 · AS Paper 2 (Decision 2) · Q3(b) 1 mark
(b) Explain why arcs DF and DG can never both be full to capacity. (1)
June 2019 · AS Paper 2 (Decision 2) · Q3(c) 1 mark
(c) Obtain the capacity of the cut that passes through the arcs AC, AD, BD, DE, EG and EJ. (1)
June 2019 · AS Paper 2 (Decision 2) · Q3(d) 3 marks
(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)
June 2019 · AS Paper 2 (Decision 2) · Q3(e) 1 mark
(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)
June 2019 · AS Paper 2 (Decision 2) · Q3(f) 3 marks
(f) Prove that the answer to part (e) is optimal. (3)
June 2019 · Paper 4D (Decision 2) · Q6(a) 2 marks
6. C2 (10, 12) (5, 8) H A E C1 (7, 9) (3, 5) (3, 5) (2, 4) (10, 14) (17, 20) C G S (8, 11) (5, 7) (4, 7) (5, 6) (3, 6) (13, 17) (0, 4) (6, 8) T F B (3, 5) (1, 2) (4, 7) (4, 4) C2 C1 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 C1 and C2 are shown. (a) Find the capacity of (i) cut C1 (ii) cut C2 (2)
June 2019 · Paper 4D (Decision 2) · Q6(b) 1 mark
(b) Explain why the arcs AE and CE cannot be at their upper capacities simultaneously. (1)
June 2019 · Paper 4D (Decision 2) · Q6(c) 1 mark
(c) Explain why a flow of 31 litres per second through the system is not possible. (1)
June 2019 · Paper 4D (Decision 2) · Q6(d) 4 marks
(d) Hence determine a minimum feasible flow and a maximum feasible flow through the system. You must draw these feasible flows on the diagrams in the answer book and give reasons to justify your answer. You should not apply the labelling procedure to find these flows. (4)
June 2018 · AS Paper 2 (Decision 2) · Q3(a) 2 marks
3. A S B E T C F C2 C1 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 C1 and C2 are shown. (a) Find the capacity of (i) cut C1 (ii) cut C2 (2)
June 2018 · AS Paper 2 (Decision 2) · Q3(b) 1 mark
(b) Using only the capacities of cuts C1 and C2 state what can be deduced about the maximum possible flow through the system. (1)
June 2018 · AS Paper 2 (Decision 2) · Q3(c) 2 marks
(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)
June 2018 · AS Paper 2 (Decision 2) · Q3(d) 2 marks
(d) Prove that 120 litres per minute is the maximum possible flow through the system. (2)
June 2018 · AS Paper 2 (Decision 2) · Q3(e) 3 marks
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)

Find an Edexcel Further Maths tutor

Stuck on this? Book a trial lesson with our Further Maths tutor.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.