| Exam Board | AQA |
|---|---|
| Module | Further Paper 3 Discrete (Further Paper 3 Discrete) |
| Year | 2024 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Standard +0.8 This is a multi-source/multi-sink max flow problem requiring supersource/supersink construction, flow augmentation algorithm application, and critical analysis of network changes. While the techniques are standard Further Maths content, the three-part structure with conceptual reasoning in part (c) about flow reduction elevates it above routine textbook exercises. The need to track augmenting paths systematically and then analyze the impact of edge removal requires solid understanding rather than just mechanical application. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Augmenting Path | Extra Flow |
| Answer | Marks | Guidance |
|---|---|---|
| 8 | 8 | 18 |
| Answer | Marks |
|---|---|
| 8(a) | Connects supersource S to |
| Answer | Marks | Guidance |
|---|---|---|
| arcs | 1.1b | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| correct arcs | 1.1b | B1 |
| Subtotal | 2 | |
| Q | Marking instructions | AO |
| Answer | Marks |
|---|---|
| 8(b) | Finds at least one correct |
| Answer | Marks | Guidance |
|---|---|---|
| augmenting path | 3.1a | M1 |
| Answer | Marks | Guidance |
|---|---|---|
| augmenting path | 1.1b | A1 |
Total of all extra flows must be 7
| Answer | Marks | Guidance |
|---|---|---|
| augmenting path | 1.1b | A1 |
| Obtains 110 | 2.2a | B1 |
| Subtotal | 4 |
| Answer | Marks |
|---|---|
| Path | Extra |
| Answer | Marks | Guidance |
|---|---|---|
| SADFT | 4 | |
| SBGT | 2 | |
| SBCEGT | 1 | |
| Q | Marking instructions | AO |
| Answer | Marks | Guidance |
|---|---|---|
| 8(c) | Explains that EG is saturated/at | |
| maximum flow before the leak | 2.4 | E1 |
| Answer | Marks | Guidance |
|---|---|---|
| the engineer’s claim is correct | 2.3 | R1 |
| Subtotal | 2 | |
| Question total | 8 | |
| Q | Marking instructions | AO |
Question 8:
8 | 8 | 18 | 7 | 12 | 1 | 11
--- 8(a) ---
8(a) | Connects supersource S to
nodes A and B with directed
arcs and connects supersink T
to nodes F and G with directed
arcs | 1.1b | B1
Includes a correct upper
capacity on each of the four
correct arcs | 1.1b | B1
Subtotal | 2
Q | Marking instructions | AO | Marks | Typical solution
--- 8(b) ---
8(b) | Finds at least one correct
augmenting path and the extra
flow (may be seen on diagram).
Condone S & T not included in
augmenting path | 3.1a | M1 | Augmenting Extra
Path Flow
SADFT 4
SBGT 2
SBCEGT 1
Maximum flow = 110 litres per
second
Finds a second correct
augmenting path and the extra
flow.
Condone S & T not included in
augmenting path | 1.1b | A1
Finds a third correct augmenting
path and the extra flow, and no
incorrect paths.
Total of all extra flows must be 7
Condone S & T not included in
augmenting path | 1.1b | A1
Obtains 110 | 2.2a | B1
Subtotal | 4
Augmenting
Path | Extra
Flow
SADFT | 4
SBGT | 2
SBCEGT | 1
Q | Marking instructions | AO | Marks | Typical solution
--- 8(c) ---
8(c) | Explains that EG is saturated/at
maximum flow before the leak | 2.4 | E1 | EG is saturated, and none of the
flow through EG can be re-routed
as each of BG, DG and DF are
also saturated.
Hence, the maximum flow through
the network decreases by 31 litres
per second and so the engineer’s
claim is correct.
Explains that the flow of 31 litres
per second through EG cannot
be re-routed as BG, DG & DF
are also all saturated or that EG
is part of the minimum cut of the
network and then concludes that
the engineer’s claim is correct | 2.3 | R1
Subtotal | 2
Question total | 8
Q | Marking instructions | AO | Marks | Typical solutionFigure 1 shows a network of water pipes.
The number on each arc represents the upper capacity for each pipe in litres per second.
The numbers in the circles represent an initial feasible flow of 103 litres per second.
\includegraphics{figure_1}
\begin{enumerate}[label=(\alph*)]
\item On Figure 1 above, add a supersource $S$ and a supersink $T$ to the network.
[2 marks]
\item Using flow augmentation, find the maximum flow through the network.
You must indicate any flow augmenting paths clearly in the table below.
You may use Figure 2, on the opposite page, in your solution.
[4 marks]
\begin{tabular}{|c|c|}
\hline Augmenting Path & Extra Flow \\
\hline & \\
\hline & \\
\hline & \\
\hline & \\
\end{tabular}
Maximum Flow ______________ litres per second
\item While the flow through the network is at its maximum value, the pipe $EG$ develops a leak.
To repair the leak, an engineer turns off the flow of water through $EG$
The engineer claims that the maximum flow of water through the network will reduce by 31 litres per second.
Comment on the validity of the engineer's claim.
[2 marks]
\end{enumerate}
\hfill \mbox{\textit{AQA Further Paper 3 Discrete 2024 Q8 [8]}}