| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 22 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Find minimum cut |
| Difficulty | Standard +0.3 This is a standard max-flow min-cut problem using the labelling procedure (Ford-Fulkerson algorithm), which is a core D2 topic. The network is small with only 6 nodes and straightforward structure. Part (a) is routine transcription, parts (b-c) apply textbook algorithms mechanically, and part (d) requires stating the max-flow min-cut theorem. While multi-step, it requires no novel insight—just careful execution of a learned procedure, making it slightly easier than average. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| (a) Network diagram with vertices S, A, B, C, D, T and edges: SA = 16, AC = 13, CT = 11, AD = 5, DT = 11, SB = 26, BD = 11, BT = 16 | M1 A2 | |
| (b) Minimum cut = {S, A, B, C, D} \ | {T} = 38 | M1 A1 |
| (c) Augment SACT by 11, SBT by 16, SBDT by 10 and SADT by 1, giving maximum flow diagram with flow values marked on edges | M2 A3 | |
| (d) Maximum as = to minimum cut | B1 | (11) |
**(a)** Network diagram with vertices S, A, B, C, D, T and edges: SA = 16, AC = 13, CT = 11, AD = 5, DT = 11, SB = 26, BD = 11, BT = 16 | M1 A2 | |
**(b)** Minimum cut = {S, A, B, C, D} \| {T} = 38 | M1 A1 | |
**(c)** Augment SACT by 11, SBT by 16, SBDT by 10 and SADT by 1, giving maximum flow diagram with flow values marked on edges | M2 A3 | |
**(d)** Maximum as = to minimum cut | B1 | (11) |The following matrix gives the capacities of the pipes in a system.
\begin{array}{c|c|c|c|c|c|c|c}
To & & S & T & A & B & C & D \\
From & & & & & & & \\
\hline
S & & -- & -- & 16 & 26 & -- & -- \\
T & & -- & -- & -- & -- & -- & -- \\
A & & -- & -- & -- & -- & 13 & 5 \\
B & & -- & 16 & -- & -- & -- & 11 \\
C & & -- & 11 & -- & -- & -- & -- \\
D & & -- & 11 & -- & -- & -- & -- \\
\end{array}
\begin{enumerate}[label=(\alph*)]
\item Represent this information as a digraph. [3 marks]
\item Find the minimum cut, expressing it in the form $\{$ $\}|\{$ $\}$, and state its value. [2 marks]
\item Starting from having no flow in the system, use the labelling procedure to find a maximal flow through the system. You should list each flow-augmenting route you use, together with its flow. [5 marks]
\item Explain how you know that this flow is maximal. [1 mark]
\end{enumerate}
[11 marks]
\hfill \mbox{\textit{OCR D2 Q5 [22]}}