| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| Session | June |
| Marks | 18 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Lower and upper capacity networks |
| Difficulty | Challenging +1.2 This is a multi-part network flows question requiring systematic application of standard D2 algorithms (cuts, feasibility analysis, flow augmentation). While it has many parts (7 sub-questions), each involves routine application of taught procedures rather than novel problem-solving. The lower/upper capacity constraint adds mild complexity beyond basic max-flow, but students prepared for D2 would find this a straightforward bookwork-style question testing whether they can execute the standard methods correctly. |
| Spec | 7.02q Adjacency matrix: and weighted matrix representation7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| 1. What appears to be network diagram coordinates or node information (5 | 4, (3,4), E | (2,2), etc.) |
I don't see a mark scheme in the content provided. The text contains:
1. What appears to be network diagram coordinates or node information (5|4, (3,4), E|(2,2), etc.)
2. An activity table with columns for Activity, Duration (hours), and Immediate predecessors
3. Copyright and attribution information
There are no marking annotations (M1, A1, B1, DM1, etc.) or marking guidance present in this extract.
Please provide the actual mark scheme content for Question 5 that includes the marking points you'd like cleaned up.5 The network represents a system of pipes through which fluid can flow. The weights on the arcs show the lower and upper capacities for the pipes, in litres per second.\\
\includegraphics[max width=\textwidth, alt={}, center]{661c776a-9c9f-485f-b0fd-f58651e3e065-6_577_1182_351_443}\\
(i) Identify the source and explain how you know that the sink is at $G$.\\
(ii) Calculate the capacity of the cut that separates $\{ A , B , C , D , E , F \}$ from $\{ G , H , I , J , K , L \}$.\\
(iii) Assuming that a feasible flow exists, explain why arc $J G$ must be at its lower capacity. Write down the flows in arcs $H K$ and $I L$.\\
(iv) Assuming that a feasible flow exists, explain why arc HI must be at its upper capacity. Write down the flows in arcs $E H$ and $C B$.\\
(v) Show a flow of 10 litres per second through the system.\\
(vi) Using your flows from part (v), label the arrows on the diagram to show the excess capacities and the potential backflows.\\
(vii) Write down a flow augmenting path from your diagram in part (vi), but do not update the excess capacities and the potential backflows. Hence show a maximum flow through the system, and state how you know that the flow is maximal.
\hfill \mbox{\textit{OCR D2 2012 Q5 [18]}}