| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| Session | June |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Calculate cut capacity |
| Difficulty | Moderate -0.5 This is a standard network flows question requiring routine application of the max-flow min-cut algorithm. Part (a) involves straightforward calculation of cut capacities by summing arc capacities crossing the cuts, while part (b) requires finding flow-augmenting paths—a mechanical procedure taught in D2. The question is slightly easier than average A-level standard because it's a direct application of a taught algorithm with no novel problem-solving required, though it does require careful bookkeeping. |
| Spec | 7.02p Networks: weighted graphs, modelling connections |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | Value of cut \(C_1 = 34\); Value of cut \(C_2 = 45\) | B1; B1 (2) |
| (b) | S B F E G T or S B F E E T – value 2; Maximum flow \(= 28\) | M1 A1 A1;B1 (3) |
(a) | Value of cut $C_1 = 34$; Value of cut $C_2 = 45$ | B1; B1 (2) | cao |
(b) | S B F E G T or S B F E E T – value 2; Maximum flow $= 28$ | M1 A1 A1;B1 (3) | Feasible flow-augmenting route and a value stated; correct flow-augmenting route and value; 1A1 = B1: cao |
**Total [5]**
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4002eb3f-9d7e-40a1-8fd4-5a271d14c8e7-5_888_1607_248_228}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 shows a capacitated network. The capacity of each arc is shown on the arc. The numbers in circles represent an initial flow from S to T .
Two cuts $\mathrm { C } _ { 1 }$ and $\mathrm { C } _ { 2 }$ are shown in Figure 1.
\begin{enumerate}[label=(\alph*)]
\item Find the capacity of each of the two cuts.\\
(2)
\item Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.\\
(3)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2009 Q4 [5]}}