| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Find missing flow values |
| Difficulty | Standard +0.3 This is a standard network flows question requiring application of the labelling procedure (Ford-Fulkerson algorithm) and max-flow min-cut theorem. While it involves multiple parts and systematic working, these are routine algorithmic procedures taught directly in D2 with no novel problem-solving required. The initial part (a) simply applies conservation of flow at nodes, making it slightly easier than average overall. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Content | Marks | Guidance |
| (a) \(x = 2, y = 14\) | B2 | |
| (b) (i), (ii) Augment SCT by 2 and SBECADT by 3 giving network diagram with: edges A-D (capacity 13), S-A (capacity 18), S-B (capacity 19), A-C (capacity 5), B-C (capacity 2), C-D (capacity 2), D-T (capacity 15), B-E (capacity 1), C-E (capacity 17), E-T (capacity 18), D-E (capacity 20), with all intermediate capacities labeled | M2 A3 | |
| maximum flow = 53 | M2 A3 | |
| (c) (i) minimum cut = 53, passing through DT, CT and ET | B1 | |
| (ii) max flow = min cut; it is not possible to get any more flow across this cut | B1 | (9) |
| Content | Marks | Guidance |
|---------|-------|----------|
| (a) $x = 2, y = 14$ | B2 | |
| (b) (i), (ii) Augment SCT by 2 and SBECADT by 3 giving network diagram with: edges A-D (capacity 13), S-A (capacity 18), S-B (capacity 19), A-C (capacity 5), B-C (capacity 2), C-D (capacity 2), D-T (capacity 15), B-E (capacity 1), C-E (capacity 17), E-T (capacity 18), D-E (capacity 20), with all intermediate capacities labeled | M2 A3 | |
| maximum flow = 53 | M2 A3 | |
| (c) (i) minimum cut = 53, passing through DT, CT and ET | B1 | |
| (ii) max flow = min cut; it is not possible to get any more flow across this cut | B1 | (9) |\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]{b8eb80d5-5af5-4a8b-8335-6fae95f3aa73-3_881_1310_319_315}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{center}
\end{figure}
Figure 2 shows a capacitated, directed network.\\
The numbers in bold denote the capacities of each arc.\\
The numbers in circles show a feasible flow of 48 through the network.\\
(a) Find the values of $x$ and $y$.\\
(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) (i) Find a minimum cut, listing the arcs through which it passes.\\
(ii) Explain why this proves that the flow found in part (b) is a maximum.\\
\hfill \mbox{\textit{OCR D2 Q4 [9]}}