| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Standard +0.3 This is a standard D1 network flows question following the textbook algorithm (labelling procedure/max-flow min-cut). While multi-part with 16 marks, it requires systematic application of a well-defined procedure rather than problem-solving insight. The supersource/supersink addition and proving maximality via min-cut are routine exam techniques. Slightly above average due to length and bookwork, but fundamentally algorithmic. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks |
|---|---|
| \(S S_1 - 47\), \(S S_2 - 87\), \(T, T - 51\), \(T_2 T - 73\) added to diagram 1 | M1, A1 |
| Answer | Marks |
|---|---|
| \(SS_1 \xrightarrow{°}47\), \(SS_2 \xleftarrow{38}49\), \(T, T \xrightarrow{8}43\), \(T_2 T \xrightarrow{20}52\) | M1, A1 |
| Answer | Marks | Guidance |
|---|---|---|
| e.g. \(S S_c A\) P−T, T − 2; \(S S_L e\) T: T − 1; \(S S_L e\) D T: T − 10; \(S S_L c e\) B D T: T − 4. Maximum flow − 113 | M1, A4, 3, 2, 1, 0, (B1) |
| Answer | Marks |
|---|---|
| Example network diagram with flows shown | M1, A1 |
| Answer | Marks | Guidance |
|---|---|---|
| max flow - min cut theorem; cut A T, A D, S₁ B, S₂ B, GE, CF | (m1) A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Idea of a directed flow along arcs; from s to T; thourgh alpsystem; pacluses included | B2, 1, 0 |
## Part (a)
| $S S_1 - 47$, $S S_2 - 87$, $T, T - 51$, $T_2 T - 73$ added to diagram 1 | M1, A1 | |
## Part (b)
| $SS_1 \xrightarrow{°}47$, $SS_2 \xleftarrow{38}49$, $T, T \xrightarrow{8}43$, $T_2 T \xrightarrow{20}52$ | M1, A1 | |
## Part (c)
| e.g. $S S_c A$ P−T, T − 2; $S S_L e$ T: T − 1; $S S_L e$ D T: T − 10; $S S_L c e$ B D T: T − 4. Maximum flow − 113 | | M1, A4, 3, 2, 1, 0, (B1) |
## Part (d)
| Example network diagram with flows shown | M1, A1 | |
## Part (e)
| max flow - min cut theorem; cut A T, A D, S₁ B, S₂ B, GE, CF | | (m1) A1 |
## Part (f)
| Idea of a directed flow along arcs; from s to T; thourgh alpsystem; pacluses included | | B2, 1, 0 |
---\includegraphics{figure_6}
Figure 6 shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow through the network. Take this as the initial flow.
\begin{enumerate}[label=(\alph*)]
\item On Diagram 1 and Diagram 2 in the answer book, add a supersource $S$ and a supersink $T$. On Diagram 1 show the minimum capacities of the arcs you have added. [2]
\end{enumerate}
Diagram 2 in the answer book shows the first stage of the labelling procedure for the given initial flow.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item Complete the initial labelling procedure in Diagram 2. [2]
\item Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow, and state the maximal flow. [6]
\item Show a maximal flow pattern on Diagram 3. [2]
\item Prove that your flow is maximal. [2]
\item Describe briefly a situation for which this network could be a suitable model. [2]
\end{enumerate}
(Total 16 marks)
\hfill \mbox{\textit{Edexcel D1 2005 Q8 [16]}}