| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2004 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Find missing flow values |
| Difficulty | Moderate -0.8 This is a standard textbook application of the max-flow min-cut algorithm with clear diagrams provided. Part (a) requires simple conservation of flow at nodes, parts (b-d) follow the routine labelling procedure taught in D1, and part (e) asks for a standard min-cut proof. While multi-part with 13 marks total, each step is algorithmic with no novel problem-solving required—easier than average A-level questions. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
\includegraphics{figure_3}
Figure 3 shows a capacitated directed network. The number on each arc is its capacity.
\includegraphics{figure_4}
Figure 4 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 in this answer book to find a maximum flow through the network. You must list each flow-augmenting route 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 2004 Q5 [13]}}