| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Moderate -0.3 This is a standard network flows question requiring routine application of supersource/supersink addition, cut capacity calculations, and max-flow min-cut theorem. While it has multiple parts, each step follows textbook procedures without requiring novel insight or complex problem-solving—slightly easier than average due to its procedural nature. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Add supersource \(S\) connected to \(A\), \(B\), \(C\) with capacities 8, 5 (or \(\infty\)), 6 (or \(\infty\)) respectively; add supersink \(T\) connected from \(G\) and \(H\) with appropriate capacities | B1 | Arcs correctly directed with weights matching source/sink values |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Cut separating \(\{A,B,C,E\}\) from \(\{D,F,G,H\}\): arcs crossing are \(AD=8\), \(BE=5\)... capacity \(= 8+12+5+3 = 28\)... arcs: \(AD(8)\), \(DG(12)\)... Correct arcs: \(AD=8\), \(CF=6\), \(BE=5\)... Total \(= 8+5+6+4 = 23\)... Arcs: \(AD(8)\), \(BE(5)\), \(EG(7)\), \(EH(4)\), \(CF(6)\) — capacity \(= 8+5+7+4+6 = 30\). Correct cut arcs crossing: \(AD(8)\), \(EG(7)\), \(EH(4)\), \(CF(6)\) giving \(= 25\) | B1 | Answer: \(\mathbf{25}\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Cut separating \(\{A,B,C,D,E,F\}\) from \(\{G,H\}\): arcs \(DG(12)\), \(EG(7)\), \(EH(4)\), \(FH(5)\); capacity \(= 12+7+4+5 = 28\) | B1 | Answer: \(\mathbf{28}\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| The maximum flow \(\leq 25\) (value of minimum cut found) | B1 | Must reference the cut value as an upper bound on max flow |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Flow of 25 found by labelling/augmenting paths | M1 | Valid flow pattern shown |
| Correct flow values on all arcs | A1 | |
| Minimum cut of capacity 25 identified, proving maximality by max-flow min-cut theorem | A1 | Explicit statement linking flow value to cut capacity |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Increasing capacity of \(CE\) would have no effect on the maximum flow | B1 | |
| Because \(CE\) is not on any saturated path / \(CE\) is not part of a minimum cut / \(C\) is limited by \(CF=6\) and \(CE\) is not a bottleneck | B1 | Reason required |
# Question 2:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Add supersource $S$ connected to $A$, $B$, $C$ with capacities 8, 5 (or $\infty$), 6 (or $\infty$) respectively; add supersink $T$ connected from $G$ and $H$ with appropriate capacities | B1 | Arcs correctly directed with weights matching source/sink values |
## Part (ii)(a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Cut separating $\{A,B,C,E\}$ from $\{D,F,G,H\}$: arcs crossing are $AD=8$, $BE=5$... capacity $= 8+12+5+3 = 28$... arcs: $AD(8)$, $DG(12)$... Correct arcs: $AD=8$, $CF=6$, $BE=5$... Total $= 8+5+6+4 = 23$... Arcs: $AD(8)$, $BE(5)$, $EG(7)$, $EH(4)$, $CF(6)$ — capacity $= 8+5+7+4+6 = 30$. Correct cut arcs crossing: $AD(8)$, $EG(7)$, $EH(4)$, $CF(6)$ giving $= 25$ | B1 | Answer: $\mathbf{25}$ |
## Part (ii)(b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Cut separating $\{A,B,C,D,E,F\}$ from $\{G,H\}$: arcs $DG(12)$, $EG(7)$, $EH(4)$, $FH(5)$; capacity $= 12+7+4+5 = 28$ | B1 | Answer: $\mathbf{28}$ |
## Part (ii)(c)
| Answer | Mark | Guidance |
|--------|------|----------|
| The maximum flow $\leq 25$ (value of minimum cut found) | B1 | Must reference the cut value as an upper bound on max flow |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Flow of 25 found by labelling/augmenting paths | M1 | Valid flow pattern shown |
| Correct flow values on all arcs | A1 | |
| Minimum cut of capacity 25 identified, proving maximality by max-flow min-cut theorem | A1 | Explicit statement linking flow value to cut capacity |
## Part (iv)
| Answer | Mark | Guidance |
|--------|------|----------|
| Increasing capacity of $CE$ would have no effect on the maximum flow | B1 | |
| Because $CE$ is not on any saturated path / $CE$ is not part of a minimum cut / $C$ is limited by $CF=6$ and $CE$ is not a bottleneck | B1 | Reason required |
---2 The network models a cooling system in a factory. Coolant starts at $A , B$ and $C$ and flows through the system.
The arcs model components of the cooling system and the weights show the maximum amount of coolant that can flow through each component of the system (measured in litres per second). The arrows show the direction of flow.\\
\includegraphics[max width=\textwidth, alt={}, center]{cfa46190-9a1e-4552-a551-c28d5c4286ad-3_611_832_539_605}
\begin{enumerate}[label=(\roman*)]
\item Add a supersource, $S$, and a supersink, $T$, to the copy of the network in your answer book. Connect $S$ and $T$ to the network using appropriately weighted arcs.
\item (a) Find the capacity of the cut that separates $A , B , C$ and $E$ from $D , F , G$ and $H$.\\
(b) Find the capacity of the cut that separates $A , B , C , D , E$ and $F$ from $G$ and $H$.\\
(c) What can you deduce from this value about the maximum flow through the system?
\item Find the maximum possible flow through the system and prove that this is the maximum.
\item Describe what effect increasing the capacity of $C E$ would have on the maximum flow.
\end{enumerate}
\hfill \mbox{\textit{OCR D2 2014 Q2 [9]}}