| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2017 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Moderate -0.5 This is a standard textbook application of the labelling procedure (max flow-min cut algorithm) with straightforward initialization and execution. While it requires multiple steps and careful bookkeeping, it follows a mechanical algorithm with no novel problem-solving or insight required—students simply apply the taught procedure to a given network. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks |
|---|---|
| Initial flow = 57 | B1 (1) |
| Answer | Marks |
|---|---|
| Value of the cut = 102 | B1 (1) |
| Answer | Marks |
|---|---|
| M1 A1 (2) |
| Answer | Marks |
|---|---|
| e.g. SBEGT – 2; SBACT – 5; SBCT – 3; SBEDFGT – 1 | M1 A1 A1 A1 (4) |
| e.g. SBCT – 7; SBEGT – 2; SBEDFGT – 1; SBACT – 1 |
| Answer | Marks |
|---|---|
| M1 A1 (2) |
| Answer | Marks |
|---|---|
| Or as above with AC(15), CB(0) and AB(9) | |
| The cut through CT, BT, ET, EG and FG has a value of 68 | DB1 DB1 (2) |
| Value of the flow is 68 so by the max flow – min cut theorem flow is maximal |
**Part (a):**
Initial flow = 57 | B1 (1)
**Part (b):**
Value of the cut = 102 | B1 (1)
**Part (c):**
| M1 A1 (2)
**Part (d):**
e.g. SBEGT – 2; SBACT – 5; SBCT – 3; SBEDFGT – 1 | M1 A1 A1 A1 (4)
e.g. SBCT – 7; SBEGT – 2; SBEDFGT – 1; SBACT – 1 |
**Part (e):**
| M1 A1 (2)
**Part (f):**
Or as above with AC(15), CB(0) and AB(9) |
The cut through CT, BT, ET, EG and FG has a value of 68 | DB1 DB1 (2)
Value of the flow is 68 so by the max flow – min cut theorem flow is maximal |
**Notes for Question 6:**
- **a1B1:** CAO
- **b1B1:** CAO
- **c1M1:** Two numbers on each arc and any four numbers correct
- **c1A1:** CAO do give bod since they might well cross these numbers out (in attempting (d))
- **d1M1:** One valid flow augmenting route found and any value stated
- **d1A1:** A second correct flow route and any value stated
- **d2A1:** Three correct flow routes with corresponding correct values
- **d3A1:** CSO flow increased by 11 and no more
- **e1M1:** Consistent flow pattern ≥ 61 (check each node). One number only per arc. No unnumbered arcs
- **e1A1:** CAO showing flow of 68
- **f1DB1:** Must have attempted (e) and scored at least M1A1 in (d) – at least one number on all but one arc, and either drawn or stated a cut. Cut may be drawn on any diagram. Note that the cut must separate source (S) from sink (T)
- **f2DB1:** CSO – (e) must be fully correct (showing a correct flow of 68) and a correct cut (either stated or shown on any diagram). Must state the value of 68 in their answer and refer to max flow – min cut theorem – all four words
---6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{d5798c81-290a-4e4b-aa46-497b62ca899b-07_1155_1541_223_264}
\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 the corresponding arc. The numbers in circles represent an initial flow from S to T .
\begin{enumerate}[label=(\alph*)]
\item State the value of the initial flow.
\item State the capacity of cut $C _ { 1 }$
\item Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along $\mathrm { AC } , \mathrm { SB } , \mathrm { BE } , \mathrm { DE }$ and FG .\\
(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 2 in the answer book.
\item Prove that your flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2017 Q6 [12]}}