| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2004 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Find missing flow values |
| Difficulty | Moderate -0.5 This is a standard max-flow min-cut algorithm question requiring straightforward application of the labelling procedure. While it has multiple parts and 13 marks, it follows a routine template: identify flows, apply the augmenting path algorithm, and verify with min-cut theorem. The techniques are algorithmic rather than requiring problem-solving insight, making it slightly easier than average despite being a longer question. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(x = 9\), \(y = 16\) | B1 B1 | 2 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Initial flow = 53 – Either finds a flow-augmenting route or demonstrates not enough saturated arcs for a minimum cut | B1 B1 | 2 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: [Network diagram with flow values] | M1A1 | 2 marks |
| Answer | Marks | Guidance |
|---|---|---|
| (IFDA – 2, max flow – 64) | A1, B1 | 3 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: [Network diagram showing minimum cut] | M1 A1 | 2 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Max flow – min cut. Finds a cut GC, AF, DF, DJ, EI, EH value 64. Note: must not use supersource or supersink arcs. | M1, A1 | 2 marks |
### (a)
**Answer:** $x = 9$, $y = 16$ | B1 B1 | 2 marks
### (b)
**Answer:** Initial flow = 53 – Either finds a flow-augmenting route or demonstrates not enough saturated arcs for a minimum cut | B1 B1 | 2 marks
### (c)
**Answer:** [Network diagram with flow values] | M1A1 | 2 marks
(e.g. IDA – 9)
(IFDA – 2, max flow – 64) | A1, B1 | 3 marks
### (d)
**Answer:** [Network diagram showing minimum cut] | M1 A1 | 2 marks
(e.g. cuts: C, 9, 11, 14, 6, 4 with annotations for 20, 0, 25, 0, etc.)
### (e)
**Answer:** Max flow – min cut. Finds a cut GC, AF, DF, DJ, EI, EH value 64. Note: must not use supersource or supersink arcs. | M1, A1 | 2 marks
---\includegraphics{figure_1}
Figure 1 shows a capacitated directed network. The number on each arc is its capacity.
\includegraphics{figure_2}
Figure 2 shows a feasible initial flow through the same network.
\begin{enumerate}[label=(\alph*)]
\item Write down the values of the flow $x$ and the flow $y$. [2]
\item Obtain the value of the initial flow through the network, and explain how you know it is not maximal. [2]
\item Use this initial flow and the labelling procedure on Diagram 1 below to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
\textbf{Diagram 1}
\includegraphics{figure_3} [5]
\item Show your maximal flow pattern on Diagram 2.
\textbf{Diagram 2}
\includegraphics{figure_4} [2]
\item Prove that your flow is maximal. [2]
\end{enumerate}
(Total 13 marks)
\hfill \mbox{\textit{Edexcel D2 2004 Q7 [13]}}