| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2011 |
| Session | January |
| Marks | 18 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Lower and upper capacity networks |
| Difficulty | Standard +0.3 This is a standard network flows question with lower/upper capacities covering routine D2 topics: identifying source/sink, calculating cut capacity, finding feasible flows, and applying max-flow min-cut theorem. While it has multiple parts, each requires straightforward application of well-defined algorithms rather than problem-solving insight. Slightly easier than average A-level due to the procedural nature of network flow questions. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| \(B\) is the source (all flows out at \(B\)); \(E\) is the sink (all flows in at \(E\)) | B1 | Both \(B\) and \(E\) (assume first answer is source); reasons not needed |
| Answer | Marks | Guidance |
|---|---|---|
| \(4+4+4+5+5 = 22\) litres per second | M1, A1 | Substantially correct using upper capacities; 22 |
| Answer | Marks | Guidance |
|---|---|---|
| Does not partition source from sink | B1 | Source and sink are both in the same set |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | B1 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| At least \(3+1=4\) must flow out of \(D\); 4 is the most that can flow in, so flow must be 4; at least 1 must flow along \(AE \Rightarrow BA = 5\) | B1, B1 | 4 must flow out of vertex \(D\); \(DG=3\) and \(DE=1\) at minimum |
| Answer | Marks | Guidance |
|---|---|---|
| At least \(3+2=5\) must flow out of \(I\); 5 must flow along \(FI\); at least 5 must flow along \(CF\); so at least \(2+5=7\) must flow along \(BC\) | B1, M1, A1 | 5 cao; substantially correct starting at \(I\) tracing back along \(IFCB\); 5 must flow along \(FI\); wholly correct reasoning; \(CF=5\) and \(CE=2\), hence 7 |
| Answer | Marks | Guidance |
|---|---|---|
| Minimum flow: \(BA=5, BC=7, BE=2\) | M1, A1 | \(BA=5, BC=7, BE=2\); this flow (assume blank means zero) |
| Maximum flow: \(BA=5, BC=8, BE=4\) | M1, A1 | \(BA=5, BC=8, BE=4\); this flow |
# Question 4:
## Part (i)
| $B$ is the source (all flows out at $B$); $E$ is the sink (all flows in at $E$) | B1 | Both $B$ and $E$ (assume first answer is source); reasons not needed |
## Part (ii)
| $4+4+4+5+5 = 22$ litres per second | M1, A1 | Substantially correct using upper capacities; 22 |
## Part (iii)
| Does not partition source from sink | B1 | Source and sink are both in the same set |
## Part (iv)a
| 3 | B1 | 3 |
## Part (iv)b
| At least $3+1=4$ must flow out of $D$; 4 is the most that can flow in, so flow must be 4; at least 1 must flow along $AE \Rightarrow BA = 5$ | B1, B1 | 4 must flow out of vertex $D$; $DG=3$ and $DE=1$ at minimum |
## Part (iv)c
| At least $3+2=5$ must flow out of $I$; 5 must flow along $FI$; at least 5 must flow along $CF$; so at least $2+5=7$ must flow along $BC$ | B1, M1, A1 | 5 cao; substantially correct starting at $I$ tracing back along $IFCB$; 5 must flow along $FI$; wholly correct reasoning; $CF=5$ and $CE=2$, hence 7 |
## Part (v)
| Minimum flow: $BA=5, BC=7, BE=2$ | M1, A1 | $BA=5, BC=7, BE=2$; this flow (assume blank means zero) |
| Maximum flow: $BA=5, BC=8, BE=4$ | M1, A1 | $BA=5, BC=8, BE=4$; this flow |4 Answer parts (v) and (vi) of this question on the insert provided.
The diagram represents a system of pipes through which fluid can flow. The weights on the arcs show the lower and upper capacities of the pipes in litres per second.\\
\includegraphics[max width=\textwidth, alt={}, center]{33995efa-7ede-4e83-89d3-7b6c8be8d955-4_703_789_479_678}
\begin{enumerate}[label=(\roman*)]
\item Which vertex is the source and which vertex is the sink?
\item Cut $\alpha$ partitions the vertices into the sets $\{ A , B , C \} , \{ D , E , F , G , H , I \}$. Calculate the capacity of cut $\alpha$.
\item Explain why partitioning the vertices into sets $\{ A , D , G \} , \{ B , C , E , F , H , I \}$ does not give a cut.
\item (a) How many litres per second must flow along arc $D G$ ?\\
(b) Explain why the arc $A D$ must be at its upper capacity. Hence find the flow in $\operatorname { arc } B A$.\\
(c) Explain why at least 7 litres per second must flow along arc $B C$.
\item Use the diagrams in the insert to show a minimum feasible flow and a maximum feasible flow.
The upper capacity of $B C$ is now increased from 8 to 18 .
\item (a) Use the diagram in the insert to show a flow of 19 litres per second.\\
(b) List the saturated arcs when 19 litres per second flows through the network. Hence, or otherwise, find a cut of capacity 19 .
\item Explain how your answers to part (vi) show that 19 litres per second is the maximum flow.
\end{enumerate}
\hfill \mbox{\textit{OCR D2 2011 Q4 [18]}}