| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Calculate cut capacity |
| Difficulty | Standard +0.3 This is a standard D1 network flows question testing routine application of cut capacity calculations and the labelling procedure algorithm. Part (a) requires simple addition of arc capacities across given cuts, (b) is straightforward comparison, (c) involves reading values from a diagram using flow conservation, and (d) is methodical application of a learned algorithm. While multi-part with 10 marks total, each step follows textbook procedures with no novel problem-solving required, making it slightly easier than average. |
| Spec | 7.02r Graph modelling: model and solve problems using graphs |
| Answer | Marks | Guidance |
|---|---|---|
| (a) \(C_1 = 80; C_2 = 94\) | A2 | |
| (b) Minimum cut: \(\{S, A, B, C, D, F\} \mid \{E, T\} = 57\) | M1 A1 | |
| (c) \(x = 15, y = 10, z = 36\) | A3 | |
| (d) Augment SCET by 2 and SCAET by 1 giving maximum flow below | M4 A3 | |
| This is maximum flow as it is equal to the minimum cut | B1 | (15) |
**(a)** $C_1 = 80; C_2 = 94$ | A2 |
**(b)** Minimum cut: $\{S, A, B, C, D, F\} \mid \{E, T\} = 57$ | M1 A1 |
**(c)** $x = 15, y = 10, z = 36$ | A3 |
**(d)** Augment SCET by 2 and SCAET by 1 giving maximum flow below | M4 A3 |
This is maximum flow as it is equal to the minimum cut | B1 | (15)
---6. This question should be answered on the sheet provided.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-06_723_1292_276_349}
\captionsetup{labelformat=empty}
\caption{Fig. 4}
\end{center}
\end{figure}
Figure 4 above shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.
\begin{enumerate}[label=(\alph*)]
\item Calculate the values of cut $C _ { 1 }$ and $C _ { 2 }$.
\item Find the minimum cut and state its value.\\
(2 marks)
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-06_647_1303_1430_347}
\captionsetup{labelformat=empty}
\caption{Fig. 5}
\end{center}
\end{figure}
Figure 5 shows a feasible flow through the same network.
\item State the values of $x , y$ and $z$.
\item Using this as your initial flow pattern, use the labelling procedure to find a maximal flow. You should list each flow-augmenting route you use together with its flow.
State how you know that you have found a maximal flow.\\
(8 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q6 [15]}}