| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | January |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Explain capacity/flow constraints |
| Difficulty | Standard +0.3 This is a standard network flows question testing routine application of cut capacity calculations and max-flow min-cut theorem. Part (i) is direct calculation, parts (ii)-(iii) require understanding of flow constraints (standard D2 content), and part (iv) applies the well-rehearsed max-flow min-cut theorem. While multi-part with several marks, it requires no novel insight—just systematic application of taught algorithms and concepts. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02p Networks: weighted graphs, modelling connections7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| \(6+3+2+4 = 15\) litres per second | B1 | For 15 |
| Answer | Marks | Guidance |
|---|---|---|
| \(6+2+3+6+2+2 = 21\) litres per second | M1 | For showing how 21 (given) was worked out |
| Answer | Marks | Guidance |
|---|---|---|
| Do not use arc \(DG\) as it is crossed twice or \(X = \{S,A,B,C,E,F\}\) \(Y = \{D,G,H,I,T\}\) | A1 | For explaining why arc \(DG\) is not used |
| \(SC\) cannot be full since the most that can leave it is \(2+4 = 6\) litres per second | B1 | For 6 and 'out' or equivalent |
| \(AD\) cannot be full since the most that can enter it is \(2+3 = 5\) litres per second | B1 | For 5 and 'in' or equivalent |
| The most that can flow in \(SB\) is \(2+3 = 5\) litres per second | B1 | For \(SB = 5\) |
| Answer | Marks | Guidance |
|---|---|---|
| Arc | A | B |
| Flow | 5 | 5 |
| Arc | S | T |
| Flow | 6 | 2 |
| Arc | I | J |
| Flow | 2 | 2 |
| M1 | For a feasible flow | |
| A1 | For a feasible flow of 14 litres per second (directions must be shown for the A mark) |
| Answer | Marks | Guidance |
|---|---|---|
| M1 | For this cut described or drawn on diagram | |
| A1 | For explicitly stating that this cut \(= 14\) | |
| Maximum flow \(\geq\) this flow \(= 14\); Minimum cut \(\leq\) this cut \(= 14\). But maximum flow \(=\) minimum cut, so 14 is the maximum flow and the minimum cut. | B1 | For explaining how maximum flow \(=\) minimum cut shows that 14 is the maximum here (at least referring to 'this flow' and 'this cut', not just stating 'max flow \(=\) min cut') |
**(i)**
$6+3+2+4 = 15$ litres per second | B1 | For 15
**(ii)**
$6+2+3+6+2+2 = 21$ litres per second | M1 | For showing how 21 (given) was worked out
**(iii)**
Do not use arc $DG$ as it is crossed twice or $X = \{S,A,B,C,E,F\}$ $Y = \{D,G,H,I,T\}$ | A1 | For explaining why arc $DG$ is not used
$SC$ cannot be full since the most that can leave it is $2+4 = 6$ litres per second | B1 | For 6 and 'out' or equivalent
$AD$ cannot be full since the most that can enter it is $2+3 = 5$ litres per second | B1 | For 5 and 'in' or equivalent
The most that can flow in $SB$ is $2+3 = 5$ litres per second | B1 | For $SB = 5$
**(iv)**
Maximum flow $= 14$ litres per second, for example:
| Arc | A | B | C | D | E | F | G |
|-----|---|---|---|---|---|---|---|
| Flow | 5 | 5 | 3 | 5 | 5 | 5 | 5 |
| Arc | S | T | B | C |
|-----|---|---|---|---|
| Flow | 6 | 2 | 4 | 2 |
| Arc | I | J |
|-----|---|---|
| Flow | 2 | 2 |
| M1 | For a feasible flow
| A1 | For a feasible flow of 14 litres per second (directions must be shown for the A mark)
---
**Cut:** $X = \{S,B,C\}$ $Y = \{A,D,E,F,G,H,I,T\}$. This cut has capacity 14 litres per second.
| M1 | For this cut described or drawn on diagram
| A1 | For explicitly stating that this cut $= 14$
Maximum flow $\geq$ this flow $= 14$; Minimum cut $\leq$ this cut $= 14$. But maximum flow $=$ minimum cut, so 14 is the maximum flow and the minimum cut. | B1 | For explaining how maximum flow $=$ minimum cut shows that 14 is the maximum here (at least referring to 'this flow' and 'this cut', not just stating 'max flow $=$ min cut')
---3 The network represents a system of pipes along which fluid can flow from $S$ to $T$. The values on the arcs are the capacities in litres per second.\\
\includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_634_1112_404_484}\\
(i) Calculate the capacity of the cut with $\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}$.\\
(ii) Explain why the capacity of the cut $\alpha$, shown on the diagram, is only 21 litres per second.\\
(iii) Explain why neither of the arcs $S C$ and $A D$ can be full to capacity. Give the maximum flow in $\operatorname { arc } S B$.\\
(iv) Find the maximum flow through the system and draw a diagram to show a way in which this can be achieved. Show that your flow is maximal by using the maximum flow-minimum cut theorem.
\hfill \mbox{\textit{OCR D2 2006 Q3 [12]}}