| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2003 |
| Session | November |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Standard +0.3 This is a standard D1 network flows question requiring routine application of the labelling procedure algorithm. Parts (a) and (b) involve basic flow conservation and standard supersource/supersink setup, while parts (c)-(e) follow textbook procedures for finding maximum flow and verifying with a cut. The question is slightly easier than average as it provides an initial flow and follows a structured, algorithmic approach with no novel problem-solving required. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| \(x=3,\ y=26\) | B1, B1 | (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Network diagram with flows: \(S \to F_1 = 42\), \(F_1 \to R_1 = 47\), \(R_1 \to T\); \(S \to F_2 = 41\), \(F_2 \to R_3\); \(R_2 \to T = 32\), \(R_3 \to T = 10\) | M1, A1, A1 | (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Labelled flow diagram as shown | M1, A1, A1 | (3) |
| e.g. \(S\ F_1\ A\ E\ R_1\ T - 7\) | DM1 | |
| \(S\ F_1\ B\ E\ R_1\ T - 5\) | A1 | |
| \(S\ F_1\ B\ G\ R_1\ T - 1\) | A1 | |
| \(S\ F_2\ C\ D\ B\ G\ R_2\ T - 4\) | A1 | (4) |
| Answer | Marks | Guidance |
|---|---|---|
| Network diagram with flows as shown, edges: 19, 32, 13, 15, 8, 8, 6, 12, 21, 25, 12, 10, 30, 10, 7 | B1 | |
| Max Flow \(= 82\) | B1 | (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Or \(ER_1\), BG, CG, \(CR_2\), \(CR_3\) \((=82)\) | M1, A1 | (2) |
# Question 7:
## Part (a)
$x=3,\ y=26$ | B1, B1 | (2)
## Part (b)
Network diagram with flows: $S \to F_1 = 42$, $F_1 \to R_1 = 47$, $R_1 \to T$; $S \to F_2 = 41$, $F_2 \to R_3$; $R_2 \to T = 32$, $R_3 \to T = 10$ | M1, A1, A1 | (3)
## Part (c)
Labelled flow diagram as shown | M1, A1, A1 | (3)
e.g. $S\ F_1\ A\ E\ R_1\ T - 7$ | DM1 |
$S\ F_1\ B\ E\ R_1\ T - 5$ | A1 |
$S\ F_1\ B\ G\ R_1\ T - 1$ | A1 |
$S\ F_2\ C\ D\ B\ G\ R_2\ T - 4$ | A1 | (4)
## Part (d)
Network diagram with flows as shown, edges: 19, 32, 13, 15, 8, 8, 6, 12, 21, 25, 12, 10, 30, 10, 7 | B1 |
Max Flow $= 82$ | B1 | (2)
## Part (e)
$F_1$: A, BE, BG, CG, $CR_2$, $CR_3$ $(=82)$
Or $ER_1$, BG, CG, $CR_2$, $CR_3$ $(=82)$ | M1, A1 | (2)
**Total: 16 marks**
---7.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 6}
\includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-10_1018_1557_342_214}
\end{center}
\end{figure}
Figure 6 shows a capacitated, directed network of pipes flowing from two oil fields $\mathrm { F } _ { 1 }$ and $\mathrm { F } _ { 2 }$ to three refineries $\mathrm { R } _ { 1 } , \mathrm { R } _ { 2 }$ and $\mathrm { R } _ { 3 }$. The number on each arc represents the capacity of the pipe and the numbers in the circles represent a possible flow of 65.
\begin{enumerate}[label=(\alph*)]
\item Find the value of $x$ and the value of $y$.
\item On Diagram 1 in the answer book, add a supersource and a supersink, and arcs showing their minimum capacities.
\item Taking the given flow of 65 as the initial flow pattern, use the labelling procedure on Diagram 2 to find the maximum flow. State clearly your flow augmenting routes.
\item Show the maximum flow on Diagram 3 and write down its value.
\item Verify that this is the maximum flow by finding a cut equal to the flow.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2003 Q7 [16]}}