| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2004 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Calculate cut capacity |
| Difficulty | Moderate -0.5 This is a standard D1 network flows question testing routine application of the max-flow min-cut theorem. Parts (a) and (b) require only reading capacities from a diagram and comparing values, while part (c) involves straightforward analysis of which new arc increases the minimum cut capacity. No novel problem-solving or complex reasoning is required—just mechanical application of a well-practiced algorithm. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
\includegraphics{figure_1}
Figure 1 shows a network of roads represented by arcs. The capacity of the road represented by that arc is shown on each arc. The numbers in circles represent a possible flow of 26 from $B$ to $L$.
Three cuts $C_1$, $C_2$ and $C_3$ are shown on Fig. 1.
\begin{enumerate}[label=(\alph*)]
\item Find the capacity of each of the three cuts. [3]
\item Verify that the flow of 26 is maximal. [1]
\end{enumerate}
The government aims to maximise the possible flow from $B$ to $L$ by using one of two options.
Option 1: Build a new road from $E$ to $J$ with capacity 5.
or
Option 2: Build a new road from $F$ to $H$ with capacity 3.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item By considering both options, explain which one meets the government's aim [3]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2004 Q3 [7]}}