| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Topic | Network Flows |
| Type | Apply labelling procedure for max flow |
| Difficulty | Moderate -0.8 This is a standard textbook application of the max-flow labelling procedure (Ford-Fulkerson algorithm) with straightforward steps: identifying sources (basic definition), reading a given flow value, applying a well-defined algorithm, and verifying maximality using the max-flow min-cut theorem. All parts follow routine procedures taught in D2 with no novel problem-solving required. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
\includegraphics{figure_4}
The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.
\begin{enumerate}[label=(\alph*)]
\item Write down the source vertices. [2]
\end{enumerate}
\includegraphics{figure_5}
Figure 5 shows a feasible flow through the same network.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumii}{1}
\item State the value of the feasible flow shown in Fig. 5. [1]
\end{enumerate}
Taking the flow in Fig. 5 as your initial flow pattern,
\begin{enumerate}[label=(\alph*)]
\setcounter{enumii}{2}
\item use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow. [6]
\item Show the maximal flow on Diagram 2 and state its value. [3]
\item Prove that your flow is maximal. [2]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q8 [14]}}