| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| Session | June |
| Marks | 20 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Calculate cut capacity |
| Difficulty | Challenging +1.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 significantly above routine exercises. However, it remains within the D2 syllabus without requiring novel problem-solving approaches. |
| Spec | 7.02q Adjacency matrix: and weighted matrix representation7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(8+0+6+5+4 = 23\) gallons per minute | M1 | \(8+0+6+5+4\) or 23 |
| A1 | 23 with units |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| At most 6 gallons per minute can enter \(A\) so there cannot be 7 gallons per minute leaving it | B1 | Maximum into \(A=6\) |
| At most 7 gallons per minute can leave \(F\) so there cannot be 10 gallons per minute entering it | B1 | Maximum out of \(F=7\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| A diagram showing a flow with 12 through \(E\); flow is feasible (upper capacities not exceeded) | M1, M1 | Assume that blanks mean 0 |
| Nothing flows through \(A\) and \(D\) | A1 | |
| Maximum flow through \(E=12\) gallons per minute | B1 | 12 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| If flows through \(A\) but not \(D\) its route must be \(S-A-C-E\), but the flow through \(E\) is already a maximum | B1 | A correct explanation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(S-(B)-C-D-F-T\); 1 gallon per minute | M1, A1 | Follow through their part (iii); 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Flow \(= 12+1=13\) gallons per minute | ||
| Cut through \(ET\) and \(FT\) or \(\{S,A,B,C,D,E,F\},\{T\}=13\) gallons per minute | B1 | Identifying this cut in any way |
| Every cut forms a restriction; every cut \(\geq\) every flow; min cut \(\geq\) max flow | M1, A1 | Use of max flow – min cut theorem; min cut \(\geq\) max flow |
| This cut \(=\) this flow so must be min cut and max flow | B1 | This cut \(=\) this flow (or having shown both are 13) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| 3 gallons per minute | B1 | 3 |
| Must flow 6 along \(ET\) and 7 along \(FT\) | B1 | |
| Can send 4 into \(F\) from \(D\) so only need to send 9 through \(E\) | B1 | A correct explanation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| A diagram showing a flow of 13 without using \(BE\); flow is feasible and only sends 9 through \(E\) | M1, A1 | May imply directions and assume blanks mean 0 |
# Question 4(i)
| Answer/Working | Mark | Guidance |
|---|---|---|
| $8+0+6+5+4 = 23$ gallons per minute | M1 | $8+0+6+5+4$ or 23 |
| | A1 | 23 with units |
---
# Question 4(ii)
| Answer/Working | Mark | Guidance |
|---|---|---|
| At most 6 gallons per minute can enter $A$ so there cannot be 7 gallons per minute leaving it | B1 | Maximum into $A=6$ |
| At most 7 gallons per minute can leave $F$ so there cannot be 10 gallons per minute entering it | B1 | Maximum out of $F=7$ |
---
# Question 4(iii)
| Answer/Working | Mark | Guidance |
|---|---|---|
| A diagram showing a flow with 12 through $E$; flow is feasible (upper capacities not exceeded) | M1, M1 | Assume that blanks mean 0 |
| Nothing flows through $A$ and $D$ | A1 | |
| Maximum flow through $E=12$ gallons per minute | B1 | 12 |
---
# Question 4(iv)a
| Answer/Working | Mark | Guidance |
|---|---|---|
| If flows through $A$ but not $D$ its route must be $S-A-C-E$, but the flow through $E$ is already a maximum | B1 | A correct explanation |
---
# Question 4(iv)b
| Answer/Working | Mark | Guidance |
|---|---|---|
| $S-(B)-C-D-F-T$; 1 gallon per minute | M1, A1 | Follow through their part (iii); 1 |
---
# Question 4(v)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Flow $= 12+1=13$ gallons per minute | | |
| Cut through $ET$ and $FT$ or $\{S,A,B,C,D,E,F\},\{T\}=13$ gallons per minute | B1 | Identifying this cut in any way |
| Every cut forms a restriction; every cut $\geq$ every flow; min cut $\geq$ max flow | M1, A1 | Use of max flow – min cut theorem; min cut $\geq$ max flow |
| This cut $=$ this flow so must be min cut and max flow | B1 | This cut $=$ this flow (or having shown both are 13) |
---
# Question 4(vi)
| Answer/Working | Mark | Guidance |
|---|---|---|
| 3 gallons per minute | B1 | 3 |
| Must flow 6 along $ET$ and 7 along $FT$ | B1 | |
| Can send 4 into $F$ from $D$ so only need to send 9 through $E$ | B1 | A correct explanation |
---
# Question 4(vii)
| Answer/Working | Mark | Guidance |
|---|---|---|
| A diagram showing a flow of 13 without using $BE$; flow is feasible and only sends 9 through $E$ | M1, A1 | May imply directions and assume blanks mean 0 |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]{9057da95-c53a-416c-8340-c94aff366385-6_599_1580_402_280}
\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 arcs $A C$ and $A D$ cannot both be full to capacity and why the 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 2009 Q4 [20]}}