| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Year | 2023 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Standard +0.3 This is a standard max-flow min-cut algorithm question requiring mechanical application of the labelling procedure. Part (a) reads initial flow from diagram, (b) calculates a cut capacity by addition, (c)-(e) follow textbook procedure. While multi-part with several marks, it requires no novel insight—just careful execution of a learned algorithm, making it slightly easier than average A-level maths. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(72\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Value of cut \(= 25 + 15 + 27 + 15 + 10 = 92\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| One correct flow augmenting route found from S to T | M1 | Routes containing SB, BA, AD, CF, ED, EG, DG or JT are incorrect |
| Two correct routes (ignoring numerical values) | A1 | — |
| Increasing the flow by 5 (and no more); at least two routes with correct values | A1 | cso |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct diagram showing updated flow pattern | B1 | cao; if two numbers on each arc neither circled then B0; do not accept blank arc as zero |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Use of max-flow min-cut theorem; attempt to find cut through saturated arcs | M1 | Must contain source on one side, sink on other; dependent on attempt at part (d) |
| Cut through AD, BD, ED, EG, GJ and JT; value of flow \(= 77\) | A1 | — |
| Flow is optimal, therefore it follows | A1 | Must use all four words: 'maximum', 'flow', 'minimum', 'cut' |
# Question 2:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| $72$ | B1 | cao |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Value of cut $= 25 + 15 + 27 + 15 + 10 = 92$ | B1 | cao |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| One correct flow augmenting route found from S to T | M1 | Routes containing SB, BA, AD, CF, ED, EG, DG or JT are incorrect |
| Two correct routes (ignoring numerical values) | A1 | — |
| Increasing the flow by 5 (and no more); at least two routes with correct values | A1 | cso |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct diagram showing updated flow pattern | B1 | cao; if two numbers on each arc neither circled then B0; do not accept blank arc as zero |
## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| Use of max-flow min-cut theorem; attempt to find cut through saturated arcs | M1 | Must contain source on one side, sink on other; dependent on attempt at part (d) |
| Cut through AD, BD, ED, EG, GJ and JT; value of flow $= 77$ | A1 | — |
| Flow is optimal, therefore it follows | A1 | Must use all four words: 'maximum', 'flow', 'minimum', 'cut' |
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{ddebe845-4280-471b-8da0-cb7211cea756-03_855_1820_210_127}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
An engineer monitors a system of pipes through which a fluid flows from the source, S , to the sink, T .
The engineer initialises the labelling procedure for this system, and the excess capacities and potential backflows are shown on the arrows either side of each arc, as shown in Figure 1.
\begin{enumerate}[label=(\alph*)]
\item State the value of the initial flow.
\item Obtain the capacity of the cut that passes through the arcs $\mathrm { SA } , \mathrm { SB } , \mathrm { CE } , \mathrm { FE }$ and FJ .
\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.
\item Use your answer to (c) to draw a maximum flow pattern on Diagram 1 in the answer book.
\item Prove that the answer to (d) is optimal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 AS 2023 Q2 [9]}}