| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | State initial flow value |
| Difficulty | Easy -1.2 Part (a) asks students to simply read and sum the flow values shown in circles on the diagram - this is pure observation requiring no calculation or problem-solving. While the full question involves flow augmentation and max-flow min-cut theorem (standard D2 content), this specific part is trivial recall/observation, significantly easier than average A-level questions. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(85\) | B1 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(c_1 = 140,\ c_2 = 104\) | B1, B1 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. \(S\ B\ D\ F\ H\ J\ T\ -4\); \(S\ B\ D\ F\ G\ T\ -1\); \(S\ B\ D\ F\ C\ H\ I\ T\ -2\); \(S\ B\ D\ F\ C\ H\ J\ T\ -2\); \(S\ B\ D\ E\ G\ T\ -10\) | M1A1, A1, A1, A1 | 5 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Max flow – min cut theorem; flow is \(104\), min cut is \(c_2\) | M1A1 | 2 |
# Question 9:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $85$ | B1 | 1 |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $c_1 = 140,\ c_2 = 104$ | B1, B1 | 2 |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. $S\ B\ D\ F\ H\ J\ T\ -4$; $S\ B\ D\ F\ G\ T\ -1$; $S\ B\ D\ F\ C\ H\ I\ T\ -2$; $S\ B\ D\ F\ C\ H\ J\ T\ -2$; $S\ B\ D\ E\ G\ T\ -10$ | M1A1, A1, A1, A1 | 5 |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Max flow – min cut theorem; flow is $104$, min cut is $c_2$ | M1A1 | 2 |9.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-7_931_1651_196_118}
\captionsetup{labelformat=empty}
\caption{Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item State the value of the initial flow.
\item State the capacities of cuts $\mathrm { C } _ { 1 }$ and $\mathrm { C } _ { 2 }$.
Figure 2 shows the labelling procedure applied to the above network.
\item Using Figure 2, increase the flow by a further 19 units. You must list each flow-augmenting path you use, together with its flow.
\item Prove that the flow is now maximal.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-8_2146_1038_127_422}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2007 Q9 [10]}}