| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2019 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Lower and upper capacity networks |
| Difficulty | Challenging +1.8 This is a Further Maths Decision 2 question on network flows with lower and upper capacities, requiring understanding of cut capacity calculations, feasibility constraints, and finding min/max flows without algorithms. While the topic is advanced, parts (a)-(c) are relatively mechanical applications of definitions, and part (d) requires logical reasoning about constraints rather than novel insight. The multi-part structure and need to synthesize constraints across the network elevates it above standard questions but doesn't reach the highest difficulty tier. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(C_1 = 9+11+4+5+7 = 36\) | 1B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(C_2 = 8+5-2-3+11+4+5+2+4 = 34\) | 2B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| If AE and CE were both full to capacity then \(12+4=16\) litres per second would flow through E, but maximum capacity of two arcs out of E (EH and EG) is only \(8+5=13\), so AE and CE cannot both be full to capacity | 1B1 | 2.4 — calculates maximum capacity entering E and compares with maximum capacity leaving E; condones 'flow into \(E = 12+4 < 13\) which is the flow out of E' |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| The minimum flow through arcs AE, CE, CG, FG, FT and DT (providing a cut) is \(10+2+5+5+6+4=32\), so a minimum of 32 must be flowing through the system so 31 is not possible | 1B1 | 2.4 — valid reason why flow cannot be 31 litres per second. Note: if smallest of \(C_1\) and \(C_2\) from (a) is less than 31, do NOT allow '31 > {smallest from a}, hence flow of 31 not possible' |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Attempt to find a flow of 32 using the answer to (c) | 1M1 | 3.4 — award for: indicating min flow \(>31\) so min flow could be 32; OR attempting flow of 32 with sum from S = 32 and correct arc constraints; OR attempting flow of 32 into T with \(DT=4\), \(6\leq FT\leq 8\), \(4\leq GT\leq 4\), \(17\leq HT\leq 20\); OR identifies both 'min flow = 32' AND 'max flow = 34' |
| CAO for consistent flow of 32 (one number per arc, consistent at each node) | 1A1 | 1.1b |
| Attempt to augment minimum flow and recognise that from (a) maximum flow \(\leq 34\) | 1B1 | 2.1 |
| States maximum flow must be 34 with reference to smallest cut in (a); CAO for consistent flow of 34 (one number per arc, consistent at each node) | 2B1 | 1.1b |
# Question 6 (Network Flow):
## Part (a)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $C_1 = 9+11+4+5+7 = 36$ | 1B1 | CAO |
## Part (a)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $C_2 = 8+5-2-3+11+4+5+2+4 = 34$ | 2B1 | CAO |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| If AE and CE were both full to capacity then $12+4=16$ litres per second would flow through E, but maximum capacity of two arcs out of E (EH and EG) is only $8+5=13$, so AE and CE cannot both be full to capacity | 1B1 | 2.4 — calculates maximum capacity entering E and compares with maximum capacity leaving E; condones 'flow into $E = 12+4 < 13$ which is the flow out of E' |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| The minimum flow through arcs AE, CE, CG, FG, FT and DT (providing a cut) is $10+2+5+5+6+4=32$, so a minimum of 32 must be flowing through the system so 31 is not possible | 1B1 | 2.4 — valid reason why flow cannot be 31 litres per second. Note: if smallest of $C_1$ and $C_2$ from (a) is less than 31, do NOT allow '31 > {smallest from a}, hence flow of 31 not possible' |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Attempt to find a flow of 32 using the answer to (c) | 1M1 | 3.4 — award for: indicating min flow $>31$ so min flow could be 32; OR attempting flow of 32 with sum from S = 32 and correct arc constraints; OR attempting flow of 32 into T with $DT=4$, $6\leq FT\leq 8$, $4\leq GT\leq 4$, $17\leq HT\leq 20$; OR identifies both 'min flow = 32' AND 'max flow = 34' |
| CAO for consistent flow of 32 (one number per arc, consistent at each node) | 1A1 | 1.1b |
| Attempt to augment minimum flow and recognise that from (a) maximum flow $\leq 34$ | 1B1 | 2.1 |
| States maximum flow must be 34 with reference to smallest cut in (a); CAO for consistent flow of 34 (one number per arc, consistent at each node) | 2B1 | 1.1b |6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5274a614-7862-49f0-ad1d-b59b73aa51ad-07_983_1513_210_283}
\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 flows from a source, S , to a sink, T .
The numbers ( $l , u$ ) on each arc represent, in litres per second, the lower capacity, $l$, and the upper capacity, $u$, of the corresponding pipe.
Two cuts $C _ { 1 }$ and $C _ { 2 }$ are shown.
\begin{enumerate}[label=(\alph*)]
\item Find the capacity of
\begin{enumerate}[label=(\roman*)]
\item $\operatorname { cut } C _ { 1 }$
\item $\operatorname { cut } C _ { 2 }$
\end{enumerate}\item Explain why the arcs AE and CE cannot be at their upper capacities simultaneously.
\item Explain why a flow of 31 litres per second through the system is not possible.
\item Hence determine a minimum feasible flow and a maximum feasible flow through the system. You must draw these feasible flows on the diagrams in the answer book and give reasons to justify your answer. You should not apply the labelling procedure to find these flows.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 2019 Q6 [8]}}