| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Year | 2022 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | List saturated arcs |
| Difficulty | Moderate -0.5 This is a straightforward application of standard network flow algorithms requiring identification of saturated arcs, calculation of cut capacities, and finding an augmenting path. While it involves multiple parts, each step follows routine procedures taught in FD2 with no novel problem-solving required. The proof in part (f) is a direct application of the max-flow min-cut theorem. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(50\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Saturated arcs: AB, BC, SD, BE, DT, GE, GH and GT | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Capacity of arc EH is 37. Three arcs flowing into E are BE, FE and GE. Total capacity \(= 10 + 19 + 5 = 34\). Since \(37 > 34\), EH cannot be full to capacity | B1 | Must be numerical; correct reasoning required |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| (i) Value of cut \(C_1 = 10 + 6 + 6 + 13 + 23 = 58\) | B1 | cao |
| (ii) Value of cut \(C_2 = 37 + 6 + 12 + 13 + 23 = 91\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| e.g. SACBFEHT | B1 | One correct flow-augmenting route only |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Use of max-flow min-cut theorem; identification of cut through BE, FE, GE, GH, GT, DT | M1 | Attempt to find cut through saturated arcs; source one side, sink other |
| Value of flow \(= 53\) | A1 | Use appropriate process; cut (BE, FE, GE, GH, GT, DT) with value 53 stated correctly |
| Therefore flow is maximal | A1 | Must use all four words 'maximum', 'flow', 'minimum', 'cut'; dep on first A mark |
# Question 2:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| $50$ | B1 | cao |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Saturated arcs: AB, BC, SD, BE, DT, GE, GH and GT | B1 | cao |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Capacity of arc EH is 37. Three arcs flowing into E are BE, FE and GE. Total capacity $= 10 + 19 + 5 = 34$. Since $37 > 34$, EH cannot be full to capacity | B1 | Must be numerical; correct reasoning required |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| (i) Value of cut $C_1 = 10 + 6 + 6 + 13 + 23 = 58$ | B1 | cao |
| (ii) Value of cut $C_2 = 37 + 6 + 12 + 13 + 23 = 91$ | B1 | cao |
## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| e.g. SACBFEHT | B1 | One correct flow-augmenting route only |
## Part (f)
| Answer | Mark | Guidance |
|--------|------|----------|
| Use of max-flow min-cut theorem; identification of cut through BE, FE, GE, GH, GT, DT | M1 | Attempt to find cut through saturated arcs; source one side, sink other |
| Value of flow $= 53$ | A1 | Use appropriate process; cut (BE, FE, GE, GH, GT, DT) with value 53 stated correctly |
| Therefore flow is maximal | A1 | Must use all four words 'maximum', 'flow', 'minimum', 'cut'; dep on first A mark |
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{d7e250dc-9e38-4f65-a51a-c6a08082f310-03_1120_1757_212_153}
\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.
\item List the eight saturated arcs.
\item Explain why arc EH can never be full to capacity.
\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 that increases the flow by three units.
Given that the flow through the network is increased by three units,
\item prove that this new flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 AS 2022 Q2 [9]}}