| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Standard +0.8 This is a multi-part network flows question requiring students to add supersource/supersink, apply the labelling procedure, find maximum flow, and prove maximality using cut theorem. While systematic, it requires understanding multiple D2 concepts and careful execution across 5 parts, making it moderately challenging but still a standard exam question for this module. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | \(M1 A1 A1\) | (3) |
| (b) | \(M1 A1\) | (2) |
| \(B1M1\) | — | One valid flow augmenting route found and a value stated |
| \(A1\) | — | Flow increased by at least 3 |
| \(A1\) | — | A second correct flow route of value at least 5 and value correct |
| \(C3A1\) | — | CSO Flow increased by 21 and no more |
| (c) | \(M1 A1\) | (4) |
| \(A1\) | — | — |
| (d) | \(M1 A1\) | (2) |
| (e) | \(DB1\) | (2) |
| \(DB1\) | — | CSO (d) fully correct (showing a correct flow of 102) and a correct cut. Must refer to max flow–min cut theorem; all four words |
| 13 marks |
**(a)** | $M1 A1 A1$ | (3) | Four arcs added, $SS_1$, $SS_2$, $T_1T$, $T_2T$ and 2 numbers on each; CAO for arcs; CAO for flow values and capacities |
**(b)** | $M1 A1$ | (2) | Two numbers on each arc and at least three arcs or six numbers correct; CAO do give bod since they might well cross these numbers out |
| $B1M1$ | — | One valid flow augmenting route found and a value stated |
| $A1$ | — | Flow increased by at least 3 |
| $A1$ | — | A second correct flow route of value at least 5 and value correct |
| $C3A1$ | — | CSO Flow increased by 21 and no more |
**(c)** | $M1 A1$ | (4) | E.g. $SS:BET;T - 13$, $SS:BADT;T - 3$, $SS:BADET;T - 5$; CAO for arcs; CAO for flow values and capacities |
| $A1$ | — | — |
**(d)** | $M1 A1$ | (2) | — |
**(e)** | $DB1$ | (2) | Must have attempted (d); at least one number on all but one arc, and made an attempt at a cut, either drawn or stated |
| $DB1$ | — | CSO (d) fully correct (showing a correct flow of 102) and a correct cut. Must refer to max flow–min cut theorem; all four words |
| | 13 marks | |
---5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{d708ce08-4ea3-4a13-a39c-00efcde32c57-5_707_969_237_523}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Add a supersource, S , and a supersink, T , and corresponding arcs to Diagrams 1 and 2, in the answer book.
\item Enter the flow value and appropriate capacity on each of the arcs you have added to Diagram 1.
\end{enumerate}\item Complete the initialisation of the labelling procedure on Diagram 2 by entering values along the new arcs from $S$ and $T$, and along $A B , A D$ and $D _ { 2 }$.
\item Hence use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
\item Draw a maximal flow pattern on Diagram 3 in the answer book.
\item Prove that your flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2014 Q5 [13]}}