| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2021 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Lower and upper capacity networks |
| Difficulty | Challenging +1.2 This is a standard Further Maths Decision 2 network flows question covering lower/upper capacities and the labelling procedure. While the topic itself is advanced (Further Maths), the question follows a highly structured, algorithmic approach with clear steps (calculate cuts, apply labelling procedure, verify optimality). The vertex restriction in part (h) adds mild complexity, but overall this is a routine application of taught algorithms rather than requiring novel problem-solving insight. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(C_1 = 8+11+8+10+6+2=45\) | B1 | cao |
| \(C_2 = 8+17-4-0-1+30+2=52\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Maximum possible flow is \(\leq 45\) litres per second | B1ft | Deduced from their least value in (a); must include 'less than or equal to' (oe) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Initial flow \(= 36\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Diagram showing two numbers on each arc with correct flow augmentation | M1 | Two numbers on each arc and at least two arcs or four numbers correct |
| Correct completed diagram | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| One flow augmenting route found from S to T | M1 | One flow augmenting route found |
| e.g., SABGT−2, SCFT−2, SDCET−2, SABET−1 | A1 | Two correct routes with flow values |
| e.g., SABGT−3, SCFT−2, SDCET−2 | A1 | cso – increasing the flow by 7 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct completed flow diagram with all values | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Use of max-flow min-cut theorem; identification of cut through AB, SB, BC, EC, CF, DF and DT | M1 | Construct argument based on max-flow min-cut theorem |
| Value of flow \(= 43\) | A1 | Use appropriate process of finding minimum cut: cut + value correct |
| Therefore flow is maximal | A1 | Correct deduction that flow is maximal |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Flows into B go to \(B_\text{IN}\) and flows out of B go from \(B_\text{OUT}\); labelled diagram with \((5,8)\) on AB, \((0,16)\) on \(B_\text{IN}\) to \(B_\text{OUT}\), \((0,8)\) on \(B_\text{OUT}\) to G, \((7,11)\) on SB, \((12,17)\) on BE, \((2,5)\) on EC | B1 | Flows into B go to \(B_\text{IN}\) and flows out of B go from \(B_\text{OUT}\) |
| Arc of capacity 16 from \(B_\text{IN}\) to \(B_\text{OUT}\) | B1 | cao |
| Maximum flow \(= 40\) | B1ft | value of their maximum flow \(-3\) |
# Question 5:
## Part (a)(i) and (ii):
| Answer | Mark | Guidance |
|--------|------|----------|
| $C_1 = 8+11+8+10+6+2=45$ | B1 | cao |
| $C_2 = 8+17-4-0-1+30+2=52$ | B1 | cao |
## Part (b):
| Answer | Mark | Guidance |
|--------|------|----------|
| Maximum possible flow is $\leq 45$ litres per second | B1ft | Deduced from their least value in (a); must include 'less than or equal to' (oe) |
## Part (c):
| Answer | Mark | Guidance |
|--------|------|----------|
| Initial flow $= 36$ | B1 | cao |
## Part (d):
| Answer | Mark | Guidance |
|--------|------|----------|
| Diagram showing two numbers on each arc with correct flow augmentation | M1 | Two numbers on each arc and at least two arcs or four numbers correct |
| Correct completed diagram | A1 | cao |
## Part (e):
| Answer | Mark | Guidance |
|--------|------|----------|
| One flow augmenting route found from S to T | M1 | One flow augmenting route found |
| e.g., SABGT−2, SCFT−2, SDCET−2, SABET−1 | A1 | Two correct routes with flow values |
| e.g., SABGT−3, SCFT−2, SDCET−2 | A1 | cso – increasing the flow by 7 |
## Part (f):
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct completed flow diagram with all values | B1 | cao |
## Part (g):
| Answer | Mark | Guidance |
|--------|------|----------|
| Use of max-flow min-cut theorem; identification of cut through AB, SB, BC, EC, CF, DF and DT | M1 | Construct argument based on max-flow min-cut theorem |
| Value of flow $= 43$ | A1 | Use appropriate process of finding minimum cut: cut + value correct |
| Therefore flow is maximal | A1 | Correct deduction that flow is maximal |
## Part (h):
| Answer | Mark | Guidance |
|--------|------|----------|
| Flows into B go to $B_\text{IN}$ and flows out of B go from $B_\text{OUT}$; labelled diagram with $(5,8)$ on AB, $(0,16)$ on $B_\text{IN}$ to $B_\text{OUT}$, $(0,8)$ on $B_\text{OUT}$ to G, $(7,11)$ on SB, $(12,17)$ on BE, $(2,5)$ on EC | B1 | Flows into B go to $B_\text{IN}$ and flows out of B go from $B_\text{OUT}$ |
| Arc of capacity 16 from $B_\text{IN}$ to $B_\text{OUT}$ | B1 | cao |
| Maximum flow $= 40$ | B1ft | value of their maximum flow $-3$ |5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{262aa0e6-479f-447a-94db-aeb901b3c6fe-5_1095_1666_212_203}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 shows a capacitated, directed network. The network represents a system of pipes through which fluid can flow.
The weights on the arcs show the lower and upper capacities for the corresponding pipes, in litres per second.
\begin{enumerate}[label=(\alph*)]
\item Calculate the capacity of
\begin{enumerate}[label=(\roman*)]
\item cut $C _ { 1 }$
\item cut $C _ { 2 }$
\end{enumerate}\item Using only the capacities of cuts $C _ { 1 }$ and $C _ { 2 }$, state what can be deduced about the maximum flow through the system.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{262aa0e6-479f-447a-94db-aeb901b3c6fe-6_775_1516_169_278}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 2 shows an initial flow through the same network.
\item State the value of the initial flow.
\item By entering values along $B C , C F$ and $D T$, complete the labelling procedure on Diagram 1 in the answer book.
\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.
\item Use your answer to (e) to find a maximum flow pattern for this system of pipes and draw it on Diagram 2 in the answer book.
\item Prove that the answer to (f) is optimal.
A vertex restriction is now applied to $B$ so that no more than 16 litres per second can flow through it.
\item \begin{enumerate}[label=(\roman*)]
\item Complete Diagram 3 in the answer book to show this restriction.
\item State the value of the maximum flow with this restriction.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 2021 Q5 [16]}}