| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Standard +0.3 This is a structured, multi-part network flows question with clear guidance at each step. Part (a) is routine application of supersource/supersink concepts, parts (b-d) follow standard max-flow algorithm procedures with the target value given, and part (e) requires a min-cut proof which is a standard technique. While it has many marks (14), the question scaffolds the solution heavily and uses well-practiced D2 algorithms rather than requiring novel problem-solving insight. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct flow diagram with labelled flows and directions | M1A1, A1 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(\underline{103}\) | B1 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. \(SBEGILT-3\); \(SBEDFKT-5\); \(SBEHJGDFKT-4\); \(SBEGDFILT-9\) | M1, A4,3,2,1,0 | 5 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct network diagram with flow value \(\underline{124}\) (given) | M1A1, A1 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Max flow \(=\) min cut; cut through \(\underline{AB, BD, DE, EG, HJ}\) | M1A1 | 2 |
# Question 5:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct flow diagram with labelled flows and directions | M1A1, A1 | 3 |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $\underline{103}$ | B1 | 1 |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. $SBEGILT-3$; $SBEDFKT-5$; $SBEHJGDFKT-4$; $SBEGDFILT-9$ | M1, A4,3,2,1,0 | 5 |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct network diagram with flow value $\underline{124}$ (given) | M1A1, A1 | 3 |
## Part (e)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Max flow $=$ min cut; cut through $\underline{AB, BD, DE, EG, HJ}$ | M1A1 | 2 |
---5.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-3_1026_1609_772_169}
\end{center}
\end{figure}
In solving a network flow problem using the labelling procedure, the diagram in Figure 1 was created.\\
The arrow on each arc indicates the direction of the flow along that arc.\\
The arrows above and below each arc show the direction and value of the flow as indicated by the labelling procedure.
\begin{enumerate}[label=(\alph*)]
\item Add a supersource S , a supersink T and appropriate arcs to the diagram above, and complete the labelling procedure for these arcs.
\item Write down the value of the initial flow shown in Figure 1.
\item Use Figure 2 below, the initial flow and the labelling procedure to find the maximal flow of 124 through this network. List each flow-augmenting path you use, together with its flow.
\item Show your flow on the diagram below and state its value.\\
\includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-4_967_1520_114_214}
\item Prove that your flow is maximal.\\
(2)\\
(Total 14 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2007 Q5 [14]}}