| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2002 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Moderate -0.5 This is a standard textbook exercise on adding a supersource to a network flow problem and applying the labelling procedure (Ford-Fulkerson algorithm). While it requires multiple steps, each component is routine: adding arcs from a supersource is mechanical, finding augmenting paths follows a standard algorithm, and proving maximality uses the max-flow min-cut theorem. The question is structured with significant scaffolding (parts a, b guide you through setup), making it easier than average despite being multi-part. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.04f Network problems: choosing appropriate algorithm |
11. 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.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\includegraphics[alt={},max width=\textwidth]{c4c64221-0373-4be9-abe3-5ff281922cdb-10_723_1172_476_337}
\end{center}
\end{figure}
\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.
\item \begin{enumerate}[label=(\roman*)]
\item State the maximum flow along $S F _ { 1 } A B R$ and $S F _ { 3 } C R$.
\item Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles.
Taking your answer to part (b)(ii) as the initial flow pattern,
\end{enumerate}\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.
\item Prove that your final flow is maximal.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2002 Q11 [11]}}