| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Year | 2020 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Find missing flow values |
| Difficulty | Moderate -0.5 This is a standard network flows question requiring application of conservation of flow at nodes to find missing values, identification of saturated arcs, cut capacity calculations, and finding an augmenting path. While it involves multiple parts, each step follows routine procedures taught in Decision Maths with no novel problem-solving required. The max-flow min-cut theorem application in part (e) is straightforward once the augmenting path is found. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| (i) \(x = 9\) | B1 | Cao |
| (ii) \(y = 14\) | B1 | Cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| SA, FE, FT | B1 | Cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| (i) Value of cut \(C_1 = 18 + 12 + 17 + 26 = 73\) | B1 | Cao |
| (ii) Value of cut \(C_2 = 18 + 37 + 17 + 26 = 98\) | B1 | Cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| e.g. SCFBET, SBCFBET | B1 | A correct flow-augmenting route |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Use of max-flow min-cut theorem; identification of cut through SA, AB, BE, FE and FT | M1 | Construct argument based on max-flow min-cut theorem (attempt to find a cut through saturated arcs); if cut only given in terms of capacity of arcs (rather than nodes at each end) then M1 only |
| Value of flow \(= 57\) | A1 | Use appropriate process of finding a minimum cut – cut and value correct |
| Therefore flow is maximal | A1 | Correct deduction that the flow is maximal |
## Question 1:
### Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| (i) $x = 9$ | B1 | Cao |
| (ii) $y = 14$ | B1 | Cao |
### Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| SA, FE, FT | B1 | Cao |
### Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| (i) Value of cut $C_1 = 18 + 12 + 17 + 26 = 73$ | B1 | Cao |
| (ii) Value of cut $C_2 = 18 + 37 + 17 + 26 = 98$ | B1 | Cao |
### Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| e.g. SCFBET, SBCFBET | B1 | A correct flow-augmenting route |
### Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| Use of max-flow min-cut theorem; identification of cut through SA, AB, BE, FE and FT | M1 | Construct argument based on max-flow min-cut theorem (attempt to find a cut through saturated arcs); if cut only given in terms of capacity of arcs (rather than nodes at each end) then M1 only |
| Value of flow $= 57$ | A1 | Use appropriate process of finding a minimum cut – cut and value correct |
| Therefore flow is maximal | A1 | Correct deduction that the flow is maximal |
---1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{a9f21789-1c5b-42f5-9c5a-3b29d9346c46-02_751_1557_214_255}
\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 \begin{enumerate}[label=(\roman*)]
\item Find the value of $x$.
\item Find the value of $y$.
\end{enumerate}\item List the saturated arcs.
Two cuts, $C _ { 1 }$ and $C _ { 2 }$, are shown in Figure 1.
\item Find the capacity of
\begin{enumerate}[label=(\roman*)]
\item $C _ { 1 }$
\item $\mathrm { C } _ { 2 }$
\end{enumerate}\item Write down a flow-augmenting route, using the arc CF, that increases the flow by two units.
Given that the flow through the network is increased by two units using the route found in (d), (e) prove that this new flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 AS 2020 Q1 [9]}}