| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | January |
| Marks | 14 |
| 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 flow augmentation algorithm. While the topic is Further Maths level, the question follows a predictable structure with scaffolded parts (complete given flow, apply algorithm, verify with cut) requiring methodical execution rather than novel insight. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(MN\) correct | B1 | |
| \(NT\) correct | B1 | |
| \(PQ\) correct | B1 | |
| \(NP\) correct | B1 | 4 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial flow indicated as surplus forward and backward flows | M1 | |
| Use of flow augmentation | M1 | |
| One flow correctly identified (e.g. \(SMNT\ 2\); \(SPQT\ 2\)) | A1 | |
| All possible flows correct | A1 | |
| Amending flows (dependent on first M1); final situation with saturation at \(M\) and \(P\) | M1 | |
| Correct | A1 | 6 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Max flow \(= 14\) | B1 | |
| Correct diagram shown | B1 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Cut through 2 of their saturated arcs: \(\{S,M\}/\{P,N,Q,T\}\) or cuts through \(MN\), \(MP\) & \(SP\) | M1 | Cut on original network |
| Described or drawn correctly | A1 | 2 |
## Question 4:
### Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $MN$ correct | B1 | |
| $NT$ correct | B1 | |
| $PQ$ correct | B1 | |
| $NP$ correct | B1 | **4** |
### Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial flow indicated as surplus forward and backward flows | M1 | |
| Use of flow augmentation | M1 | |
| One flow correctly identified (e.g. $SMNT\ 2$; $SPQT\ 2$) | A1 | |
| All possible flows correct | A1 | |
| Amending flows (dependent on first M1); final situation with saturation at $M$ and $P$ | M1 | |
| Correct | A1 | **6** |
### Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Max flow $= 14$ | B1 | |
| Correct diagram shown | B1 | **2** |
### Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Cut through 2 of their saturated arcs: $\{S,M\}/\{P,N,Q,T\}$ or cuts through $MN$, $MP$ & $SP$ | M1 | Cut on **original** network |
| Described or drawn correctly | A1 | **2** |4 [Figures 3, 4 and 5, 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]{30a88efe-fe9e-4384-a3e3-da2a05326797-04_547_1214_555_404}
\begin{enumerate}[label=(\alph*)]
\item Figure 3, on the insert, shows a partially completed diagram for a feasible flow of 10 litres per second from $S$ to $T$. Indicate, on Figure 3, the flows along the edges $M N , P Q , N P$ and $N T$.
\item \begin{enumerate}[label=(\roman*)]
\item Taking your answer from part (a) as an initial flow, use flow augmentation on Figure 4 to find the maximum flow from $S$ to $T$.
\item State the value of the maximum flow and illustrate this flow on Figure 5.
\end{enumerate}\item Find a cut with capacity equal to that of the maximum flow.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2006 Q4 [14]}}