| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2004 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Calculate cut capacity |
| Difficulty | Standard +0.3 This is a standard max-flow min-cut theorem application from D2. Part (a) requires reading capacities across given cuts (straightforward arithmetic), part (b) applies the theorem directly (if flow equals minimum cut capacity, flow is maximal), and part (c) requires checking which new arc increases the minimum cut capacity. All steps are routine algorithmic procedures with no novel problem-solving required, making it slightly easier than average A-level difficulty. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(C_1 = 7 + 14 + 0 + 14 = 35\), \(C_2 = 7 + 14 + 5 = 26\), \(C_3 = 8 + 9 + 6 + 8 = 31\) | B1, B1, B1 | 3 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Either Min cut = Max flow and we have a flow of 26 and a cut of 26 or C2 is through saturated arcs | B1 | 1 mark |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Using EJ (capacity 5) e.g. will increase flow by 1– ie increase it to 27 since only one more unit can leave E. - BEJL - 1. Using FH (capacity 3) e.g. - will increase flow by 2 – ie increase it to 28 since only two more units can leave F. - BFHJL - 2. Thus choose option 2 add FH capacity 3. | M1, A1, A1 | 3 marks |
### (a)
**Answer:** $C_1 = 7 + 14 + 0 + 14 = 35$, $C_2 = 7 + 14 + 5 = 26$, $C_3 = 8 + 9 + 6 + 8 = 31$ | B1, B1, B1 | 3 marks
### (b)
**Answer:** Either Min cut = Max flow and we have a flow of 26 and a cut of 26 or C2 is through saturated arcs | B1 | 1 mark
### (c)
**Answer:** Using EJ (capacity 5) e.g. will increase flow by 1– ie increase it to 27 since only one more unit can leave E. - BEJL - 1. Using FH (capacity 3) e.g. - will increase flow by 2 – ie increase it to 28 since only two more units can leave F. - BFHJL - 2. Thus choose option 2 add FH capacity 3. | M1, A1, A1 | 3 marks
---\includegraphics{figure_5}
The diagram above shows a network of roads represented by arcs. The capacity of the road represented by that arc is shown on each arc. The numbers in circles represent a possible flow of 26 from $B$ to $L$.
Three cuts $C_1$, $C_2$ and $C_3$ are shown on The diagram above.
\begin{enumerate}[label=(\alph*)]
\item Find the capacity of each of the three cuts. [3]
\item Verify that the flow of 26 is maximal. [1]
\end{enumerate}
The government aims to maximise the possible flow from $B$ to $L$ by using one of two options.
Option 1: Build a new road from $E$ to $J$ with capacity 5.
\textbf{or}
Option 2: Build a new road from $F$ to $H$ with capacity 3.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item By considering both options, explain which one meets the government's aim [3]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2004 Q9 [7]}}