| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Lower and upper capacity networks |
| Difficulty | Standard +0.3 This is a standard D2 network flows question testing routine application of cut capacity calculations and lower/upper capacity constraints. While it requires multiple parts and careful bookkeeping with lower bounds, the techniques are algorithmic and well-practiced. The conceptual demand is modest—no novel insights or proof techniques beyond textbook methods are needed. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| (i) \(4+4+8+7+6 = 29\) litres per second | B1 | For 29 |
| (ii) \(4-1-2+3+3+5 = 12\) litres per second | M1, A1 | For using upper and lower capacities correctly; For showing how 12 (given) was worked out |
| Answer | Marks | Guidance |
|---|---|---|
| So minimum flow across cut = 0 | A1, [4] | For a substantially correct calculation; For 0, from an appropriate calculation |
| (iii) Flow in arc \(CE \geq 2\) and flow in arc \(CF \geq 3\), so at least 5 litres per second must flow into \(C\) | M1, A1 | For any reasonable attempt (eg \(CE = 2, CF = 3\)); For correct reasoning |
| At most 4 litres per second flow into \(A\), of which at least 1 flows out to \(B\) and 2 flow out to \(E\), so at most 1 litre per second can flow along \(AD\) | M1, A1, [4] | For identifying \(< 4\) in and \(> 3\) out or equivalent; For a correct conclusion |
| (iv) Either a diagram or a description of a flow of 11 litres per second. Arcs \(AD, AE, BE, CE, CF\) must all be at their minimum capacities. | M1, A1, A1, [3] | For a flow of 11 litres per second from \(S\) to \(T\); Flow satisfies all lower capacities; Flow satisfies all upper capacities |
| (v) \(11 \leq \text{maximum flow} \leq 12\) | B1, B1, [2] | 11 as lower bound; 12 as upper bound (max flow = 12 ⟹ B0, B1) |
(i) $4+4+8+7+6 = 29$ litres per second | B1 | For 29
(ii) $4-1-2+3+3+5 = 12$ litres per second | M1, A1 | For using upper and lower capacities correctly; For showing how 12 (given) was worked out
$0 - 5 - 4 + 3 + 0 + 5 = -1$
So minimum flow across cut = 0 | A1, [4] | For a substantially correct calculation; For 0, from an appropriate calculation
(iii) Flow in arc $CE \geq 2$ and flow in arc $CF \geq 3$, so at least 5 litres per second must flow into $C$ | M1, A1 | For any reasonable attempt (eg $CE = 2, CF = 3$); For correct reasoning
At most 4 litres per second flow into $A$, of which at least 1 flows out to $B$ and 2 flow out to $E$, so at most 1 litre per second can flow along $AD$ | M1, A1, [4] | For identifying $< 4$ in and $> 3$ out or equivalent; For a correct conclusion
(iv) Either a diagram or a description of a flow of 11 litres per second. Arcs $AD, AE, BE, CE, CF$ must all be at their minimum capacities. | M1, A1, A1, [3] | For a flow of 11 litres per second from $S$ to $T$; Flow satisfies all lower capacities; Flow satisfies all upper capacities
(v) $11 \leq \text{maximum flow} \leq 12$ | B1, B1, [2] | 11 as lower bound; 12 as upper bound (max flow = 12 ⟹ B0, B1)
---1 The network represents a system of pipes along which fluid can flow from $S$ to $T$. The values on the arcs are lower and upper capacities in litres per second.\\
\includegraphics[max width=\textwidth, alt={}, center]{e879b1f5-edc7-4819-80be-2a90dbf3d451-02_696_1292_376_424}\\
(i) Calculate the capacity of the cut with $\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}$.\\
(ii) Show that the capacity of the cut $\alpha$, shown on the diagram, is 12 litres per second and calculate the minimum flow across the cut $\alpha$, from $S$ to $T$, (without regard to the remainder of the diagram).\\
(iii) Explain why the arc SC must have at least 5 litres per second flowing through it. By considering the flow through $A$, explain why $A D$ cannot be full to capacity.\\
(iv) Show that it is possible for 11 litres per second to flow through the system.\\
(v) From your previous answers, what can be deduced about the maximum flow through the system?
\hfill \mbox{\textit{OCR D2 2006 Q1 [14]}}