| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | State maximum flow along specific routes |
| Difficulty | Moderate -0.5 This is a standard network flows question testing routine application of max-flow min-cut theorem and labelling procedure. Part (a) is trivial identification, parts (b-d) follow textbook algorithms with no novel insight required, and part (e) is a straightforward modification. The multi-part structure and marks make it substantial, but each component is mechanical application of learned techniques, making it slightly easier than average A-level difficulty. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(D\) | B1 | Total: 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \((17+25+35+13+12+13) = 115\) | B1 | Total: 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(ABD_{\max} = 25\); \(GED_{\max} = 12\) | B1B1 | Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Forward and backward flows | M1 | |
| Adjusting flows on diagram | M1 | |
| Routes and flows in chart | M1 | |
| One correct route other than \(ABD\), \(GED\) | A1 | |
| Another correct | A1 | |
| Route \(ABD\ GED\ GFD\ GD\ AD\ AFD\ GEBD\); Flow \(25\ 12\ 16\ 13\ 17\ 15\ 7\) | A1 | All correct; Total: 6 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Total \(= 105\); Max flow diagram correct | B1 | |
| Correct diagram shown | B1 | Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Cut through \(AF, AD, BD, DE, DG\) and \(GF\) | M1 | Through 3 saturated arcs (fairly generous) |
| Correct | A1 | Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Reduce max flow by their \(EG\), changing 19 to 15 | M1 | Reduce by 4 since everywhere else saturated |
| \(\Rightarrow\) New max \(= 101\) | A1 | Correct answer \(\Rightarrow\) 2 marks; Total: 2 |
# Question 4:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $D$ | B1 | Total: 1 |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $(17+25+35+13+12+13) = 115$ | B1 | Total: 1 |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $ABD_{\max} = 25$; $GED_{\max} = 12$ | B1B1 | Total: 2 |
## Part (d)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Forward and backward flows | M1 | |
| Adjusting flows on diagram | M1 | |
| Routes and flows in chart | M1 | |
| One correct route other than $ABD$, $GED$ | A1 | |
| Another correct | A1 | |
| Route $ABD\ GED\ GFD\ GD\ AD\ AFD\ GEBD$; Flow $25\ 12\ 16\ 13\ 17\ 15\ 7$ | A1 | All correct; Total: 6 |
## Part (d)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Total $= 105$; Max flow diagram correct | B1 | |
| Correct diagram shown | B1 | Total: 2 |
## Part (d)(iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Cut through $AF, AD, BD, DE, DG$ and $GF$ | M1 | Through 3 saturated arcs (fairly generous) |
| Correct | A1 | Total: 2 |
## Part (e)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Reduce max flow by their $EG$, changing 19 to 15 | M1 | Reduce by 4 since everywhere else saturated |
| $\Rightarrow$ New max $= 101$ | A1 | Correct answer $\Rightarrow$ 2 marks; Total: 2 |
---4 [Figures 4 and 5, printed on the insert, are provided for use in this question.]\\
The network shows the routes along corridors from the playgrounds $A$ and $G$ to the assembly hall in a school. The number on each edge represents the maximum number of pupils that can travel along the corridor in one minute.\\
\includegraphics[max width=\textwidth, alt={}, center]{587bccdf-abd7-4a08-a76e-61374f322e2e-04_1043_1573_559_228}
\begin{enumerate}[label=(\alph*)]
\item State the vertex that represents the assembly hall.
\item Find the value of the cut shown on the diagram.
\item State the maximum flow along the routes $A B D$ and $G E D$.
\item \begin{enumerate}[label=(\roman*)]
\item Taking your answers to part (c) as the initial flow, use a labelling procedure on Figure 4 to find the maximum flow through the network.
\item State the value of the maximum flow and, on Figure 5, illustrate a possible flow along each edge corresponding to this maximum flow.
\item Verify that your flow is a maximum flow by finding a cut of the same value.
\end{enumerate}\item On a particular day, there is an obstruction allowing no more than 15 pupils per minute to pass through vertex $E$. State the maximum number of pupils that can move through the network per minute on this particular day.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2006 Q4 [16]}}