| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Vertex restrictions in networks |
| Difficulty | Standard +0.3 This is a standard network flow problem with a vertex capacity constraint, which is handled by the textbook technique of splitting vertex C into two nodes. Part (a) is routine application of this method, and part (b) is a standard labelling procedure (Ford-Fulkerson) with a given starting flow. While it requires careful bookkeeping across multiple steps, it involves no novel problem-solving—just methodical application of algorithms taught in D2. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{d88fdf1e-7547-434d-ba87-7f816e4386ba-1_627_1116_1190_388}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{center}
\end{figure}
Figure 1 shows a capacitated, directed network. The numbers on each arc indicate the maximum capacity of that arc.
In addition to the restrictions on flow through the arcs a maximum flow of 6 units is allowed to pass through vertex $C$.
\begin{enumerate}[label=(\alph*)]
\item Redraw the network to take into account this restriction.
\item Starting with an initial flow of 6 units along SADT and 6 units along SBT 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.
\end{enumerate}
\hfill \mbox{\textit{OCR D2 Q2 [8]}}