| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 20 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Calculate cut capacity |
| Difficulty | Standard +0.8 This is a comprehensive network flows question requiring multiple techniques (cut capacity calculation, flow augmentation, max-flow min-cut theorem proof, and analysis of vertex restrictions). While individual parts use standard D2 algorithms, the multi-part structure, need to explain theoretical concepts (why arcs can't both be full), and especially parts (vi)-(vii) requiring insight about maintaining maximum flow under constraints elevate this above routine exercises. However, it remains within the scope of well-prepared D2 students following established procedures. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(F\) only has flow out, no flow in | B1 | All arrows at \(F\) point out |
| Sink is at \(J\) | B1 | \(J\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 30 litres per second | B1 | 30 (cao), condone units missing |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| At most 5 flows out (of \(BA\)) along \(AD\) | B1 | Condone \(AD = 5\), as possibly referring to capacity |
| \(BA \leq 5\) and \(BE \leq 10\), so \(CB \leq 15\) | M1 | Using \(BA\) and \(BE\) to get \(CB\) (limit) 15 (or 'through \(B\)') |
| But any flow in \(FC\) must go along \(CB\), hence \(FC \leq 15\) (as given in question) | A1 | Correct argument for \(FC\), using \(\leq\) (or in words) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| A flow from \(F\) to \(J\) in which \(DE = FE = IH = 0\) and \(KJ = 13\) | M1 | A flow from \(F\) to \(J\) in which \(DE=FE=IH=0\) and \(KJ=13\) (even if some capacities are not met) |
| This flow (cao) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| At least six arcs with arrows correctly labelled (or all reversed) | M1 | |
| Correct (or all reversed) | A1 | If augmenting is done on diagram, accept original values provided they can be read |
| \(F-E-D-G-J\) or \(F-I-H-G-J\) (flow \(= 1\)) | B1 | \(F-E-D-G-J\) or \(F-I-H-G-J\) (or in reverse) (ft labelling) |
| Cut \(\{A,B,C,D,E,F,G,H,I,K,L\}, \{J\}\) | B1 | Cut through arcs \(GJ\) and \(KJ\) written or unambiguously shown (cao) |
| Max flow \(= 20\) litres per sec | B1 | 20 (cao) |
# Question 4:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $F$ only has flow out, no flow in | B1 | All arrows at $F$ point out |
| Sink is at $J$ | B1 | $J$ |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 30 litres per second | B1 | 30 (cao), condone units missing |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| At most 5 flows out (of $BA$) along $AD$ | B1 | Condone $AD = 5$, as possibly referring to capacity |
| $BA \leq 5$ and $BE \leq 10$, so $CB \leq 15$ | M1 | Using $BA$ and $BE$ to get $CB$ (limit) 15 (or 'through $B$') |
| But any flow in $FC$ must go along $CB$, hence $FC \leq 15$ (as given in question) | A1 | Correct argument for $FC$, using $\leq$ (or in words) |
## Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| A flow from $F$ to $J$ in which $DE = FE = IH = 0$ and $KJ = 13$ | M1 | A flow from $F$ to $J$ in which $DE=FE=IH=0$ and $KJ=13$ (even if some capacities are not met) |
| This flow (cao) | A1 | |
## Part (v)
| Answer | Marks | Guidance |
|--------|-------|----------|
| At least six arcs with arrows correctly labelled (or all reversed) | M1 | |
| Correct (or all reversed) | A1 | If augmenting is done on diagram, accept original values provided they can be read |
| $F-E-D-G-J$ or $F-I-H-G-J$ (flow $= 1$) | B1 | $F-E-D-G-J$ or $F-I-H-G-J$ (or in reverse) (ft labelling) |
| Cut $\{A,B,C,D,E,F,G,H,I,K,L\}, \{J\}$ | B1 | Cut through arcs $GJ$ and $KJ$ written or unambiguously shown (cao) |
| Max flow $= 20$ litres per sec | B1 | 20 (cao) |4 The network represents a system of pipes through which fluid can flow from a source, $S$, to a sink, $T$. The weights on the arcs represent pipe capacities in gallons per minute.\\
\includegraphics[max width=\textwidth, alt={}, center]{bfdc0280-9979-4bbe-81ba-9b1c36ff8374-6_597_1577_404_283}
\begin{enumerate}[label=(\roman*)]
\item Calculate the capacity of the cut that separates $\{ S , A , C , D \}$ from $\{ B , E , F , T \}$.
\item Explain why the $\operatorname { arcs } A C$ and $A D$ cannot both be full to capacity and why the $\operatorname { arcs } D F$ and $E F$ cannot both be full to capacity.
\item Draw a diagram to show a flow in which as much as possible flows through vertex $E$ but none flows through vertex $A$ and none flows through vertex $D$. State the maximum flow through vertex $E$.
An engineer wants to find a flow augmenting route to improve the flow from part (iii).
\item (a) Explain why there can be no flow augmenting route that passes through vertex $A$ but not through vertex $D$.\\
(b) Write down a flow augmenting route that passes through vertex $D$ but not through vertex $A$. State the maximum by which the flow can be augmented.
\item Prove that the augmented flow in part (iv)(b) is the maximum flow.
\item A vertex restriction means that the flow through $E$ can no longer be at its maximum rate. By how much can the flow through $E$ be reduced without reducing the maximum flow from $S$ to $T$ ? Explain your reasoning.
The pipe represented by the arc $B E$ becomes blocked and cannot be used.
\item Draw a diagram to show that, even when the flow through $E$ is reduced as in part (vi), the same maximum flow from $S$ to $T$ is still possible.
\end{enumerate}
\hfill \mbox{\textit{OCR D2 2013 Q4 [20]}}