| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Apply labelling procedure for max flow |
| Difficulty | Standard +0.3 This is a standard D1 max flow question requiring routine application of the labelling procedure algorithm. While it involves multiple parts and careful bookkeeping, it follows a well-practiced algorithmic method with no novel problem-solving required. The network is small enough to manage systematically, making it slightly easier than average A-level questions. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02c Graph terminology: walk, trail, path, cycle, route7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| To From | S | \(T\) | A | \(B\) | \(C\) | D |
| S | - | - | 16 | 26 | - | - |
| T | - | - | - | - | - | - |
| A | - | - | - | - | 13 | 5 |
| B | - | 16 | - | - | - | 11 |
| C | - | 11 | - | - | - | - |
| D | - | 11 | - | - | - | - |
| Answer | Marks |
|---|---|
| [Flow network diagram showing vertices S, A, B, C, D, T with labeled edges: S-A (16), S-B (26), A-D (5), A-C (13), D-C (not shown or 0), D-T (11), C-T (11), B-D (11), B-T (16)] | M1 A2 |
| Answer | Marks |
|---|---|
| Minimum cut = \(\{S, A, B, C, D\} \mid \{T\} = 38\) | M1 A1 |
| Answer | Marks |
|---|---|
| [Flow network diagram with augmented flows labeled in circles on edges] | M2 A2 |
| Maximum flow = 38 | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Maximum as = to minimum cut | B1 | (11) |
**Part (a)**
[Flow network diagram showing vertices S, A, B, C, D, T with labeled edges: S-A (16), S-B (26), A-D (5), A-C (13), D-C (not shown or 0), D-T (11), C-T (11), B-D (11), B-T (16)] | M1 A2 |
**Part (b)**
Minimum cut = $\{S, A, B, C, D\} \mid \{T\} = 38$ | M1 A1 |
**Part (c)**
E.g. augment SAC7 by 11, SBT by 16, SBDT by 10 and SADT by 1, giving
[Flow network diagram with augmented flows labeled in circles on edges] | M2 A2 |
Maximum flow = 38 | A1 |
**Part (d)**
Maximum as = to minimum cut | B1 | (11) |
---4. The following matrix gives the capacities of the pipes in a system.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
To From & S & $T$ & A & $B$ & $C$ & D \\
\hline
S & - & - & 16 & 26 & - & - \\
\hline
T & - & - & - & - & - & - \\
\hline
A & - & - & - & - & 13 & 5 \\
\hline
B & - & 16 & - & - & - & 11 \\
\hline
C & - & 11 & - & - & - & - \\
\hline
D & - & 11 & - & - & - & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Represent this information as a digraph.
\item Find the minimum cut, expressing it in the form $\{ \} \mid \{ \}$, and state its value.
\item Starting from having no flow in the system, use the labelling procedure to find a maximal flow through the system. You should list each flow-augmenting route you use, together with its flow.
\item Explain how you know that this flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q4 [11]}}