| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Standard +0.3 This is a standard D2 network flows question requiring routine application of the labelling procedure algorithm. While it has multiple parts (14 marks total), each step follows a well-defined algorithmic process taught directly in the specification: reading capacities/flows from a diagram, applying the labelling procedure mechanically, and verifying maximality using the max-flow min-cut theorem. No novel insight or problem-solving is required—students simply execute the standard algorithm they've practiced. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(C_1 = 141\) | B1 | |
| \(C_2 = 97\) | B1 | |
| Value of flow \(= 52\) | B1(3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Updated flow diagram shown | M1 A1(2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| SBEHT \(-13\) | M1, A1 | |
| SACFHT \(- 7\) | A1 | |
| SACEHT \(- 2\) | A1 | |
| SBGECDFHT \(- 11\) | A1(5) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Min cut shown on diagram | M1 A1(2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Min cut \(=\) max flow \(= 85\) | M1 A1(2) |
## Question 5:
### Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $C_1 = 141$ | B1 | |
| $C_2 = 97$ | B1 | |
| Value of flow $= 52$ | B1(3) | |
### Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Updated flow diagram shown | M1 A1(2) | |
### Part (c):
| Answer/Working | Marks | Guidance |
|---|---|---|
| SBEHT $-13$ | M1, A1 | |
| SACFHT $- 7$ | A1 | |
| SACEHT $- 2$ | A1 | |
| SBGECDFHT $- 11$ | A1(5) | |
### Part (d):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Min cut shown on diagram | M1 A1(2) | |
### Part (e):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Min cut $=$ max flow $= 85$ | M1 A1(2) | |
---5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e80fcab6-7c7d-4a0c-84e0-c23f5a969a75-4_924_1646_221_207}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 shows a capacitated, directed, network. The capacity of each arc is shown on that arc and the numbers in circles represent an initial flow from S to T .
Two cuts, $\mathrm { C } _ { 1 }$ and $\mathrm { C } _ { 2 }$ are shown on Figure 1.
\begin{enumerate}[label=(\alph*)]
\item Find the capacity of each of the two cuts and the value of the initial flow.\\
(3)
\item Complete the initialisation of the labelling procedure on Figure 1 in the answer book, by entering values along $\mathrm { SB } , \mathrm { AB } , \mathrm { BE }$ and BG .\\
(2)
\item Hence use the labelling procedure to find a maximum flow of 85 through the network. You must list each flow-augmenting path you use, together with its flow.\\
(5)
\item Show your flow pattern on Figure 2.\\
(2)
\item Prove that your flow is maximal.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q5 [14]}}