| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Moderate -0.5 This is a standard textbook exercise on adding supersource/supersink to a network flow problem, followed by routine application of the labelling procedure (max-flow algorithm). While it requires multiple steps and careful bookkeeping, it involves only direct application of a well-defined algorithm with no novel insight or problem-solving required. The topic is D2 level but the question type is procedural and formulaic. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| (a) Supersource \(W\) connects to \(W_1\) (cap 14), \(W_2\) (cap 12), \(W_3\) (cap 14). Supersink \(R\) connects from \(R_1\) (cap 6), \(R_2\) (cap 25). | B3 | One mark per correct arc with correct capacity |
| (b)(i) \(W \to W_1 \to A \to R_1 \to R\): flow = \(\min(14, 8, 6, 6) = 6\) | B1 | |
| (b)(ii) \(W \to W_3 \to C \to R_2 \to R\): flow = \(\min(14, 11, 16, 25) = 11\) | B1 |
**Question 12:**
**(a)** Supersource $W$ connects to $W_1$ (cap 14), $W_2$ (cap 12), $W_3$ (cap 14). Supersink $R$ connects from $R_1$ (cap 6), $R_2$ (cap 25). | B3 | One mark per correct arc with correct capacity
**(b)(i)** $W \to W_1 \to A \to R_1 \to R$: flow = $\min(14, 8, 6, 6) = 6$ | B1
**(b)(ii)** $W \to W_3 \to C \to R_2 \to R$: flow = $\min(14, 11, 16, 25) = 11$ | B112.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-012_618_1211_253_253}
\end{center}
\end{figure}
A company has 3 warehouses $W _ { 1 } , W _ { 2 }$, and $W _ { 3 }$. It needs to transport the goods stored there to 2 retail outlets $R _ { 1 }$ and $R _ { 2 }$. The capacities of the possible routes, in van loads per day, are shown in Fig 2. Warehouses $W _ { 1 } , W _ { 2 }$ and $W _ { 3 }$ have 14, 12 and 14 van loads respectively available per day and retail outlets $R _ { 1 }$ and $R _ { 2 }$ can accept 6 and 25 van loads respectively per day.
\begin{enumerate}[label=(\alph*)]
\item On Diagram 1 on the answer sheet add a supersource $W$, a supersink $R$ and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added.
\item State the maximum flow along
\begin{enumerate}[label=(\roman*)]
\item $W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R$,
\item $W W _ { 3 } \quad C \quad R _ { 2 } \quad R$.
\end{enumerate}\item Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from $W$ to $R$. Show your working on Diagram 2. List each flowaugmenting route you use, together with its flow.
\item From your final flow pattern, determine the number of van loads passing through $B$ each day.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q12}}