| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | January |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Apply labelling procedure for max flow |
| Difficulty | Moderate -0.5 This is a standard application of the max flow-min cut algorithm with a structured step-by-step format. While it requires multiple iterations of the labelling procedure, it follows a routine algorithmic process taught directly in D2 with no novel problem-solving or proof required, making it slightly easier than average. |
| 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 |
|---|---|---|
| (i) | \(4 + 2 + 4 + 0 + 5 = 15\) | M1 |
| A1 | 15 from correct calculation | |
| [2] | ||
| (ii) | Subtract 3 from \(SA, AD, DT\) and add 3 to \(TD, DA, AS\) | M1 |
| Subtract 2 from \(SB, BE, ET\) and add 2 to \(TE, EB, BS\) | M1 | Correctly adding along one of the three flow augmenting routes |
| Subtract 2 from \(SC, CF, FT\) and add 2 to \(TF, FC, CS\) | A1 | All changes correct and no other changes made |
| [3] | ||
| (iii) | eg Route \(SCET\) | B1 |
| Flow = 3 | B1 ft | Maximum extra flow on their route |
| [2] | ||
| (iv) | Maximum flow = 11 litres per second | B1 |
| Cut: \(X = \{S\}, Y = \{A,B,C,D,E,F,T\}\) | B1 | This cut described in this way |
| [2] | ||
| (v) | eg Network diagram showing flows | M1 |
| M1 | On each arc, flow \(\leq\) capacity | |
| A1 | A valid directed flow of 11 | |
| [3] |
(i) | $4 + 2 + 4 + 0 + 5 = 15$ | M1 | At least four correct terms |
| | | A1 | 15 from correct calculation |
| | | [2] | |
(ii) | Subtract 3 from $SA, AD, DT$ and add 3 to $TD, DA, AS$ | M1 | Correctly subtracting along one of the three flow augmenting routes |
| | Subtract 2 from $SB, BE, ET$ and add 2 to $TE, EB, BS$ | M1 | Correctly adding along one of the three flow augmenting routes |
| | Subtract 2 from $SC, CF, FT$ and add 2 to $TF, FC, CS$ | A1 | All changes correct and no other changes made |
| | | [3] | |
(iii) | eg Route $SCET$ | B1 | Any valid flow augmenting route (not ft) |
| | Flow = 3 | B1 ft | Maximum extra flow on their route |
| | | [2] | |
(iv) | Maximum flow = 11 litres per second | B1 | 11 with units |
| | Cut: $X = \{S\}, Y = \{A,B,C,D,E,F,T\}$ | B1 | This cut described in this way |
| | | [2] | |
(v) | eg Network diagram showing flows | M1 | At each vertex, flow in = flow out |
| | | M1 | On each arc, flow $\leq$ capacity |
| | | A1 | A valid directed flow of 11 |
| | | [3] | |
---5 (i) Capacity = $\_\_\_\_$\\
(ii)\\
\includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_671_997_456_614}\\
(iii) Route: $\_\_\_\_$ Flow $=$ $\_\_\_\_$\\
(iv) Maximum flow = $\_\_\_\_$\\
Cut: $\mathrm { X } = \{$\\
\} $\quad \mathrm { Y } = \{$\\
(v)\\
\includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_659_995_1774_616}
\hfill \mbox{\textit{OCR D2 2007 Q5 [12]}}