| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | June |
| Marks | 14 |
| 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 the max-flow min-cut algorithm with clear scaffolding. Parts (a)-(d) involve routine application of the labelling procedure following a given initial flow, requiring only careful bookkeeping. Part (e) asks for proof via max-flow min-cut theorem, which is a standard result. While multi-step with 14 marks total, it's methodical rather than conceptually challenging—slightly easier than average A-level maths due to the algorithmic nature and heavy guidance. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks |
|---|---|
| (a) \(c_1 = 103\), \(c_2 = 177\), Slack = 76 | B1, B1, B1(3) |
| (b) [Network diagram with labels: A connected to nodes with various weights and degrees] | m1 A1(2) |
| (c) e.g. \(SBCDT - 6\); \(SBCDET - 1\); \(SBACDET - 15\); max flow is 98 | m1 A3,2,1,0(5) |
| (d) [Network diagram showing flow values on edges with maximum flow = minimum cut interpretation] | m1 A1(2) |
| (e) Maximum flow = minimum cut; cut through AD, AC, BC and BE | m1 A1(2) |
(a) $c_1 = 103$, $c_2 = 177$, Slack = 76 | B1, B1, B1(3)
(b) [Network diagram with labels: A connected to nodes with various weights and degrees] | m1 A1(2)
(c) e.g. $SBCDT - 6$; $SBCDET - 1$; $SBACDET - 15$; max flow is 98 | m1 A3,2,1,0(5)
(d) [Network diagram showing flow values on edges with maximum flow = minimum cut interpretation] | m1 A1(2)
(e) Maximum flow = minimum cut; cut through AD, AC, BC and BE | m1 A1(2)
---
## Summary of Mark Types Used
- **m1**: Method mark (one mark)
- **m**: Method
- **A1**: Accuracy mark (one mark)
- **A**: Answer/Accuracy
- **B1, B2**: Independent marks
- **B2,1,0**: Graduated mark scheme (2, 1, or 0)
- **A1(L1)**: Accuracy mark on same line, level 1
- **DM1**: Dependent method mark
- **cao**: Correct answer only
- **c.a.o**: Correct answer only\includegraphics{figure_5}
Figure 5 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 Figure 5.
\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 Diagram 1 by entering values along arcs AC, CD, DE and DT. [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 Diagram 2. [2]
\item Prove that your flow is maximal. [2]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2006 Q7 [14]}}