| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Lower and upper capacity networks |
| Difficulty | Standard +0.3 This is a standard application of the max-flow labelling procedure with lower/upper capacities, starting from a given feasible flow. While it requires careful bookkeeping and understanding of the algorithm, it's a routine textbook exercise in D2 with no novel problem-solving required. The cut verification in part (b) is direct application of max-flow min-cut theorem. Slightly easier than average A-level due to being algorithmic rather than requiring mathematical insight. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Augment \(SBDT\) by 2 and \(SABDT\) by 2, giving maximum flow diagram with flows shown | M2 A4 | Max flow = 19; flows: \(AC=10\), \(SA=8\), \(AB=3\), \(SB=12\), \(BD=8\), \(BDT\) path, \(CT=9\), \(DT=10\) etc. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Cut through arcs \(AC\), \(AB\) and \(SB\) | M1 A1 | |
| \(= 10 - 3 + 12 = 19\) | Capacity calculation | |
| Proves max. flow as no more flow is possible across this cut | B1 | (9 total) |
# Question 3:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Augment $SBDT$ by 2 and $SABDT$ by 2, giving maximum flow diagram with flows shown | M2 A4 | Max flow = 19; flows: $AC=10$, $SA=8$, $AB=3$, $SB=12$, $BD=8$, $BDT$ path, $CT=9$, $DT=10$ etc. |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Cut through arcs $AC$, $AB$ and $SB$ | M1 A1 | |
| $= 10 - 3 + 12 = 19$ | | Capacity calculation |
| Proves max. flow as no more flow is possible across this cut | B1 | **(9 total)** |
---\begin{enumerate}
\item A sheet is provided for use in answering this question.
\end{enumerate}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{df7b056f-1446-43f1-a2fd-c0d56533550e-3_588_1285_287_296}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{center}
\end{figure}
Figure 1 shows a capacitated, directed network. The numbers on each arc indicate the minimum and maximum capacity of that arc.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{df7b056f-1446-43f1-a2fd-c0d56533550e-3_648_1288_1155_296}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{center}
\end{figure}
Figure 2 shows a feasible flow through the same network.\\
(a) Using this as your initial flow pattern, use the labelling procedure to find a maximal flow. You should list each flow-augmenting route you use together with its flow and draw the maximal flow pattern.\\
(6 marks)\\
(b) Find a cut of the same value as your maximum flow and explain why this proves it gives the maximim possible flow.\\
\hfill \mbox{\textit{OCR D2 Q3 [9]}}