| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Find missing flow values |
| Difficulty | Standard +0.3 This is a standard D1 network flows question requiring application of the labelling procedure and max-flow min-cut theorem. While it involves multiple parts and systematic working, these are routine algorithmic procedures taught directly in the specification with no novel problem-solving required. The conceptual demand is low compared to typical A-level pure maths questions. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | \(x = 2, y = 14\) | M2 A1 |
| (b) (i) | e.g. augment \(SC7\) by 2 and \(SBECADT\) by 3 | |
| (b) (ii) | Diagram showing augmentations with maximum flow = 53 | M3 A3, A1 |
| (c) (i) | minimum cut = 53, passing through \(DT\), \(CT\) and \(ET\) | B1 |
| (c) (ii) | max flow = min cut; it is not possible to get any more flow across this cut | B1 |
**(a)** | $x = 2, y = 14$ | M2 A1 | |
**(b) (i)** | e.g. augment $SC7$ by 2 and $SBECADT$ by 3 | | |
**(b) (ii)** | Diagram showing augmentations with maximum flow = 53 | M3 A3, A1 | |
**(c) (i)** | minimum cut = 53, passing through $DT$, $CT$ and $ET$ | B1 | |
**(c) (ii)** | max flow = min cut; it is not possible to get any more flow across this cut | B1 | (11) |3. This question should be answered on the sheet provided.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-04_883_1317_317_315}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{center}
\end{figure}
Figure 2 shows a capacitated, directed network.\\
The numbers in bold denote the capacities of each arc.\\
The numbers in circles show a feasible flow of 48 through the network.
\begin{enumerate}[label=(\alph*)]
\item Find the values of $x$ and $y$.
\item \begin{enumerate}[label=(\roman*)]
\item Use the labelling procedure to find the maximum flow through this network, listing each flow-augmenting route you use together with its flow.
\item Show your maximum flow pattern and state its value.
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item Find a minimum cut, listing the arcs through which it passes.
\item Explain why this proves that the flow found in part (b) is a maximum.\\
(2 marks)
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q3 [11]}}