| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Moderate -0.8 This is a standard textbook application of the labelling procedure algorithm for network flows. Part (a) requires simple addition of initial flows, part (b) is direct application of the initialization step, and parts (c)-(e) follow the algorithmic procedure taught in D2. While multi-part with 11 marks total, it requires no problem-solving insight—just careful execution of a learned algorithm, making it easier than average A-level questions. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Part | Scheme | Marks |
| (a) | Initial flow = 62 | B1 |
| (b) | [Network diagram with flows shown] | M1 A1 |
| (c) | E.g. SCEDT - 3, SCEADT - 3, SBADT - 2 or SCBADT 2, SCEDT - 3, SBCEDT 1, SCEADT 2, SBADT - 3 or similar | M1 A1 A1 |
| (d) | [Diagram showing flow values on arcs with cut indicated] | M1 A1 |
| (e) | The cut through SA, AB, AE, DE, ET and FT has value 70. Value of the flow is 70 so by max flow – min cut theorem flow is maximal | DB1 DB1 |
| 11 marks |
| Part | Scheme | Marks | Guidance |
|------|--------|-------|----------|
| (a) | Initial flow = 62 | B1 | |
| (b) | [Network diagram with flows shown] | M1 A1 | b1M1: Two numbers on each arc and at least two arcs or four numbers correct (so correct numbers with the correct arrows). b1A1: CAO do give bod since they might well cross these number out. c1M1: One valid flow augmenting route found and a value stated. |
| (c) | E.g. SCEDT - 3, SCEADT - 3, SBADT - 2 or SCBADT 2, SCEDT - 3, SBCEDT 1, SCEADT 2, SBADT - 3 or similar | M1 A1 A1 | c2A1: A second correct flow route and value correct. c3A1: CSO Flow increased by 8 and no more. |
| (d) | [Diagram showing flow values on arcs with cut indicated] | M1 A1 | d1M1: Consistent flow pattern 2+ (check each node). One number only per arc. No unnumbered arcs. d1a1: CAO, showing flow of 70, must follow from their routes. e1DB1: Must have attempted (d) - at least one number on all but one arc, and either drawn or stated a cut. Cut may be drawn on any diagram. e2DB1: CSO – (d) fully correct (showing a correct flow of 70) and a correct cut. Must refer to max flow-min cut theorem – all four words. |
| (e) | The cut through SA, AB, AE, DE, ET and FT has value 70. Value of the flow is 70 so by max flow – min cut theorem flow is maximal | DB1 DB1 | |
| | | **11 marks** | |
---5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{76ea87ad-b77b-482c-93dd-c8593ae3199f-6_652_1340_214_367}
\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 State the value of the initial flow.\\
(1)
\item Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along $\mathrm { SC } , \mathrm { AB } , \mathrm { CE } , \mathrm { DE }$ and DT .\\
(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.\\
(4)
\item Draw a maximal flow pattern on Diagram 2 in the answer book.\\
(2)
\item Prove that your flow is maximal.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2014 Q5 [11]}}