| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Paper | Download PDF ↗ |
| Topic | Network Flows |
| Type | State maximum flow along specific routes |
| Difficulty | Moderate -0.3 This is a standard D1 network flows question following a predictable structure: read capacities from specific paths, apply the labelling procedure algorithm, and verify maximality using min-cut. While it requires multiple steps and careful bookkeeping, it's a routine application of a well-practiced algorithm with no novel problem-solving required. Slightly easier than average because the question explicitly guides students through each stage of the standard max-flow procedure. |
| Spec | 7.02p Networks: weighted graphs, modelling connections |
6. This question should be answered on the sheet provided in the answer booklet.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-003_469_844_422_1731}
\captionsetup{labelformat=empty}
\caption{Fig. 3}
\end{center}
\end{figure}
Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.
\begin{enumerate}[label=(\alph*)]
\item State the maximum flow along
\begin{enumerate}[label=(\roman*)]
\item SAET,
\item SBDT,
\item SCFT.\\
(3 marks)
\end{enumerate}\item Show these maximum flows on Diagram 1 on the answer sheet.\\
(1 mark)
\item Taking your answer to part (b) as the initial flow pattern, use the labelling procedure to find a maximum flow from $S$ to $T$. Your working should be shown on Diagram 2. List each flow augmenting route you find, together with its flow.\\
(6 marks)
\item Indicate a maximum flow on Diagram 3.\\
(2 marks)
\item Prove that your flow is maximal.\\
(2 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q6}}