| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2020 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Lower and upper capacity networks |
| Difficulty | Challenging +1.2 This is a structured Further Maths question on network flows with lower/upper capacities. While the topic is advanced, the question guides students through standard techniques (identifying source/sink, cut capacity, feasibility constraints, max-flow min-cut theorem) with clear sub-parts. Parts (a)-(d) require understanding definitions and logical reasoning about capacity constraints, while (e)-(f) apply standard algorithms. The multi-step nature and Further Maths content place it above average difficulty, but the scaffolding and routine application of learned techniques prevent it from being exceptionally challenging. |
| Spec | 7.02p Networks: weighted graphs, modelling connections |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Source node is C | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| G is the sink node as all the arcs incident to G flow into G | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Capacity of cut \(C_1 = 10 + 2 - 1 + 6 + 8 + 1 - 0 = 26\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Arc JH must be at its upper capacity of 5 as the two arcs that flow into J (EJ and FJ) have a lower capacity of \(2 + 3 = 5\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Arcs AD and CD must be at the lower capacities (which in total is 9) as the only two arcs (DG and DE) that flow out of D have a total upper capacity of \(7 + 2 = 9\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Updated flow diagram showing flows: A-D: 5, D-G: 7, D-E: 2 (etc. as per diagram) | M1 | |
| Correct completed flow diagram | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Use of max-flow min-cut theorem | M1 | |
| Identification of cut through DG, DE, CE, CF, CB, BA with capacity of 18 and value of flow \(= 18\) | A1 | |
| Therefore it follows that flow is maximal | A1 |
# Question 5:
## Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Source node is C | B1 | |
## Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| G is the sink node as all the arcs incident to G flow into G | B1 | |
## Part (c):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Capacity of cut $C_1 = 10 + 2 - 1 + 6 + 8 + 1 - 0 = 26$ | B1 | |
## Part (d)(i):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Arc JH must be at its upper capacity of 5 as the two arcs that flow into J (EJ and FJ) have a lower capacity of $2 + 3 = 5$ | B1 | |
## Part (d)(ii):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Arcs AD and CD must be at the lower capacities (which in total is 9) as the only two arcs (DG and DE) that flow out of D have a total upper capacity of $7 + 2 = 9$ | B1 | |
## Part (e):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Updated flow diagram showing flows: A-D: 5, D-G: 7, D-E: 2 (etc. as per diagram) | M1 | |
| Correct completed flow diagram | A1 | |
## Part (f):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Use of max-flow min-cut theorem | M1 | |
| Identification of cut through DG, DE, CE, CF, CB, BA with capacity of 18 and value of flow $= 18$ | A1 | |
| Therefore it follows that flow is maximal | A1 | |5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e0fc09f9-06ea-4528-a2de-f409112d85cc-06_830_1397_205_333}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 2 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 capacities and upper capacities for the corresponding pipes, in litres per second.
\begin{enumerate}[label=(\alph*)]
\item State the source node.
\item Explain why the sink node must be G.
\item Calculate the capacity of the cut $C _ { 1 }$
\item Assuming that a feasible flow exists,
\begin{enumerate}[label=(\roman*)]
\item explain why arc JH must be at its upper capacity,
\item explain why arcs AD and CD must be at their lower capacities.
\end{enumerate}\item Use Diagram 1 in the answer book to show a flow of 18 litres per second through the system.
\item Prove that the answer to (e) is the maximum flow through the system.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 2020 Q5 [10]}}