| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Calculate cut capacity |
| Difficulty | Moderate -0.3 This is a standard D1 network flows question testing routine application of the max-flow min-cut algorithm. Parts (a) and (b) require simple reading/addition from the diagram, part (c) is mechanical application of the labelling procedure following given labels, and part (d) requires stating that flow equals cut capacity. While it's a 10-mark question requiring multiple steps, all techniques are algorithmic with no problem-solving insight needed, making it slightly easier than average. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks |
|---|---|
| B1 |
| Answer | Marks |
|---|---|
| B1, B1 (2) |
| Answer | Marks |
|---|---|
| m1 A1 / A1 / A1 / A1 (5) |
| Answer | Marks |
|---|---|
| m1 a1 (2) |
## (a)
SS
| B1 |
## (b)
$C_1 = 14.0$, $C_z = 10.4$
| B1, B1 (2) |
## (c)
e.g.
$S \& D F H J T - 4$
$S \& D F G T - 1$
$S \& D F C H J T - 2$
$S \& D F C H J T - 2$
$S \& D G - 10$
| m1 A1 / A1 / A1 / A1 (5) |
## (d)
max flow - min cut theorem, flow is 10k, mincst is $C_2$
| m1 a1 (2) |\includegraphics{figure_6}
Figure 6 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.
\begin{enumerate}[label=(\alph*)]
\item State the value of the initial flow. [1]
\item State the capacities of cuts $C_1$ and $C_2$. [2]
\end{enumerate}
Diagram 3 in the answer book shows the labelling procedure applied to the above network.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item Using Diagram 3, increase the flow by a further 19 units. You must list each flow-augmenting path you use, together with its flow. [5]
\item Prove that the flow is now maximal. [2]
\end{enumerate}
(Total 10 marks)
\hfill \mbox{\textit{Edexcel D1 2007 Q8 [10]}}