| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | January |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Vertex restrictions in networks |
| Difficulty | Challenging +1.2 This is a multi-part network flows question requiring understanding of cuts, capacity constraints, and vertex restrictions. Parts (i)-(iii) involve standard cut calculations and logical reasoning about flow constraints. Part (iv) requires applying feasibility conditions and the max-flow min-cut theorem. Part (v) involves redrawing the network with vertex splitting and finding a specific flow. While it has many parts (5 marks worth), each individual step uses standard D2 techniques without requiring novel insight—slightly above average due to the logical reasoning required in parts (ii)-(iv) and the vertex restriction modification. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(\alpha = 12\) litres per second | B1 | 12 |
| \(\beta = 15\) litres per second | B1 | 15 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| At least 3 litres per second must flow into \(A\), so \(AC\) and \(AF\) cannot both have flows of 1 | B1 | At least 3 flows along \(SA\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| At most 4 litres per second can flow into \(B\), and at least 4 must flow out, so \(BC\) and \(BD\) must have flows of 2 | B1 | At \(B\): flow in \(\leq 4\) (and flow out \(\geq 4\)) hence given flows in \(BC\) and \(BD\) |
| Hence only 2 litres per second flows into \(D\); at least 2 litres per second must flow out, so \(DE\) and \(DT\) must both be at lower capacities | B1 | Stating that flow into \(D\) is 2 and hence given flows in \(DE\) and \(DT\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Flow across \(\{S,A,B,C\}, \{D,E,F,G,T\} \geq 11\) (so 10 litres per second is impossible) | M1, A1 | Or any equivalent reasoning (e.g. flow through \(C\)); wholly convincing argument |
| Minimum \(= 11\) (with example flow shown) | M1, A1 | 11; showing that 11 is possible (check \(C\)) |
| Maximum \(= 12\); no more than 12 can cross cut \(\alpha\) and 12 is possible, e.g. augment flow by 1 litre per second along \(SAFT\) | M1, A1 | 12; showing that 12 is possible but 13 is not |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| A correct reduced network (vertex \(E\) and all arcs incident on \(E\) deleted), including arc capacities; or putting \(E_{\text{in}}\) and \(E_{\text{out}}\) with capacity 0 between them; or giving \(CE\), \(EG\) and \(DE\) upper and lower capacities of 0 | B1 | |
| On same or new diagram: \(SA=3,\ SC=2,\ SB=4,\ BC=2,\ BT=2\) (and nothing through \(E\)) | M1 | |
| A valid flow of 9 litres per second through the network | A1 |
# Question 6:
## Part (i)
| Answer/Working | Mark | Guidance |
|---|---|---|
| $\alpha = 12$ litres per second | B1 | 12 |
| $\beta = 15$ litres per second | B1 | 15 |
## Part (ii)
| Answer/Working | Mark | Guidance |
|---|---|---|
| At least 3 litres per second must flow into $A$, so $AC$ and $AF$ cannot both have flows of 1 | B1 | At least 3 flows along $SA$ |
## Part (iii)
| Answer/Working | Mark | Guidance |
|---|---|---|
| At most 4 litres per second can flow into $B$, and at least 4 must flow out, so $BC$ and $BD$ must have flows of 2 | B1 | At $B$: flow in $\leq 4$ (and flow out $\geq 4$) hence given flows in $BC$ and $BD$ |
| Hence only 2 litres per second flows into $D$; at least 2 litres per second must flow out, so $DE$ and $DT$ must both be at lower capacities | B1 | Stating that flow into $D$ is 2 and hence given flows in $DE$ and $DT$ |
## Part (iv)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Flow across $\{S,A,B,C\}, \{D,E,F,G,T\} \geq 11$ (so 10 litres per second is impossible) | M1, A1 | Or any equivalent reasoning (e.g. flow through $C$); wholly convincing argument |
| Minimum $= 11$ (with example flow shown) | M1, A1 | 11; showing that 11 is possible (check $C$) |
| Maximum $= 12$; no more than 12 can cross cut $\alpha$ and 12 is possible, e.g. augment flow by 1 litre per second along $SAFT$ | M1, A1 | 12; showing that 12 is possible but 13 is not |
## Part (v)
| Answer/Working | Mark | Guidance |
|---|---|---|
| A correct reduced network (vertex $E$ and all arcs incident on $E$ deleted), including arc capacities; or putting $E_{\text{in}}$ and $E_{\text{out}}$ with capacity 0 between them; or giving $CE$, $EG$ and $DE$ upper and lower capacities of 0 | B1 | |
| On same or new diagram: $SA=3,\ SC=2,\ SB=4,\ BC=2,\ BT=2$ (and nothing through $E$) | M1 | |
| A valid flow of 9 litres per second through the network | A1 | |6 The diagram represents a system of pipes through which fluid can flow from a source, $S$, to a sink, $T$. It also shows two cuts, $\alpha$ and $\beta$. The weights on the arcs show the lower and upper capacities of the pipes in litres per second.\\
\includegraphics[max width=\textwidth, alt={}, center]{1ceb5585-6d3f-4723-ad49-7addfb40ab66-6_818_1285_434_429}\\
(i) Calculate the capacities of the cuts $\alpha$ and $\beta$.\\
(ii) Explain why the arcs $A C$ and $A F$ cannot both be at their lower capacities.\\
(iii) Explain why the $\operatorname { arcs } B C , B D , D E$ and $D T$ must all be at their lower capacities.\\
(iv) Show that a flow of 10 litres per second is impossible. Deduce the minimum and maximum feasible flows, showing your working.
Vertex $E$ becomes blocked so that no fluid can flow through it.\\
(v) Draw a copy of the network with this vertex restriction. You are advised to make your diagram quite large. Show a flow of 9 litres per second on your diagram.
\hfill \mbox{\textit{OCR D2 2010 Q6 [14]}}