| 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 | Moderate -0.3 This is a standard network flows question testing routine application of max-flow min-cut algorithm. Part (a) is simple arithmetic (1 mark), parts (b)-(c) follow textbook labelling procedure, and part (d) applies the theorem mechanically. While multi-part with several marks, it requires no novel insight—just careful execution of a learned algorithm, making it slightly easier than average A-level difficulty. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks |
|---|---|
| (a) \(1 + 8 + 8 + 15 = 32\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| max flow = 21 | M2 A3 | |
| (c) max flow as = min cut of 21 \(\{S, A, B, C, D, F, G, J\} | \{E, H, I, T\}\) | M1 A1 |
| (d) new min cut = 24 \(\{S, A\} | \{B, C, D, E, F, G, H, I, J, T\}\) \(\therefore\) max flow could increase by 3 | M1 A1, A1 |
**(a)** $1 + 8 + 8 + 15 = 32$ | B1 |
**(b)** (i), (ii) e.g. augment $SABGFIT$ by 4 giving:
![Flow network diagram with augmented path]
max flow = 21 | M2 A3 |
**(c)** max flow as = min cut of 21 $\{S, A, B, C, D, F, G, J\} | \{E, H, I, T\}$ | M1 A1 |
**(d)** new min cut = 24 $\{S, A\} | \{B, C, D, E, F, G, H, I, J, T\}$ $\therefore$ max flow could increase by 3 | M1 A1, A1 | **(11)** |
---\begin{enumerate}
\item A sheet is provided for use in answering this question.
\end{enumerate}
A town has adopted a one-way system to cope with recent problems associated with congestion in one area.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{34728928-2a21-463d-982e-c46ab2dc05c8-5_684_1320_454_316}
\captionsetup{labelformat=empty}
\caption{Fig. 3}
\end{center}
\end{figure}
Figure 3 models the one-way system as a capacitated directed network. The numbers on the arcs are proportional to the number of vehicles that can pass along each road in a given period of time.\\
(a) Find the capacity of the cut which passes through the $\operatorname { arcs } A E , B F , B G$ and $C D$.\\
(1 mark)
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{34728928-2a21-463d-982e-c46ab2dc05c8-6_714_1280_171_333}
\captionsetup{labelformat=empty}
\caption{Fig. 4}
\end{center}
\end{figure}
Figure 4 shows a feasible flow of 17 through the same network. For convenience, a supersource, $S$, and a supersink, $T$, have been used.\\
(b) (i) Use the labelling procedure to find the maximum flow through this network listing each flow-augmenting route you use together with its flow.\\
(ii) Show your maximum flow pattern and state its value.\\
(c) Prove that your flow is the maximum possible through the network.\\
(d) It is suggested that the maximum flow through the network could be increased by making road $E F$ undirected, so that it has a capacity of 8 in either direction.
Using the maximum flow-minimum cut theorem, find the increase in maximum flow this change would allow.
\hfill \mbox{\textit{OCR D2 Q5 [11]}}