| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Calculate cut capacity |
| Difficulty | Standard +0.3 This is a standard network flows question testing routine application of cut calculations and the labelling procedure algorithm. Part (a)-(b) require simple arithmetic of arc capacities across given cuts, while (c)-(d) involve mechanical application of the flow-augmentation algorithm—all standard D2 textbook exercises with no novel problem-solving required. 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 |
|---|---|
| \(C_1 = 80\); \(C_2 = 94\) | B2 |
| Answer | Marks |
|---|---|
| Minimum cut: \(\{S, A, B, C, D, F\} \mid \{E, T\} = 57\) | M1 A1 |
| Answer | Marks |
|---|---|
| \(x = 15,\ y = 10,\ z = 36\) | B2 |
| Answer | Marks | Guidance |
|---|---|---|
| Augment \(SCET\) by 2 and \(SCAET\) by 1 giving maximum flow diagram shown | M2 A2 | |
| Max flow \(= 57\) | ||
| This is maximum flow as it is equal to the minimum cut | B1 | (11 marks total) |
# Question 4:
## Part (a)
| $C_1 = 80$; $C_2 = 94$ | B2 | |
## Part (b)
| Minimum cut: $\{S, A, B, C, D, F\} \mid \{E, T\} = 57$ | M1 A1 | |
## Part (c)
| $x = 15,\ y = 10,\ z = 36$ | B2 | |
## Part (d)
| Augment $SCET$ by 2 and $SCAET$ by 1 giving maximum flow diagram shown | M2 A2 | |
| Max flow $= 57$ | | |
| This is maximum flow as it is equal to the minimum cut | B1 | **(11 marks 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]{89e3545e-fa4b-47dd-8651-7c8f998df9e7-3_725_1303_274_340}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{center}
\end{figure}
Figure 2 above shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.\\
(a) Calculate the values of cuts $C _ { 1 }$ and $C _ { 2 }$.\\
(b) Find the minimum cut and state its value.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{89e3545e-fa4b-47dd-8651-7c8f998df9e7-3_645_1316_1430_338}
\captionsetup{labelformat=empty}
\caption{Fig. 3}
\end{center}
\end{figure}
Figure 3 shows a feasible flow through the same network.\\
(c) State the values of $x , y$ and $z$.\\
(d) 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.
State how you know that you have found a maximal flow.\\
\hfill \mbox{\textit{OCR D2 Q4 [11]}}