| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2023 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Find flow-augmenting route by inspection |
| Difficulty | Moderate -0.5 This is a standard network flows question requiring routine application of max-flow min-cut theorem. Parts (a)-(c) involve reading values from a diagram and finding an augmenting path by inspection (explicitly stated), while part (d) applies the standard proof technique of showing flow equals minimum cut capacity. No novel problem-solving required, just textbook procedures. |
| Spec | 7.02p Networks: weighted graphs, modelling connections |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(54\) | B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(C_1 = 17 + 8 + 17 + 11 + 18 = 71\) | B1 | CAO for \(C_1\) |
| \(C_2 = 17 + 6 + 29 + 17 + 21 = 90\) | B1 | CAO for \(C_2\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| SAFDET | B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Use of max-flow min-cut theorem | M1 | Construct argument based on max-flow min-cut theorem; attempt to find a cut through arcs — must contain source on one side and sink on the other. Allow a cut drawn on diagram (need not be correct one). If cut not drawn, must list arcs not values. |
| Identification of cut through FT, FE, DF, AD, BD, CD and CE; Value of flow \(= 56\) | A1 | Use appropriate process of finding a minimum cut — FT, FE, DF, AD, BD, CD and CE plus value correct and value of flow through the network stated correctly (\(56\)) |
| Therefore it follows that flow is maximal | A1 | Correct deduction that flow is maximal — must use all four words 'maximum', 'flow', 'minimum' and 'cut' (allow use of max and min); dependent on previous A1 |
## Question 1:
### Part (a):
| Answer | Mark | Guidance |
|--------|------|----------|
| $54$ | B1 | CAO |
**(1 mark)**
---
### Part (b):
| Answer | Mark | Guidance |
|--------|------|----------|
| $C_1 = 17 + 8 + 17 + 11 + 18 = 71$ | B1 | CAO for $C_1$ |
| $C_2 = 17 + 6 + 29 + 17 + 21 = 90$ | B1 | CAO for $C_2$ |
**(2 marks)**
---
### Part (c):
| Answer | Mark | Guidance |
|--------|------|----------|
| SAFDET | B1 | CAO |
**(1 mark)**
---
### Part (d):
| Answer | Mark | Guidance |
|--------|------|----------|
| Use of max-flow min-cut theorem | M1 | Construct argument based on max-flow min-cut theorem; attempt to find a cut through arcs — must contain source on one side and sink on the other. Allow a cut drawn on diagram (need not be correct one). If cut not drawn, must list arcs not values. |
| Identification of cut through FT, FE, DF, AD, BD, CD and CE; Value of flow $= 56$ | A1 | Use appropriate process of finding a minimum cut — FT, FE, DF, AD, BD, CD and CE plus value correct and value of flow through the network stated correctly ($56$) |
| Therefore it follows that flow is maximal | A1 | Correct deduction that flow is maximal — must use all four words 'maximum', 'flow', 'minimum' and 'cut' (allow use of max and min); dependent on previous A1 |
**(3 marks)**
**Total: 7 marks**1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{ae354c58-6de8-4f94-b404-2f0feecb5bf3-02_953_1687_251_191}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of that pipe. The numbers in circles represent a feasible flow from S to T .
\begin{enumerate}[label=(\alph*)]
\item State the value of the feasible flow.\\
(1)
\item Find the capacity of cut $\mathrm { C } _ { 1 }$ and the capacity of cut $\mathrm { C } _ { 2 }$\\
(2)
\item By inspection, find a flow-augmenting route to increase the flow by two units. You must state your route.\\
(1)
\item Prove that, once the flow-augmenting route found in (c) has been applied, the flow is now maximal.\\
(3)
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 2023 Q1 [7]}}