| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Moderate -0.3 This is a standard max-flow min-cut algorithm question requiring routine application of the labelling procedure. While it has multiple parts and 14 marks, each step follows a well-defined algorithmic process taught in D2 with no novel problem-solving required—students simply execute the learned procedure and verify using the max-flow min-cut theorem. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(C_1 = 103\), \(C_2 = 177\), flow = 76 | B1, B1, B1 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: [Diagrams showing various paths] | M1 A1 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: e.g. S B C D T – 6, S B C D E T – 1, S B A C D E T – 15, Max flow is 98 | M1 A3,2,1,0 | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: [Diagram showing flow network with values] | M1 A1 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Maximum flow = minimum cut. Cut through AD, AC, BC and BE | M1 A1 | 2 |
## Part (a)
**Answer:** $C_1 = 103$, $C_2 = 177$, flow = 76 | B1, B1, B1 | 3
## Part (b)
**Answer:** [Diagrams showing various paths] | M1 A1 | 2
## Part (c)
**Answer:** e.g. S B C D T – 6, S B C D E T – 1, S B A C D E T – 15, Max flow is 98 | M1 A3,2,1,0 | B1 | 5
## Part (d)
**Answer:** [Diagram showing flow network with values] | M1 A1 | 2
## Part (e)
**Answer:** Maximum flow = minimum cut. Cut through AD, AC, BC and BE | M1 A1 | 2\includegraphics{figure_9}
The figure above shows a capacitated, directed network. The capacity of each arc is shown on each arc. The numbers in circles represent an initial flow from $S$ to $T$.
Two cuts $C_1$ and $C_2$ are shown on the figure.
\begin{enumerate}[label=(\alph*)]
\item Write down the capacity of each of the two cuts and the value of the initial flow. [3]
\item Complete the initialisation of the labelling procedure on the diagram below by entering values along arcs $AC$, $CD$, $DE$ and $DT$.
\includegraphics{figure_9b}
[2]
\item Hence use the labelling procedure to find a maximal flow through the network. You must list each flow-augmenting path you use, together with its flow. [5]
\item Show your maximal flow pattern on the diagram below.
\includegraphics{figure_9d}
[2]
\item Prove that your flow is maximal. [2]
\end{enumerate}
(Total 14 marks)
\hfill \mbox{\textit{Edexcel D2 2006 Q9 [14]}}