| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Session | Specimen |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Find missing flow values |
| Difficulty | Standard +0.3 This is a standard network flows question requiring application of conservation of flow at nodes to find missing values, identification of flow-augmenting paths, and verification using max-flow min-cut theorem. While it's a Further Maths topic (inherently harder), the techniques are algorithmic and well-practiced, requiring minimal novel insight—slightly easier than average A-level difficulty overall. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Corridors must be one-way | B1 | Explanation of assumption to use this model |
| Answer | Marks | Guidance |
|---|---|---|
| e.g. \(55 + x + 40 = 63 + 54 + 24\) or \(7 + y = 54 + 5\) | M1 | Either a correct equation, or explanation that flow in = flow out |
| \(x = 46\) | A1 | cao |
| \(y = 52\) | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| SACET \((= 5)\), SDFET \((= 5)\) | M1, A1 | One flow augmenting route found S to T; two correct flow augmenting routes \(5+\) |
| Answer | Marks | Guidance |
|---|---|---|
| Students must choose SACET, as they cannot travel from F to E | A1 | Deduce that SACET must be used as students cannot travel from F to E as route is one-way |
| Answer | Marks | Guidance |
|---|---|---|
| Consistent flow pattern \(= 151\) (diagram) | B1 | A consistent flow pattern \(= 151\) |
| Answer | Marks | Guidance |
|---|---|---|
| Use of max-flow min-cut theorem | M1 | Constructing argument based on max-flow min-cut theorem |
| Identification of cut through AC, DC, DE, (EF), FT \(= 151\); value of flow \(= 151\) | A1 | Use appropriate process of finding a minimum cut – cut + value correct |
| Therefore it follows that flow is optimal | A1 | Correct deduction that the flow is maximal |
| Answer | Marks | Guidance |
|---|---|---|
| Consider increasing capacity of arcs in minimum cut | B1 | Constructing an argument based on arcs in the minimum cut |
| Increasing capacity of any arc other than FT would not increase flow by more than 1, as total capacity directly into T is only 152; increasing capacity on FT could increase total flow by 16 (increased flow along SAD, SD and SBD could all be directed through DF to F) | B1 | Detailed explanation as to why choosing anything other than FT does not help |
| Therefore school should choose to widen FT, which could increase the flow through the network by 16 | B1 | Correct deduction and correct increase in flow of 16 |
## Question 3:
### Part (a):
| Corridors must be one-way | B1 | Explanation of assumption to use this model |
### Part (b):
| e.g. $55 + x + 40 = 63 + 54 + 24$ or $7 + y = 54 + 5$ | M1 | Either a correct equation, or explanation that flow in = flow out |
| $x = 46$ | A1 | cao |
| $y = 52$ | A1 | cao |
### Part (c)(i):
| SACET $(= 5)$, SDFET $(= 5)$ | M1, A1 | One flow augmenting route found S to T; two correct flow augmenting routes $5+$ |
### Part (c)(ii):
| Students must choose SACET, as they cannot travel from F to E | A1 | Deduce that SACET must be used as students cannot travel from F to E as route is one-way |
### Part (d):
| Consistent flow pattern $= 151$ (diagram) | B1 | A consistent flow pattern $= 151$ |
### Part (e):
| Use of max-flow min-cut theorem | M1 | Constructing argument based on max-flow min-cut theorem |
| Identification of cut through AC, DC, DE, (EF), FT $= 151$; value of flow $= 151$ | A1 | Use appropriate process of finding a minimum cut – cut + value correct |
| Therefore it follows that flow is optimal | A1 | Correct deduction that the flow is maximal |
### Part (f):
| Consider increasing capacity of arcs in minimum cut | B1 | Constructing an argument based on arcs in the minimum cut |
| Increasing capacity of any arc other than FT would not increase flow by more than 1, as total capacity directly into T is only 152; increasing capacity on FT could increase total flow by 16 (increased flow along SAD, SD and SBD could all be directed through DF to F) | B1 | Detailed explanation as to why choosing anything other than FT does not help |
| Therefore school should choose to widen FT, which could increase the flow through the network by 16 | B1 | Correct deduction and correct increase in flow of 16 |
---3.
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{81510c1c-89ce-4fa8-aa1b-3c8b255804cc-4_2255_54_315_34}
\end{center}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{81510c1c-89ce-4fa8-aa1b-3c8b255804cc-4_913_1783_287_139}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{center}
\end{figure}
Figure 5 represents a network of corridors in a school. The number on each arc represents the maximum number of students, per minute, that may pass along each corridor at any one time. At 11 am on Friday morning, all students leave the hall (S) after assembly and travel to the cybercafé ( T ). The numbers in circles represent the initial flow of students recorded at 11 am one Friday.
\begin{enumerate}[label=(\alph*)]
\item State an assumption that has been made about the corridors in order for this situation to be modelled by a directed network.
\item Find the value of x and the value of y , explaining your reasoning.
Five new students also attend the assembly in the hall the following Friday. They too need to travel to the cybercafé at 11 am . They wish to travel together so that they do not get lost. You may assume that the initial flow of students through the network is the same as that shown in Figure 5 above.
\item \begin{enumerate}[label=(\roman*)]
\item List all the flow augmenting routes from S to T that increase the flow by at least 5
\item State which route the new students should take, giving a reason for your answer.
\end{enumerate}\item Use the answer to part (c) to find a maximum flow pattern for this network and draw it on Diagram 1 in the answer book.
\item Prove that the answer to part (d) is optimal.
The school is intending to increase the number of students it takes but has been informed it cannot do so until it improves the flow of students at peak times. The school can widen corridors to increase their capacity, but can only afford to widen one corridor in the coming term.
\item State, explaining your reasoning,
\begin{enumerate}[label=(\roman*)]
\item which corridor they should widen,
\item the resulting increase of flow through the network.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 AS Q3 [14]}}