| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2005 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Moderate -0.8 This is a routine application of the labelling procedure for max flow problems. Part (i) is direct identification of cut arcs, (ii)-(iii) are standard bookwork applying the algorithm mechanically, and (iv)-(v) apply the max-flow min-cut theorem. While multi-part, each step follows textbook procedures with no novel problem-solving required. |
| Spec | 7.02q Adjacency matrix: and weighted matrix representation7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(AD, EB, CF\) | B1 | For these three directed arcs and no others |
| \(8 + 2 + 7 = 17\) litres per second | M1 | \(8 + 7 + 0\) or \(8 + 7 - 2\) seen \(\Rightarrow\) M1, A0 |
| A1 | For 17 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct diagram with flow/capacity labels | M1 | Accept all arrows reversed |
| A1 | For no more than three errors | |
| A1 | For a correct labelling |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(SCEBDT\) | B1 | For this path only |
| Correct labelled diagram | B1 | For a correct labelling |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Cut \(\{S, A, B, C, D, E, F\}\ \{T\} = 13\) | B1 | For this cut or the cut \(\{S\}\ \{A, B, C, D, E, F, T\}\), in any form, or 'no more can flow into \(T\)', or 'no more can flow out of \(S\)', or equivalent |
| Diagram in (iii) shows a flow of 13 litres/second | B1 | For flow shown \(= 13\) or max flow \(\geq 13 \geq\) min cut (but NOT just stating max flow \(=\) min cut). Value 13 given in question |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct flow diagram shown | B1 | For showing this flow, or excess capacities and potential backflows equivalent to this |
| Max flow is 11 litres per second | B1 | For 11 litres per second (with units) |
| Cut \(\{S, C, E, F\}\ \{A, B, D, T\} = 11\) | B1 | For cut or a convincing explanation in words |
# Question 1:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| $AD, EB, CF$ | B1 | For these three directed arcs and no others |
| $8 + 2 + 7 = 17$ litres per second | M1 | $8 + 7 + 0$ or $8 + 7 - 2$ seen $\Rightarrow$ M1, A0 |
| | A1 | For 17 |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct diagram with flow/capacity labels | M1 | Accept all arrows reversed |
| | A1 | For no more than three errors |
| | A1 | For a correct labelling |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| $SCEBDT$ | B1 | For this path only |
| Correct labelled diagram | B1 | For a correct labelling |
## Part (iv)
| Answer | Mark | Guidance |
|--------|------|----------|
| Cut $\{S, A, B, C, D, E, F\}\ \{T\} = 13$ | B1 | For this cut or the cut $\{S\}\ \{A, B, C, D, E, F, T\}$, in any form, or 'no more can flow into $T$', or 'no more can flow out of $S$', or equivalent |
| Diagram in (iii) shows a flow of 13 litres/second | B1 | For flow shown $= 13$ or max flow $\geq 13 \geq$ min cut (but NOT just stating max flow $=$ min cut). Value 13 given in question |
## Part (v)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct flow diagram shown | B1 | For showing this flow, or excess capacities and potential backflows equivalent to this |
| Max flow is 11 litres per second | B1 | For 11 litres per second (with units) |
| Cut $\{S, C, E, F\}\ \{A, B, D, T\} = 11$ | B1 | For cut or a convincing explanation in words |
---1 [Answer this question on the insert provided.]\\
The network below represents a system of pipelines through which fluid flows from $S$ to $T$. The capacities of the pipelines, in litres per second, are shown as weights on the arcs.\\
\includegraphics[max width=\textwidth, alt={}, center]{0403a37e-46dd-4346-afc6-e48a34417c48-2_863_1201_486_477}\\
(i) Write down the arcs from $\{ S , A , C , E \}$ to $\{ B , D , F , T \}$. Hence find the capacity of the cut that separates $\{ S , A , C , E \}$ from $\{ B , D , F , T \}$.\\
(ii) On the diagram in the insert show the excess capacities and potential backflows when 5 litres per second flow along SADT and 6 litres per second flow along SCFT.\\
(iii) Give a flow-augmenting path of capacity 2 . On the second diagram in the insert show the new capacities and potential backflows.\\
(iv) Use the maximum flow - minimum cut theorem to show that the maximum flow from $S$ to $T$ is 13 litres per second.\\
(v) $E B$ is replaced by a pipeline with capacity 2 litres per second from $B$ to $E$. Find the new maximum flow from $S$ to $T$. You should show the flow on the third diagram in the insert and explain how you know that this is a maximum.
\hfill \mbox{\textit{OCR D2 2005 Q1 [12]}}