| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Lower and upper capacity networks |
| Difficulty | Standard +0.8 This is a multi-part network flows question requiring cut calculation, feasible flow completion, flow augmentation algorithm, and max-flow min-cut verification. While the techniques are standard for D2, the lower/upper capacity constraints add complexity beyond basic max-flow problems, and the multi-step algorithmic work with careful bookkeeping makes this moderately challenging for A-level. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree7.04e Route inspection: Chinese postman, pairing odd nodes7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Cut \(Q\) passes through edges \(BT\), \(DE\), \(ET\) with capacities \(6\), \(6\), \(15\) | B1 | Identifying the edges in cut \(Q\) |
| Value of cut \(Q = 6 + 6 + 15 = 27\) | B1 | Correct value |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(BT = 6\) (flow along \(BT\)) | B1 | Must be consistent with feasible flow of 24 and capacities |
| \(DE = 3\), \(ET = 9\) (or equivalent consistent values) | B1 | Both correct, flows must balance at nodes \(D\) and \(E\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Potential increases shown on edges not at upper capacity | B1 | Correct increases indicated |
| Potential decreases shown on edges with flow above lower capacity | B1 | Correct decreases indicated |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Valid flow augmenting path identified (e.g. \(S \to A \to B \to D \to T\)) | M1 | Must be a valid path using potential increases/decreases |
| Correct flow value for augmenting path | A1 | Correct bottleneck value |
| Further augmentation if needed | M1 | Second valid path |
| Correct updated flows | A1 | All flows correct |
| Maximum flow \(= 29\) | A1 | Correct final answer |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Maximum flow of 29 correctly illustrated on Figure 5 | B1 | Flows correctly marked |
| All flows feasible (within lower and upper bounds) and balanced at nodes | B1 | Must satisfy all constraints |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Cut through edges \(\{BT, DT, ET\}\) or equivalent with value \(= 29\) | B1 | Any valid minimum cut with correct value equal to maximum flow |
# Question 6:
## Part (a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Cut $Q$ passes through edges $BT$, $DE$, $ET$ with capacities $6$, $6$, $15$ | B1 | Identifying the edges in cut $Q$ |
| Value of cut $Q = 6 + 6 + 15 = 27$ | B1 | Correct value |
## Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $BT = 6$ (flow along $BT$) | B1 | Must be consistent with feasible flow of 24 and capacities |
| $DE = 3$, $ET = 9$ (or equivalent consistent values) | B1 | Both correct, flows must balance at nodes $D$ and $E$ |
## Part (c)(i):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Potential increases shown on edges not at upper capacity | B1 | Correct increases indicated |
| Potential decreases shown on edges with flow above lower capacity | B1 | Correct decreases indicated |
## Part (c)(ii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Valid flow augmenting path identified (e.g. $S \to A \to B \to D \to T$) | M1 | Must be a valid path using potential increases/decreases |
| Correct flow value for augmenting path | A1 | Correct bottleneck value |
| Further augmentation if needed | M1 | Second valid path |
| Correct updated flows | A1 | All flows correct |
| Maximum flow $= 29$ | A1 | Correct final answer |
## Part (c)(iii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum flow of 29 correctly illustrated on Figure 5 | B1 | Flows correctly marked |
| All flows feasible (within lower and upper bounds) and balanced at nodes | B1 | Must satisfy all constraints |
## Part (d):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Cut through edges $\{BT, DT, ET\}$ or equivalent with value $= 29$ | B1 | Any valid minimum cut with correct value equal to maximum flow |6 The network shows a system of pipes with the lower and upper capacities for each pipe in litres per minute.\\
\includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-12_810_1433_429_306}
\begin{enumerate}[label=(\alph*)]
\item Find the value of the cut $Q$.
\item Figure 3 opposite shows a partially completed diagram for a feasible flow of 24 litres per minute from $S$ to $T$. Indicate, on Figure 3, the flows along the edges $B T , D E$ and $E T$.
\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 4 opposite.
\item Use flow augmentation on Figure 4 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 5 opposite.
\end{enumerate}\item Find a cut with value equal to that of the maximum flow.
You may wish to show the cut on the network above.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_759_1442_276_299}
\end{center}
\end{figure}
Figure 4
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_764_1438_1930_296}
\end{center}
\end{figure}
\includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-15_2349_1691_221_153}\\
\includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-16_2489_1719_221_150}
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2010 Q6 [14]}}