| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2003 |
| Session | June |
| Marks | 18 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Find missing flow values |
| Difficulty | Standard +0.3 This is a standard D1 network flows question testing routine application of the labelling procedure algorithm. While multi-part with 18 marks total, each component (adding supersource/sink, finding unknown flows using conservation, evaluating cuts, applying the standard algorithm, verifying maximality) follows textbook procedures with no novel problem-solving required. Slightly easier than average A-level due to being algorithmic rather than requiring mathematical insight. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
\includegraphics{figure_4}
Figure 4 shows a capacitated, directed network. The unbracketed number on each arc indicates the capacity of that arc, and the numbers in brackets show a feasible flow of value 68 through the network.
\begin{enumerate}[label=(\alph*)]
\item Add a supersource and a supersink, and arcs of appropriate capacity, to Diagram 2 in the answer booklet.
[2]
\item Find the values of $x$ and $y$, explaining your method briefly.
[2]
\item Find the value of cuts $C_1$ and $C_2$.
[3]
\end{enumerate}
Starting with the given feasible flow of 68,
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{3}
\item use the labelling procedure on Diagram 3 to find a maximal flow through this network. List each flow-augmenting route you use, together with its flow.
[6]
\item Show your maximal flow on Diagram 4 and state its value.
[3]
\item Prove that your flow is maximal.
[2]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2003 Q7 [18]}}