| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Moderate -0.8 This is a standard textbook application of the labelling procedure (max-flow min-cut algorithm) with straightforward steps: reading initial flow, stating cut capacities, completing a partially-done labelling table, augmenting flow along given routes, and verifying maximality. All steps are algorithmic with no novel problem-solving required, making it easier than average A-level questions. |
| Spec | 7.02p Networks: weighted graphs, modelling connections |
| Answer | Marks | Guidance |
|---|---|---|
| Initial flow \(= 41\) | B1 | (1) |
| Answer | Marks | Guidance |
|---|---|---|
| Capacity of \(C_1 = 69\) | B1 | |
| Capacity of \(C_2 = 64\) | B1 | (2) permit B1 if 2 correct answers but transposed |
| Answer | Marks | Guidance |
|---|---|---|
| Two numbers on each arc | M1 | |
| cao | A1 | (2) |
| Answer | Marks | Guidance |
|---|---|---|
| e.g. \(SBADHT - 2\) | M1, A1 | |
| \(SCGEDHT - 2\) | A1 | (3) One valid flow augmenting route S to T, value \((\leq 4)\) stated; 1A1 flow increased by at least 2; 2A1 flow increased by 4 |
| Answer | Marks | Guidance |
|---|---|---|
| maximum flow \(=\) minimum cut | DM1 | Must have attempted (d) and made attempt at a cut |
| e.g. cut through SA, SB, CE, GE, GI or HT, FI, GI | A1 | (2) cut correct – may be drawn. Refer to max flow–min cut theorem, three words out of four |
# Question 5:
## Part (a)
Initial flow $= 41$ | B1 | (1)
## Part (b)
Capacity of $C_1 = 69$ | B1 |
Capacity of $C_2 = 64$ | B1 | (2) permit B1 if 2 correct answers but transposed
## Part (c)
Two numbers on each arc | M1 |
cao | A1 | (2)
## Part (d)
e.g. $SBADHT - 2$ | M1, A1 |
$SCGEDHT - 2$ | A1 | (3) One valid flow augmenting route S to T, value $(\leq 4)$ stated; 1A1 flow increased by at least 2; 2A1 flow increased by 4
## Part (e)
maximum flow $=$ minimum cut | DM1 | Must have attempted (d) and made attempt at a cut |
e.g. cut through SA, SB, CE, GE, GI or HT, FI, GI | A1 | (2) cut correct – may be drawn. Refer to max flow–min cut theorem, three words out of four
---5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{a91f96a3-a9b4-4bf5-bfdf-93c34912e54a-6_1012_1696_233_182}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 2 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.\\
(1)
\item State the capacities of cuts $\mathrm { C } _ { 1 }$ and $\mathrm { C } _ { 2 }$.\\
(2)
\item By entering values along DH, FH, FI and IT, complete the labelling procedure on Diagram 1 in the answer book.\\
(2)
\item Using Diagram 1, increase the flow by a further 4 units. You must list each flow-augmenting route you use, together with its flow.\\
(3)
\item Prove that the flow is now maximal.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2010 Q5 [10]}}