| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | June |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Lower and upper capacity networks |
| Difficulty | Standard +0.3 This is a standard network flows question with lower/upper capacities requiring routine application of cut calculation, feasible flow completion, and flow augmentation algorithm. While it involves multiple parts and careful bookkeeping, the techniques are algorithmic and well-practiced in D2, making it slightly easier than average A-level maths questions overall. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes7.04f Network problems: choosing appropriate algorithm |
## Question 6 Worked Solutions:
**(a)(i) Value of Cut C:**
Cut C passes through edges: $NT$ (capacity 9), $RT$ (capacity 16), $NR$ would need checking... The cut shown (dashed line) separates $\{S, M, Q, N, P, R\}$ from $\{T\}$, cutting edges: $NT = 9$, $RT = 16$
$$\text{Value of cut } C = 9 + 16 = 25$$
**(a)(ii):** The maximum flow from $S$ to $T$ is **at most 25**.
**(b) Feasible flow of 20 — finding MP, PN, QR, NR:**
Using flow conservation with known edge values at 20 total flow, working through the network to determine the four required edge flows.
---
If you can share the **actual mark scheme document**, I would be happy to extract and format it properly as requested. The mark scheme is typically a separate document published by AQA.
These pages appear to be **figure/diagram pages** (Figure 4, Figure 5, and Figure 6) provided for use in Question 6 of an AQA MD02 June 2007 paper. They contain:
- Network diagrams with nodes S, M, N, P, Q, R, T
- Capacity values on directed edges
- A blank Path/Flow table in Figure 5
**These pages do not contain any mark scheme content.** They are resource/answer pages given to candidates to write their working on.
To access the actual mark scheme for Question 6 of this paper (AQA MD02 June 2007), you would need the separate mark scheme document, which would typically show:
- Maximum flow values
- Valid flow augmenting paths
- Cut identification
- Mark allocations (M1, A1, B1 etc.)
If you have the mark scheme pages, please share those images and I can extract the content you need.6 [Figures 4, 5 and 6, printed on the insert, are provided for use in this question.]\\
The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second.\\
\includegraphics[max width=\textwidth, alt={}, center]{0c40b693-72d3-459c-bbb7-b9584a108b8e-07_713_1456_539_294}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Find the value of the cut $C$.
\item State what can be deduced about the maximum flow from $S$ to $T$.
\end{enumerate}\item Figure 4, printed on the insert, shows a partially completed diagram for a feasible flow of 20 litres per second from $S$ to $T$. Indicate, on Figure 4, the flows along the edges $M P , P N , Q R$ and $N R$.
\item \begin{enumerate}[label=(\roman*)]
\item Taking your answer from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 5.
\item Use flow augmentation on Figure 5 to find the maximum flow from $S$ to $T$. You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
\item Illustrate the maximum flow on Figure 6.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D2 2007 Q6 [15]}}