| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Standard +0.3 This is a standard max-flow problem using the labelling procedure (Ford-Fulkerson algorithm), which is a core D2 topic. The question guides students through adding a supersource, finding initial flows along specific paths, and applying the labelling procedure step-by-step. While it requires careful bookkeeping and multiple steps (7 marks for part c), it's a textbook application of a well-practiced algorithm with no novel insight required, making it slightly easier than average. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
A company wishes to transport its products from 3 factories $F_1$, $F_2$ and $F_3$ to a single retail outlet $R$. The capacities of the possible routes, in van loads per day, are shown in Fig. 5.
\includegraphics{figure_5}
\begin{enumerate}[label=(\alph*)]
\item On Diagram 1 in the answer booklet add a supersource $S$ to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added. [2]
\item \begin{enumerate}[label=(\roman*)]
\item State the maximum flow along $SF_1ABR$ and $SF_2CR$. [2]
\item Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles.
\end{enumerate}
Taking your answer to part (b)(ii) as the initial flow pattern,
\item \begin{enumerate}[label=(\roman*)]
\item use the labelling procedure to find a maximum flow from $S$ to $R$. Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow. [7]
\item Prove that your final flow is maximal.
\end{enumerate}
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q11 [11]}}