| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Apply labelling procedure for max flow |
| Difficulty | Standard +0.3 This is a standard application of the max-flow labelling procedure from Decision Maths 2, requiring routine execution of a well-defined algorithm with minimal problem-solving. The question guides students through each step (initial flow, cut capacity, augmenting paths, proving maximality via min-cut), making it slightly easier than average but still requiring careful bookwork and understanding of the max-flow min-cut theorem. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| (a) Initial flow = 44 | B1 | (1) |
| (b) Value of cut = \(12+7+4+10+2+5+31 = 71\) | B1 (2) | (2) |
| Answer | Marks | Guidance |
|---|---|---|
| e.g. SACFHT – 3; SADFHT – 2; SADGIT – 2; SBEDGIT – 2 | 1M1A1;A1 A1 | (4) |
| (d) e.g. [diagram showing minimum cut through the network] | M1A1 | (2) |
| Answer | Marks | Guidance |
|---|---|---|
| SA +7, SB +2, AC +3, AD +4, BD none, BE +2, ED +2, CH none, CF +3, EG none, EI none, DF+2, DG+2, FH +5, FT none, FI none, GI +4, HT +5, IT +4) | DM1 A1 | (2) Total 10 |
**(a)** Initial flow = 44 | B1 | (1)
**(b)** Value of cut = $12+7+4+10+2+5+31 = 71$ | B1 (2) | (2)
**(c)** e.g. SACFHT – 3; SADGIT – 4; SBEDFHT – 2
e.g. SACFHT – 3; SADFHT – 2; SADGIT – 2; SBEDGIT – 2 | 1M1A1;A1 A1 | (4)
**(d)** e.g. [diagram showing minimum cut through the network] | M1A1 | (2)
**(e)** Maximum flow=minimum cut
e.g. cut through CH, CF, AD, BD, DE, EG and EI
a1B1 CAO
b1B1 CAO
c1M1 One valid flow augmenting route found and a value stated.
c1A1 Flow increased by at least 2
c2A1 A second correct flow route (and value at least 2) correct
c3A1 CSO Flow increased by 9 and no more.
d1M1 Consistent flow pattern > 50 (check each node, must have exactly 1 number per arc)
d1A1 CAO, showing flow of 53, must follow from their routes.
e1DM1 Must have attempted (d) and made an attempt at a cut.
e1A1 cut correct – may be drawn. Refer to max flow-min cut theorem all four words (alternative cut: CH, CF, AD, BD, BE).
Guidance for 3(c):
SA +7, SB +2, AC +3, AD +4, BD none, BE +2, ED +2, CH none, CF +3, EG none, EI none, DF+2, DG+2, FH +5, FT none, FI none, GI +4, HT +5, IT +4) | DM1 A1 | (2) Total 10
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{f3feef8a-32ba-4234-a5fa-cdd26ef6967d-4_778_1420_262_360}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.
\begin{enumerate}[label=(\alph*)]
\item State the value of the initial flow.
\item State the capacity of cut $\mathrm { C } _ { 1 }$.
The labelling procedure has been used and the result drawn on Diagram 1 in the answer book.
\item Use Diagram 1 to find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.\\
(4)
\item Draw a maximum flow pattern on Diagram 2 in your answer book.\\
(2)
\item Prove that the flow shown in (d) is maximal.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2013 Q3 [10]}}