| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Moderate -0.5 This is a standard network flows question testing basic concepts: reading flow from a diagram, understanding capacity notation, calculating cut capacity, and applying the labelling procedure. While it requires multiple steps, each part follows routine D2 algorithms with no novel problem-solving. Slightly easier than average A-level due to being methodical application of learned procedures rather than requiring mathematical insight. |
| Spec | 7.02p Networks: weighted graphs, modelling connections |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(S - E - I - T\) | B1 | For this route (not in reverse) cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 6 litres per second | B1 | For 6 |
| From \(A\) to \(G\) | B1 | For direction \(AG\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(6 + 2 + 4 + 0 + 8 = 20\) litres per second | M1 | For a substantially correct attempt with \(DF = 0\) |
| M1 | For dealing with \(EI\) (\(= 8\) or \(= 2 + 6\)) | |
| A1 | For 20 cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. flow 5 along \(S-A-G-T\) and 2 along \(S-C-F-H-G-T\) | M1 | For describing a valid flow augmenting route |
| A1 | For correctly flowing 7 from \(S\) to \(T\) | |
| Diagram correctly augmented | M1 | For a reasonable attempt at augmenting a flow |
| M1 | For correctly augmenting a flow | |
| A1 | For a correct augmentation by a total of 7 | |
| Cut \(\{S,A,B,C,D,E,F,G,H,I\}, \{T\}\) | B1 | For identifying cut or arcs \(GT\) and \(IT\) |
| This cut has a value of 13 and the flow already found is \(6+7=13\) litres per second. OR: The arcs \(GT\) and \(IT\) are both saturated, so no more can flow into \(T\) | B1 | For explaining how this shows that the flow is a maximum, but NOT just stating max flow = min cut |
# Question 5:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $S - E - I - T$ | B1 | For this route (not in reverse) cao |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 6 litres per second | B1 | For 6 |
| From $A$ to $G$ | B1 | For direction $AG$ |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $6 + 2 + 4 + 0 + 8 = 20$ litres per second | M1 | For a substantially correct attempt with $DF = 0$ |
| | M1 | For dealing with $EI$ ($= 8$ or $= 2 + 6$) |
| | A1 | For 20 cao |
## Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. flow 5 along $S-A-G-T$ and 2 along $S-C-F-H-G-T$ | M1 | For describing a valid flow augmenting route |
| | A1 | For correctly flowing 7 from $S$ to $T$ |
| Diagram correctly augmented | M1 | For a reasonable attempt at augmenting a flow |
| | M1 | For correctly augmenting a flow |
| | A1 | For a correct augmentation by a total of 7 |
| Cut $\{S,A,B,C,D,E,F,G,H,I\}, \{T\}$ | B1 | For identifying cut or arcs $GT$ and $IT$ |
| This cut has a value of 13 and the flow already found is $6+7=13$ litres per second. OR: The arcs $GT$ and $IT$ are both saturated, so no more can flow into $T$ | B1 | For explaining how this shows that the flow is a maximum, but NOT just stating max flow = min cut |5 Answer this question on the insert provided.
The network represents a system of pipes through which fluid can flow from a source, S , to a sink, T .\\
\includegraphics[max width=\textwidth, alt={}, center]{09d4aacd-026b-4d81-a826-3d3f29f9c105-5_1310_1301_447_424}
The arrows are labelled to show excess capacities and potential backflows (how much more and how much less could flow in each pipe). The excess capacities and potential backflows are measured in litres per second. Currently the flow is 6 litres per second, all flowing along a single route through the system.\\
(i) Write down the route of the 6 litres per second that is flowing from $S$ to $T$.\\
(ii) What is the capacity of the pipe AG and in which direction can fluid flow along this pipe?\\
(iii) Calculate the capacity of the $\operatorname { cut } \mathrm { X } = \{ \mathrm { S } , \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } \} , \mathrm { Y } = \{ \mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { I } , \mathrm { T } \}$.\\
(iv) Describe how a further 7 litres per second can flow from S to T and update the labels on the arrows to show your flow. Explain how you know that this is the maximum flow.
{}\\
\hfill \mbox{\textit{OCR D2 2007 Q5 [13]}}