| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2002 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Moderate -0.5 This is a standard textbook exercise on adding a supersource to a network flow problem and applying the labelling procedure (Ford-Fulkerson algorithm). While it requires multiple steps, each component is routine for D1: adding arcs with appropriate capacities, identifying simple flow-augmenting paths, and verifying maximality using a cut. The question is structured with significant scaffolding (parts a, b guide the setup) and uses a straightforward network topology. This is easier than average A-level maths questions because it's purely algorithmic application without requiring problem-solving insight or novel reasoning. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct network drawn with supersource \(S\) connected to \(F_1, F_2, F_3\) with capacities 12, 9 (direct), 12 respectively | M1 A1 | (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(SF_1ABR = 6\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(SF_3CR = 8\) | B1 | (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct flow augmentation shown with updated flows and back-flows | M1 A1 | |
| e.g. \(SF_1BR=6,\ SF_2BR=3,\ SF_2CR=3,\ SF_3R=4\) | A1 A1 | |
| Total flow \(= 30\) | A1 | (5) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Max flow – min cut theorem | M1 | |
| Cut \(BR,\ F_2C,\ F_3C,\ F_3R\) | A1 | (2) |
| (11 marks) |
# Question 7:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct network drawn with supersource $S$ connected to $F_1, F_2, F_3$ with capacities 12, 9 (direct), 12 respectively | M1 A1 | **(2)** |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $SF_1ABR = 6$ | B1 | |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $SF_3CR = 8$ | B1 | **(2)** |
## Part (c)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct flow augmentation shown with updated flows and back-flows | M1 A1 | |
| e.g. $SF_1BR=6,\ SF_2BR=3,\ SF_2CR=3,\ SF_3R=4$ | A1 A1 | |
| Total flow $= 30$ | A1 | **(5)** |
## Part (c)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Max flow – min cut theorem | M1 | |
| Cut $BR,\ F_2C,\ F_3C,\ F_3R$ | A1 | **(2)** |
| | **(11 marks)** | |7. A company wishes to transport its products from 3 factories $F _ { 1 } , F _ { 2 }$ and $F _ { 3 }$ to a single retail outlet $R$. The capacities of the possible routes, in van loads per day, are shown in Fig. 5.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-7_719_1170_590_438}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item On Diagram 1 in the answer booklet add a supersource $S$ to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
\item \begin{enumerate}[label=(\roman*)]
\item State the maximum flow along $S F _ { 1 } A B R$ and $S F _ { 3 } C R$.
\item Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles.
Taking your answer to part (b)(ii) as the initial flow pattern,
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item use the labelling procedure to find a maximum flow from $S$ to $R$. Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
\item Prove that your final flow is maximal.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2002 Q7 [11]}}