| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Year | 2019 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Standard +0.3 This is a standard Further Maths network flows question requiring routine application of the labelling procedure algorithm. While it involves multiple parts and careful bookkeeping, each step follows a well-defined algorithmic process taught in FD2. The question tests procedural fluency rather than problem-solving insight, making it slightly easier than average for A-level but typical for Further Maths Decision content. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(45\) | B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Total capacity of arcs DF and DG is \(5 + 11 = 16\). Capacity into D is \(10 + 4 = 14\). As \(14 < 16\), arcs DF and DG cannot both be full to capacity. | B1 | CAO; minimum: mention max flow into D is 14, max flow out of D is 16, with comparison; node D must be mentioned |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Value of cut \(= 32 + 10 + 4 + 7 + 12 = 65\) | B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| e.g. SACFHT \(- 2\); SADGJT \(- 4\); SBEDFHT \(- 2\) | M1 | One correct flow augmenting route from S to T + flow value or two correct routes |
| e.g. SACFHT \(- 2\); SADGJT \(- 2\); SADFHT \(- 2\); SBEDGJT \(- 2\) | A1 | Two correct routes + correct flow values |
| e.g. SACFHT \(- 2\); SADGJT \(- 4\); SBEDGJT \(- 2\) | A1 | CSO — increasing flow by 8 only |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Diagram with updated flow values; Alternative: DG 11, GJ 18, JT 32; DF 3, FH 5, HT 16 | B1 | CAO; condone more than one value on an arc only if one value is circled — mark those circled only |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Use of max-flow min-cut theorem; identification of cut through CH, CF, AD, BD, DE, EG and EJ | M1 | Construct argument based on max-flow min-cut theorem; attempt to find genuine cut with value of cut or flow (but not re-iterating the cut from (c)) |
| Value of flow \(= 53\); therefore by max-flow min-cut theorem flow is maximal | A1 | Correct cut + value correct (accept '53'; cut either stated or drawn) |
| Correct deduction that flow is maximal by stating 'maximum flow (equal to) minimum cut' | A1 | Dependent on previous A mark and correct flow in (e) |
# Question 3:
## Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $45$ | B1 | CAO |
## Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Total capacity of arcs DF and DG is $5 + 11 = 16$. Capacity into D is $10 + 4 = 14$. As $14 < 16$, arcs DF and DG cannot both be full to capacity. | B1 | CAO; minimum: mention max flow into D is 14, max flow out of D is 16, with comparison; node D must be mentioned |
## Part (c):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Value of cut $= 32 + 10 + 4 + 7 + 12 = 65$ | B1 | CAO |
## Part (d):
| Answer/Working | Mark | Guidance |
|---|---|---|
| e.g. SACFHT $- 2$; SADGJT $- 4$; SBEDFHT $- 2$ | M1 | One correct flow augmenting route from S to T + flow value **or** two correct routes |
| e.g. SACFHT $- 2$; SADGJT $- 2$; SADFHT $- 2$; SBEDGJT $- 2$ | A1 | Two correct routes + correct flow values |
| e.g. SACFHT $- 2$; SADGJT $- 4$; SBEDGJT $- 2$ | A1 | CSO — increasing flow by 8 only |
## Part (e):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Diagram with updated flow values; Alternative: DG 11, GJ 18, JT 32; DF 3, FH 5, HT 16 | B1 | CAO; condone more than one value on an arc only if one value is circled — mark those circled only |
## Part (f):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Use of max-flow min-cut theorem; identification of cut through CH, CF, AD, BD, DE, EG and EJ | M1 | Construct argument based on max-flow min-cut theorem; attempt to find genuine cut with value of cut or flow (but not re-iterating the cut from (c)) |
| Value of flow $= 53$; therefore by max-flow min-cut theorem flow is maximal | A1 | Correct cut + value correct (accept '53'; cut either stated or drawn) |
| Correct deduction that flow is maximal by stating 'maximum flow (equal to) minimum cut' | A1 | Dependent on previous A mark and correct flow in (e) |
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{bbdfa492-6578-484a-a0b5-fcdb78020b83-03_801_1728_269_166}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Alexa is monitoring a system of pipes through which fluid can flow from the source, S , to the sink, T . Currently, fluid is flowing through the system from S to T .
Alexa 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 Explain why arcs DF and DG can never both be full to capacity.
\item Obtain the capacity of the cut that passes through the $\operatorname { arcs } \mathrm { AC } , \mathrm { AD } , \mathrm { BD } , \mathrm { DE } , \mathrm { EG }$ and EJ .
\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.\\
(3)
\item Use your answers to part (d) to find a maximum flow pattern for this system of pipes and draw it on Diagram 1 in the answer book.
\item Prove that the answer to part (e) is optimal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 AS 2019 Q3 [10]}}