D2.3.2 Use of the labelling procedure to augment a flow to determine the…

Section
D2.3 Flows in networks
Level
AS & A level
Statement
Use of the labelling procedure to augment a flow to determine the maximum flow in a network.
Guidance
The arrow in the same direction as the arc will be used to identify the amount by which the flow along that arc can be increased. The arrow in the opposite direction will be used to identify the amount by which the flow in the arc could be reduced.
Since 2018
33 parts, 47 marks · topic pages: Flows in networks

Back to the checklist

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(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 · 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 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(d) 1 mark
(d) Write down a flow augmenting route of weight 6 which saturates BF. (1)
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(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 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(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 · 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(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 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(e) 1 mark
(e) Write down a flow‑augmenting route that increases the flow by three units. (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(e) 1 mark
(e) By inspection find one flow‑augmenting route to increase the flow by three units. You must state your route. (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)
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(d) 1 mark
(d) Write down a flow‑augmenting route, using the arc CF, that increases the flow by two units. (1)
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(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 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)

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.