| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2003 |
| Session | June |
| Marks | 18 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Moderate -0.8 This is a standard textbook exercise on network flows requiring routine application of well-defined algorithms (adding supersource/supersink, flow conservation, labelling procedure, max-flow min-cut). While multi-part with several marks, each step follows a mechanical procedure with no novel problem-solving or insight required. Easier than average A-level maths questions. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | Adds S and T and arcs: \(SS_1 \geq 45, SS_2 \geq 35, T_1T \geq 24, T_2T \geq 58\) | M1 A1 |
| (b) | Using conservation of flow through vertices \(x = 16\) and \(y = 7\) | B1 B1 |
| (c) | \(C_1 = 86, C_2 = 81\) | B1 B2 |
| (d) | Network diagram with flow values and capacities marked. e.g. \(SS_1 ADEHT_2T -2\) or \(SS_1 ACFEHT_1T -3\) or \(SS_2 BGDT_2T -2\) | M1 A1 dM1 A1 A1 |
| (e) | e.g. Network showing Flow 75 | M1 A1 A1 |
| (f) | Max flow – min cut theorem. Cut through CF, CE, AD, BD, BG (value 75) | dM1 A1 |
(a) | Adds S and T and arcs: $SS_1 \geq 45, SS_2 \geq 35, T_1T \geq 24, T_2T \geq 58$ | M1 A1 | 2 |
(b) | Using conservation of flow through vertices $x = 16$ and $y = 7$ | B1 B1 | 2 |
(c) | $C_1 = 86, C_2 = 81$ | B1 B2 | 3 |
(d) | Network diagram with flow values and capacities marked. e.g. $SS_1 ADEHT_2T -2$ or $SS_1 ACFEHT_1T -3$ or $SS_2 BGDT_2T -2$ | M1 A1 dM1 A1 A1 | 6 |
(e) | e.g. Network showing Flow 75 | M1 A1 A1 | 3 |
(f) | Max flow – min cut theorem. Cut through CF, CE, AD, BD, BG (value 75) | dM1 A1 | 2 |7.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-4_759_1529_715_267}
\end{center}
\end{figure}
Figure 1 shows a capacitated, directed network. The unbracketed number on each arc indicates the capacity of that arc, and the numbers in brackets show a feasible flow of value 68 through the network.
\begin{enumerate}[label=(\alph*)]
\item Add a supersource and a supersink, and arcs of appropriate capacity, to Diagram 1 below.
\section*{Diagram 1}
\includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-4_684_1531_1816_267}
\item Find the values of $x$ and $y$, explaining your method briefly.
\item Find the value of cuts $C _ { 1 }$ and $C _ { 2 }$.
Starting with the given feasible flow of 68,
\item use the labelling procedure on Diagram 2 to find a maximal flow through this network. List each flow-augmenting route you use, together with its flow.
\section*{Diagram 2}
\includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-5_647_1506_612_283}
\item Show your maximal flow on Diagram 3 and state its value.
\section*{Diagram 3}
\includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-5_654_1511_1567_278}
\item Prove that your flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2003 Q7 [18]}}