| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | State initial flow value |
| Difficulty | Easy -1.2 This is a straightforward network flows question requiring basic reading of a diagram and application of standard definitions (flow conservation, saturated arcs, cut capacity). Parts (a)-(d) are direct recall/observation, (e) requires simple inspection, and (f) applies the max-flow min-cut theorem. Significantly easier than average A-level questions as it tests only basic understanding with minimal calculation. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| (a) \(x = 9, y = 11\) | B1, B1 | (2 marks) |
| Answer | Marks | Guidance |
|---|---|---|
| (b) AC DC DT ET | B2, 1, 0 | (2 marks) |
| Answer | Marks | Guidance |
|---|---|---|
| (c) 36 | B1 | (1 mark) |
| Answer | Marks | Guidance |
|---|---|---|
| (d) \(C_1 = 49, C_2 = 48, C_3 = 39\) | B1, B1, B1 | (3 marks) |
| Answer | Marks | Guidance |
|---|---|---|
| (e) e.g. SAECT | B1 | (1 mark) |
| Answer | Marks | Guidance |
|---|---|---|
| (f) maximum flow = minimum cut. cut through DT, DC, AC and AE | M1 A1 | (2 marks) |
**(a)** $x = 9, y = 11$ | B1, B1 | (2 marks) |
**Guidance:** 1B1: cao (permit B1 if 2 correct answers, but transposed). 2B1: cao
**(b)** AC DC DT ET | B2, 1, 0 | (2 marks) |
**Guidance:** 1B1: correct (condone one error – omission or extra). 2B1: all correct (no omissions or extras)
**(c)** 36 | B1 | (1 mark) |
**Guidance:** 1B1: cao
**(d)** $C_1 = 49, C_2 = 48, C_3 = 39$ | B1, B1, B1 | (3 marks) |
**Guidance:** 1B1: cao. 2B1: cao. 3B1: cao
**(e)** e.g. SAECT | B1 | (1 mark) |
**Guidance:** 1B1: A correct route (flow value of 1 given)
**(f)** maximum flow = minimum cut. cut through DT, DC, AC and AE | M1 A1 | (2 marks) |
**Guidance:** 1M1: Must have attempted (e) and made an attempt at a cut. 1A1: cut correct – may be drawn. Refer to max flow-min cut theorem. three words out of four.
**Total for Q5: 11 marks**
---5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-5_819_1421_251_322}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{center}
\end{figure}
Figure 5 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of that pipe. The numbers in circles represent a feasible flow.
\begin{enumerate}[label=(\alph*)]
\item State the values of $x$ and $y$.
\item List the saturated arcs.
\item State the value of the feasible flow.
\item State the capacities of the cuts $\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }$, and $\mathrm { C } _ { 3 }$.
\item By inspection, find a flow-augmenting route to increase the flow by one unit. You must state your route.
\item Prove that the new flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2008 Q5 [11]}}