| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| 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 following the labelling procedure algorithm taught in the module. While it has multiple parts and 14 marks, each step follows a well-defined algorithmic procedure with no novel problem-solving required. The supersource/supersink addition is routine, finding flow-augmenting paths is mechanical application of the taught method, and proving maximality uses the standard max-flow min-cut theorem. Slightly easier than average due to its algorithmic nature. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks |
|---|---|
| [Diagrams showing tree structures with labeled branches] | M1, A1, A1 (3) |
| Answer | Marks |
|---|---|
| \(\frac{103}{...}\) | B1 (1) |
| Answer | Marks |
|---|---|
| e.g. \(SEGTLT - 3\), \(SEOIHT - 5\), \(SBEHJEDKT - 4\), \(SBEGOFILIT - 9\) | M1, A1, pppj, (5) |
| Answer | Marks |
|---|---|
| [Diagram 3 showing network with flow values] | M1, A1, A1 (3) |
| Answer | Marks |
|---|---|
| Flow value = 124 lg/sec / Max flow = min cut through AB, BD, DE, EG, HJ | M1, A1 (2), [16] |
## 8(a)
| [Diagrams showing tree structures with labeled branches] | M1, A1, A1 (3) |
## 8(b)
| $\frac{103}{...}$ | B1 (1) |
## 8(c)
| e.g. $SEGTLT - 3$, $SEOIHT - 5$, $SBEHJEDKT - 4$, $SBEGOFILIT - 9$ | M1, A1, pppj, (5) |
## 8(d)
| [Diagram 3 showing network with flow values] | M1, A1, A1 (3) |
## 8(e)
| Flow value = 124 lg/sec / Max flow = min cut through AB, BD, DE, EG, HJ | M1, A1 (2), [16] |\includegraphics{figure_7}
In solving a network flow problem using the labelling procedure, the diagram in Figure 7 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 Diagram 2 in the answer book, and complete the labelling procedure for these arcs. (3)
\item Write down the value of the initial flow shown in Figure 7. (1)
\item Use Diagram 2, 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. (5)
\item Show your flow on Diagram 3 and state its value. (3)
\item Prove that your flow is maximal. (2)
\end{enumerate}
(Total 14 marks)
\hfill \mbox{\textit{Edexcel D1 2007 Q8}}