| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Year | 2021 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Standard +0.3 This is a standard Further Maths Decision module question on max-flow/min-cut, requiring routine application of the labelling procedure algorithm. Parts (a)-(c) are straightforward reading/calculation, (d) is algorithmic execution, and (f) uses the standard max-flow min-cut theorem proof—all textbook procedures with no novel problem-solving required. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| \(125\) | B1 | 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| Value of cut \(= 31 + 8 + 37 + 19 + 56 = 151\) | B1 | 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| Correct flow diagram with updated arc flows | M1 | 1.1b |
| Correct final diagram | A1 | 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| e.g., \(SADFHT - 4;\ SDBEHT - 2;\ SACFT - 1;\ SAGFEHT - 1\) | M1, A1, A1 | 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| Correct diagram with all updated flows | B1 | 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| Use of max-flow min-cut theorem; identification of cut through \(GT, FT, FH, EF, DE, BD\) and \(SB\) | M1 | 2.1 |
| Value of flow \(= 133\) | A1 | 3.1a |
| Therefore flow is maximal | A1 | 2.2a |
# Question 2:
## Part (a):
$125$ | B1 | 1.1b |
## Part (b):
Value of cut $= 31 + 8 + 37 + 19 + 56 = 151$ | B1 | 1.1b |
**Notes:** **B1:** cao
## Part (c):
Correct flow diagram with updated arc flows | M1 | 1.1b | Two numbers on each arc and at least two arcs or four numbers correct with correct arrows |
Correct final diagram | A1 | 1.1b | cao |
## Part (d):
e.g., $SADFHT - 4;\ SDBEHT - 2;\ SACFT - 1;\ SAGFEHT - 1$ | M1, A1, A1 | 1.1b | M1: One flow augmenting route found S to T; A1: Two correct routes + flow values; A1: cso — increasing flow by 8 |
## Part (e):
Correct diagram with all updated flows | B1 | 1.1b | cao |
## Part (f):
Use of max-flow min-cut theorem; identification of cut through $GT, FT, FH, EF, DE, BD$ and $SB$ | M1 | 2.1 | Construct argument based on max-flow min-cut theorem |
Value of flow $= 133$ | A1 | 3.1a | Use appropriate process of finding minimum cut — cut + value correct |
Therefore flow is maximal | A1 | 2.2a | Correct deduction that flow is maximal |
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{261e22b8-0063-419c-a388-6831a427fb65-03_860_1705_276_182}
\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 Obtain the capacity of the cut that passes through the arcs $\mathrm { AG } , \mathrm { CG } , \mathrm { GF } , \mathrm { FT } , \mathrm { FH }$ and EH .\\
(1)
\item Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along $\mathrm { SD } , \mathrm { BD } , \mathrm { BE }$ and GF .\\
(2)
\item 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.\\
(3)
\item Use the answer to part (d) to add a maximum flow pattern to Diagram 2 in the answer book.\\
(1)
\item Prove that your answer to part (e) is optimal.\\
(3)
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 AS 2021 Q2 [11]}}