| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | State maximum flow along specific routes |
| Difficulty | Moderate -0.8 This is a standard textbook application of the max-flow min-cut algorithm with clear step-by-step instructions. Parts (a)-(b) involve simple path identification, part (c) applies the labelling procedure mechanically, and the proof in (c)(iii) requires stating a standard result (max-flow = min-cut). While multi-part with 14 marks total, it requires only routine application of a well-defined algorithm with no novel problem-solving or insight. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| S ∩ D T − 8 | S ⊆ E T − 11 | S ⊆ F T − 9 |
| Answer | Marks |
|---|---|
| Diagram showing network with flows labeled | B1 (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Examples: \(SACDT - 2\), \(SCEFT - 6\), \(SCEFT - 1\), \(SACFT - 1\) | M1 A1 A1 (2) | Maximum flow = 6 |
| Answer | Marks |
|---|---|
| Network diagram with flow values labeled, e.g., A→D: 8, D→T: 10 | M1 A1 (2) |
| Answer | Marks |
|---|---|
| Maximum flow-minimum cut theorem: Cut \(\{SACEF\}\{BDFT\}\) | M1 A2, 0 (3) |
| Answer | Marks |
|---|---|
| Idea of directed flow through system of arcs from S ⊆ T | B1 (1) |
## Part (a)
S ∩ D T − 8 | S ⊆ E T − 11 | S ⊆ F T − 9 | 8, 2, 1, 0
## Part (b)
Diagram showing network with flows labeled | B1 (3)
## Part (c)
### Part (i)
Examples: $SACDT - 2$, $SCEFT - 6$, $SCEFT - 1$, $SACFT - 1$ | M1 A1 A1 (2) | Maximum flow = 6
### Part (ii)
Network diagram with flow values labeled, e.g., A→D: 8, D→T: 10 | M1 A1 (2)
### Part (iii)
Maximum flow-minimum cut theorem: Cut $\{SACEF\}\{BDFT\}$ | M1 A2, 0 (3)
## Part (d)
Idea of directed flow through system of arcs from S ⊆ T | B1 (1)
---\includegraphics{figure_4}
Figure 4 shows a capacitated directed network. The number on each arc is its capacity.
\begin{enumerate}[label=(\alph*)]
\item State the maximum flow along
\begin{enumerate}[label=(\roman*)]
\item $SADT$,
\item $SCET$,
\item $SBFT$. [2]
\end{enumerate}
\item Show these maximum flows on Diagram 1 in the answer book. [1]
\end{enumerate}
Take your answer to part (b) as the initial flow pattern.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item \begin{enumerate}[label=(\roman*)]
\item Use the labelling procedure to find a maximum flow from $S$ to $T$. Your working should be shown on Diagram 2 in the answer book. List each flow-augmenting route you use, together with its flow. [5]
\item Draw your final flow pattern on Diagram 3 in the answer book. [2]
\item Prove that your flow is maximal. [3]
\end{enumerate}
\item Give an example of a practical situation that could have been modelled by the original network. [1]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2005 Q6 [14]}}