| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Calculate cut capacity |
| Difficulty | Moderate -0.5 This is a standard network flows question from Decision Mathematics requiring calculation of cut capacities and finding maximum flow. Part (a) involves direct calculation of given cuts, part (b) is guided construction of a specific flow, and part (c) applies the max-flow min-cut theorem with a blocked edge. These are routine algorithmic procedures taught in D2 with no novel problem-solving required, making it slightly easier than average A-level maths questions overall. |
| Spec | 7.02r Graph modelling: model and solve problems using graphs7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(C_1\): cuts edges \(AB\), \(AC\), \(AD\) (from source side). Value \(= 5 + 5 + 60 = 70\) | B1 | Must identify correct edges in cut |
| \(C_2\): cuts edges \(HJ\), \(GJ\), \(IJ\) (into sink). Value \(= 30 + 10 + 30 = 70\) | B1 | Must identify correct edges in cut |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct identification of paths giving flows of 25 along \(HJ\), 10 along \(GJ\), 25 along \(IJ\) with total flow = 60 illustrated on Figure 1 | M1 | Method for finding valid flow of 60 |
| Correct labelling on Figure 1 showing all flows consistent with capacities and conservation | A1 | All flows correct and diagram fully labelled |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| With \(EH\) blocked, identify reduced network | M1 | Attempt to find maximum flow without \(EH\) |
| Finding augmenting paths in new network | M1 | Correct method applied |
| Maximum flow \(= 50\) illustrated correctly on Figure 2 | A1 | Correct value and valid flow pattern shown |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| State a cut of value 50 in the network with \(EH\) blocked | M1 | Valid cut identified |
| Since flow \(=\) cut \(= 50\), by max-flow min-cut theorem the flow is maximal | A1 | Must quote or use max-flow min-cut theorem explicitly |
# Question 3:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| $C_1$: cuts edges $AB$, $AC$, $AD$ (from source side). Value $= 5 + 5 + 60 = 70$ | B1 | Must identify correct edges in cut |
| $C_2$: cuts edges $HJ$, $GJ$, $IJ$ (into sink). Value $= 30 + 10 + 30 = 70$ | B1 | Must identify correct edges in cut |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct identification of paths giving flows of 25 along $HJ$, 10 along $GJ$, 25 along $IJ$ with total flow = 60 illustrated on Figure 1 | M1 | Method for finding valid flow of 60 |
| Correct labelling on Figure 1 showing all flows consistent with capacities and conservation | A1 | All flows correct and diagram fully labelled |
## Part (c)(i)
| Answer | Mark | Guidance |
|--------|------|----------|
| With $EH$ blocked, identify reduced network | M1 | Attempt to find maximum flow without $EH$ |
| Finding augmenting paths in new network | M1 | Correct method applied |
| Maximum flow $= 50$ illustrated correctly on Figure 2 | A1 | Correct value and valid flow pattern shown |
## Part (c)(ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| State a cut of value 50 in the network with $EH$ blocked | M1 | Valid cut identified |
| Since flow $=$ cut $= 50$, by max-flow min-cut theorem the flow is maximal | A1 | Must quote or use max-flow min-cut theorem explicitly |3 The diagram below shows a network of pipes with source $A$ and $\operatorname { sink } J$. The capacity of each pipe is given by the number on each edge.\\
\includegraphics[max width=\textwidth, alt={}, center]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-08_816_1280_443_386}
\begin{enumerate}[label=(\alph*)]
\item Find the values of the cuts $\mathrm { C } _ { 1 }$ and $\mathrm { C } _ { 2 }$.
\item Find by inspection a flow of 60 units, with flows of 25,10 and 25 along $H J , G J$ and $I J$ respectively. Illustrate your answer on Figure 1.
\item \begin{enumerate}[label=(\roman*)]
\item On a certain day the section $E H$ is blocked, as shown on Figure 2.
Find, by inspection or otherwise, the maximum flow on this day and illustrate your answer on Figure 2.
\item Show that the flow obtained in part (c)(i) is maximal.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-09_595_1065_376_475}
\end{center}
\end{figure}
(c)
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-09_617_1061_1142_477}
\end{center}
\end{figure}
Maximum flow = $\_\_\_\_$
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D2 2014 Q3 [9]}}