| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2018 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Moderate -0.3 This is a standard textbook application of the labelling procedure (max-flow min-cut algorithm) in network flows. Parts (a)-(f) are routine algorithmic steps requiring careful bookkeeping but no novel insight—calculating cut capacity, applying a well-defined procedure, and verifying optimality. While multi-part with several marks, it's methodical execution of a taught algorithm, making it slightly easier than average A-level maths questions. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Cut capacity \(= 3 + 11 + 4 + 5 + 1 + 6 = 30\) (sum of forward arc capacities through the cut) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Arc GT has capacity 3; the total flow into G can never exceed 3 (from arcs DG and EG), so GT can never carry full capacity of 3... or equivalent argument about incoming flow being limited | B1 | Must give valid reason referencing arc capacities |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| SBET: excess capacities checked along route | M1 | |
| Maximum flow along SBET \(= \min(5, 11, 5) = 5\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Flow-augmenting routes listed with flows, e.g. SBET: 5, SADGT: 3, SCFH T: 5, SBFHT: additional flow etc. | M1 | At least 2 valid routes with flows |
| All routes and flows correct | A1A1A1 | One mark per correct route/flow up to 4 marks total |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Maximum flow stated (e.g. 19 or value consistent with working) | B1 | |
| Cut identified with same capacity as max flow | B1 | Must verify cut capacity equals max flow |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Diagram correctly showing all arc flows consistent with max flow | B1B1 | One mark for correct flows on at least half the arcs; second for fully correct diagram |
# Question 4:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Cut capacity $= 3 + 11 + 4 + 5 + 1 + 6 = 30$ (sum of forward arc capacities through the cut) | B1 | |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Arc GT has capacity 3; the total flow into G can never exceed 3 (from arcs DG and EG), so GT can never carry full capacity of 3... or equivalent argument about incoming flow being limited | B1 | Must give valid reason referencing arc capacities |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| SBET: excess capacities checked along route | M1 | |
| Maximum flow along SBET $= \min(5, 11, 5) = 5$ | A1 | |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| Flow-augmenting routes listed with flows, e.g. SBET: 5, SADGT: 3, SCFH T: 5, SBFHT: additional flow etc. | M1 | At least 2 valid routes with flows |
| All routes and flows correct | A1A1A1 | One mark per correct route/flow up to 4 marks total |
## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| Maximum flow stated (e.g. 19 or value consistent with working) | B1 | |
| Cut identified with same capacity as max flow | B1 | Must verify cut capacity equals max flow |
## Part (f)
| Answer | Mark | Guidance |
|--------|------|----------|
| Diagram correctly showing all arc flows consistent with max flow | B1B1 | One mark for correct flows on at least half the arcs; second for fully correct diagram |
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4abb2325-b9df-4849-b08c-7db465fe85e0-05_1054_1569_194_248}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 represents a system of pipes through which fluid can flow from the source node, S , to the sink node, T. The labelling procedure has been applied to Figure 1, and the numbers on the arrows, either side of each arc, show the excess capacities and potential backflows.
Currently, no fluid is flowing through the system.
\begin{enumerate}[label=(\alph*)]
\item Calculate the capacity of the cut that passes through arcs $\mathrm { GT } , \mathrm { EG } , \mathrm { DE } , \mathrm { BE } , \mathrm { FE }$ and FH .
\item Explain why arc GT can never be full to capacity when fluid is flowing through the system.
\item Apply the labelling procedure to Diagram 1 in the answer book to show the maximum flow along SBET. State the amount that can flow along this route.
\item Use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
\item State the maximum flow through the system and find a cut to show that this flow is maximal.
\item Show the maximum flow on Diagram 2 in the answer book.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2018 Q4 [12]}}