| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Year | 2024 |
| Session | June |
| Marks | 8 |
| 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 testing basic concepts: reading flow values, understanding saturation constraints, calculating cut capacities, and finding a flow-augmenting route by inspection. Part (d) explicitly tells students the weight (6) and which arc to saturate (BF), making it straightforward. While it requires understanding of max-flow min-cut theorem, these are routine applications of textbook algorithms with no novel problem-solving required. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial Flow \(= 90\) | B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Maximum flow into \(C\) is \(35\). Maximum flow in \(CD\) is \(21\) and maximum flow in \(CG\) is \(19\). \(35 < 21 + 19\) and therefore \(CD\) and \(CG\) cannot both be saturated | B1 | CAO (as a minimum accept: max inflow to \(C = 35\) and max outflow \(= 40\) and \(35 < 40\)) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (i) \(26+18+24+21+19 = 108\) | B1 | CAO |
| (ii) \(24+19+17+14+40 = 114\) | B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(SBFJT\) \((+6)\) | B1 | Correct flow augmenting route found from \(S\) to \(T\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Use of max-flow min-cut theorem; identification of cut through \(EH\), \(EF\), \(BF\), \(DJ\), \(DG\) and \(CG\) | M1 | Construct argument based on max-flow min-cut theorem (e.g. attempt to find a cut through saturated arcs). Cut must be drawn or listed as arcs not values (condone omission of \(EF\) for M1 only) |
| Capacity of cut \(= 96\) | A1 | Use appropriate process of finding a minimum cut (both cut and value correct) |
| Therefore it follows that flow is maximal | A1 | Correct deduction that flow is maximal (dependent on previous A mark); must use all four words Max Flow = Min Cut |
# Question 1:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial Flow $= 90$ | B1 | CAO |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum flow into $C$ is $35$. Maximum flow in $CD$ is $21$ and maximum flow in $CG$ is $19$. $35 < 21 + 19$ and therefore $CD$ and $CG$ cannot both be saturated | B1 | CAO (as a minimum accept: max inflow to $C = 35$ and max outflow $= 40$ and $35 < 40$) |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| (i) $26+18+24+21+19 = 108$ | B1 | CAO |
| (ii) $24+19+17+14+40 = 114$ | B1 | CAO |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $SBFJT$ $(+6)$ | B1 | Correct flow augmenting route found from $S$ to $T$ |
## Part (e)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Use of max-flow min-cut theorem; identification of cut through $EH$, $EF$, $BF$, $DJ$, $DG$ and $CG$ | M1 | Construct argument based on max-flow min-cut theorem (e.g. attempt to find a cut through **saturated** arcs). Cut must be drawn or listed as arcs not values (condone omission of $EF$ for M1 only) |
| Capacity of cut $= 96$ | A1 | Use appropriate process of finding a minimum cut (both cut and value correct) |
| Therefore it follows that flow is maximal | A1 | Correct deduction that flow is maximal (dependent on previous A mark); must use all four words **Max Flow = Min Cut** |1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{40023f8e-6874-400e-84b5-60d98b648afc-02_1010_1467_353_399}
\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 the corresponding pipe. The numbers in circles represent a feasible flow from S to T.
\begin{enumerate}[label=(\alph*)]
\item State the value of this flow.\\
(1)
\item Explain why arcs CD and CG cannot both be saturated.\\
(1)
\item Find the capacity of
\begin{enumerate}[label=(\roman*)]
\item cut $C _ { 1 }$
\item cut $C _ { 2 }$
\end{enumerate}\item Write down a flow augmenting route of weight 6 which saturates BF.
The flow augmenting route in part (d) is applied to give an increased flow.
\item Prove that this increased flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 AS 2024 Q1 [8]}}