| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2001 |
| Session | January |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | State maximum flow along specific routes |
| Difficulty | Moderate -0.3 This is a standard max-flow/min-cut algorithm question from D1, requiring straightforward application of the labelling procedure. Parts (a)-(b) involve simple path identification, part (c) is routine algorithmic execution, and part (e) requires stating a min-cut—all textbook exercises with no novel problem-solving required. However, it's multi-step with 14 marks total, preventing it from being significantly below average. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | B1 cae | (i) SAET: 5 |
| B1 cae | (ii) SBDT: 4 | |
| B1 cae(3) | (iii) SCFT: 3 | |
| (b) | B1(1) | Diagram 1 showing network with capacities |
| (c) | M1 | Diagram 2 showing residual capacities with forward and backward flows |
| M1 A1(3) |
| Answer | Marks | Guidance |
|---|---|---|
| B1 | S.A.D.T. flow 2 | |
| B1 | S.C.F.E.A.D.T. flow 2 | |
| A1(6) | Total flow: \(12 + 2 + 2 = 16\) | |
| (d) | M1 A1(2) | Diagram 3 showing final flow allocation with saturated edges |
| There is a cut of capacity 16 consisting of {E.T., F.T., A.D., and B.D.}. | ||
| [A]B: E.T. is saturated and F.T. is saturated. Only possible route to T is then D.T. But as A.D. and B.D. are saturated no flow in to D is possible |
(a) | B1 cae | (i) SAET: 5 |
| B1 cae | (ii) SBDT: 4 |
| B1 cae(3) | (iii) SCFT: 3 |
(b) | B1(1) | Diagram 1 showing network with capacities |
(c) | M1 | Diagram 2 showing residual capacities with forward and backward flows |
| M1 A1(3) | |
Flow augmenting routes:
| B1 | S.A.D.T. flow 2 |
| B1 | S.C.F.E.A.D.T. flow 2 |
| A1(6) | Total flow: $12 + 2 + 2 = 16$ |
(d) | M1 A1(2) | Diagram 3 showing final flow allocation with saturated edges |
| | There is a cut of capacity 16 consisting of {E.T., F.T., A.D., and B.D.}. |
| | [A]B: E.T. is saturated and F.T. is saturated. Only possible route to T is then D.T. But as A.D. and B.D. are saturated no flow in to D is possible |
---This question should be answered on the sheet provided in the answer booklet.
\includegraphics{figure_3}
Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.
\begin{enumerate}[label=(\alph*)]
\item State the maximum flow along
\begin{enumerate}[label=(\roman*)]
\item SAET,
\item SBDT,
\item SCFT.
\end{enumerate}
[3 marks]
\item Show these maximum flows on Diagram 1 on the answer sheet. [1 mark]
\item Taking your answer to part (b) as the initial flow pattern, use the labelling procedure to find a maximum flow from S to T. Your working should be shown on Diagram 2. List each flow augmenting route you find, together with its flow. [6 marks]
\item Indicate a maximum flow on Diagram 3. [2 marks]
\item Prove that your flow is maximal. [2 marks]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2001 Q6 [14]}}