| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| Session | January |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Lower and upper capacity networks |
| Difficulty | Standard +0.8 This is a multi-part network flows question with lower and upper capacities, requiring understanding of cut capacity calculations, flow conservation constraints, feasibility analysis, and the max-flow min-cut theorem. Part (ii) requires logical reasoning about vertex constraints, and part (iv) tests understanding of feasibility conditions. While systematic, it demands more conceptual depth than standard max-flow problems and involves 4 distinct parts with 11 total marks. |
| Spec | 7.02p Networks: weighted graphs, modelling connections |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(4+3-2+8-2+7\) | M1 | Imply method mark from 18, 20 or 22 |
| \(= 18\) litres per second | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| 3 litres per second flow out of \(B\) (arc \(BD\)) so only 2 litres per second can enter \(B\) from \(E\) and only 1 litre per second can enter \(B\) from \(S\) | B1 | At \(B\): 3 out and \(1+2\) in |
| At least 4 litres per second flow out of \(E\) to \(G\), 2 litres per second from \(E\) to \(B\) and 2 litres per second from \(E\) to \(H\), so 8 litres per second must flow into \(E\) from \(C\) | B1 | At \(E\): (at least) \(4+2+2\) out |
| 8 litres per second flows from \(C\) to \(E\) and at most 11 litres per second enters \(C\) from \(S\), so at most 3 litres per second flows from \(C\) to \(H\). Also, 2 litres per second flow from \(E\) to \(H\) so the most that can enter \(H\) is 5 litres per second. But at least 5 litres per second leave \(H\) along \(HT\), hence the flow in \(HT\) is 5 litres per second | M1, A1 | Considering \(C\) to show flow in \(CH\) is at most 3; At \(H\): \(2+3\) in |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Substantially correct attempt (at least 12 correct), not shown as excess capacities and potential backflows | M1 | |
| All correct | A1 | cao |
| Flow augmenting route: \(SADFT\) or \(SADGT\) | B1 | Either of these (correct) flow augmenting routes |
| Cut: \(X=\{S,B\}\), \(Y=\{A,C,D,E,F,G,H,T\}\) or \(X=\{S,A,B\}\), \(Y=\{C,D,E,F,G,H,T\}\) | B1 | Either of these (correct) cuts described in any way, or marked clearly on diagram |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(B\) would have at most 3 litres per second entering it and at least 5 litres per second leaving | M1, A1 | Identifying that problem is at \(B\); A correct explanation |
# Question 3:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| $4+3-2+8-2+7$ | M1 | Imply method mark from 18, 20 or 22 |
| $= 18$ litres per second | A1 | cao | [2] |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| 3 litres per second flow out of $B$ (arc $BD$) so only 2 litres per second can enter $B$ from $E$ and only 1 litre per second can enter $B$ from $S$ | B1 | At $B$: 3 out and $1+2$ in |
| At least 4 litres per second flow out of $E$ to $G$, 2 litres per second from $E$ to $B$ and 2 litres per second from $E$ to $H$, so 8 litres per second must flow into $E$ from $C$ | B1 | At $E$: (at least) $4+2+2$ out |
| 8 litres per second flows from $C$ to $E$ and at most 11 litres per second enters $C$ from $S$, so at most 3 litres per second flows from $C$ to $H$. Also, 2 litres per second flow from $E$ to $H$ so the most that can enter $H$ is 5 litres per second. But at least 5 litres per second leave $H$ along $HT$, hence the flow in $HT$ is 5 litres per second | M1, A1 | Considering $C$ to show flow in $CH$ is at most 3; At $H$: $2+3$ in | [4] |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Substantially correct attempt (at least 12 correct), not shown as excess capacities and potential backflows | M1 | |
| All correct | A1 | cao |
| Flow augmenting route: $SADFT$ or $SADGT$ | B1 | Either of these (correct) flow augmenting routes |
| Cut: $X=\{S,B\}$, $Y=\{A,C,D,E,F,G,H,T\}$ or $X=\{S,A,B\}$, $Y=\{C,D,E,F,G,H,T\}$ | B1 | Either of these (correct) cuts described in any way, or marked clearly on diagram | [4] |
## Part (iv)
| Answer | Mark | Guidance |
|--------|------|----------|
| $B$ would have at most 3 litres per second entering it and at least 5 litres per second leaving | M1, A1 | Identifying that problem is at $B$; A correct explanation | [2] |
---3 Answer this question on the insert provided.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{c5bfbe78-64c4-4254-ad83-0c90f4a54b18-4_625_1100_358_520}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{center}
\end{figure}
Fig. 1 represents a system of pipes through which fluid can flow from a source, $S$, to a sink, $T$. It also shows a cut $\alpha$. The weights on the arcs show the lower and upper capacities of the pipes in litres per second.\\
(i) Calculate the capacity of the cut $\alpha$.\\
(ii) By considering vertex $B$, explain why arc $S B$ must be at its lower capacity. Then by considering vertex $E$, explain why arc $C E$ must be at its upper capacity, and hence explain why arc $H T$ must be at its lower capacity.\\
(iii) On the diagram in the insert, show a flow through the network of 15 litres per second. Write down one flow augmenting route that allows another 1 litre per second to flow through the network. Show that the maximum flow is 16 litres per second by finding a cut of 16 litres per second.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{c5bfbe78-64c4-4254-ad83-0c90f4a54b18-4_602_1086_1809_568}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{center}
\end{figure}
Fig. 2 represents the same system, but with pipe $E B$ installed the wrong way round.\\
(iv) Explain why there can be no feasible flow through this network.
\hfill \mbox{\textit{OCR D2 2009 Q3 [12]}}