| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | January |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Maximum flow and cut theorem |
| Difficulty | Moderate -0.5 This question tests direct recall and application of the max-flow min-cut theorem with minimal problem-solving. Part (a) requires stating standard theoretical results (flow ≤ cut capacity, equality implies optimality), while part (b) involves a straightforward vertex conservation check. These are textbook applications requiring no novel insight or extended reasoning. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (i) Maximum flow \(= 50\) (flow equals cut capacity, so this is maximum) | \(B1\) | |
| (ii) Maximum flow \(\geq 35\); maximum flow \(\leq 50\); so \(35 \leq \text{max flow} \leq 50\) | \(B1\) | Cannot determine exact value |
| (iii) This is impossible; flow cannot exceed cut capacity, but flow of 50 exceeds cut of 35 — contradiction | \(B1B1\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Consider vertex \(F\): minimum flow in \(= 2+2+2 = 6\), maximum flow out \(= 3+7 = ?\); or consider that minimum into \(F\) is \(2+2+2=6\) but maximum out of \(F\) via \(CF\) is \(3\), \(FH\) is \(7\), \(FG\) is \(5\); minimum flow required into \(F \geq 6\) but maximum possible out \(\leq\) available capacity — flow conservation violated | \(M1\) | Identifying appropriate vertex |
| Minimum flow into \(F = 6\) but maximum flow out \(= 3+5+7\); minimum in exceeds some bound, or specifically minimum into \(C = 6+6 = 12\) but \(AC \leq 7\) | \(A1\) | Correct explanation with figures |
# Question 4:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| **(i)** Maximum flow $= 50$ (flow equals cut capacity, so this is maximum) | $B1$ | |
| **(ii)** Maximum flow $\geq 35$; maximum flow $\leq 50$; so $35 \leq \text{max flow} \leq 50$ | $B1$ | Cannot determine exact value |
| **(iii)** This is impossible; flow cannot exceed cut capacity, but flow of 50 exceeds cut of 35 — contradiction | $B1B1$ | |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Consider vertex $F$: minimum flow in $= 2+2+2 = 6$, maximum flow out $= 3+7 = ?$; or consider that minimum into $F$ is $2+2+2=6$ but maximum out of $F$ via $CF$ is $3$, $FH$ is $7$, $FG$ is $5$; minimum flow required into $F \geq 6$ but maximum possible out $\leq$ available capacity — flow conservation violated | $M1$ | Identifying appropriate vertex |
| Minimum flow into $F = 6$ but maximum flow out $= 3+5+7$; minimum in exceeds some bound, or specifically minimum into $C = 6+6 = 12$ but $AC \leq 7$ | $A1$ | Correct explanation with figures |4
\begin{enumerate}[label=(\alph*)]
\item When investigating three network flow problems, a student finds:
\begin{enumerate}[label=(\roman*)]
\item a flow of 50 and a cut with capacity 50 ;
\item a flow of 35 and a cut with capacity 50 ;
\item a flow of 50 and a cut with capacity 35 .
In each case, write down what the student can deduce about the maximum flow.
\end{enumerate}\item The diagram below shows a network. The numbers on the arcs represent the minimum and maximum flow along each arc respectively.
By considering the flow at an appropriate vertex, explain why a flow is not possible through this network.\\
\includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-10_1189_1559_1105_246}\\
(2 marks)
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2013 Q4 [6]}}