| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2019 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Standard +0.3 This is a standard D2 network flows question following a well-rehearsed algorithm. Students add supersource/supersink (routine procedure), apply labelling procedure (algorithmic), and verify maximality using min-cut theorem (standard proof). While multi-part with several marks, it requires executing learned procedures rather than problem-solving or insight, making it slightly easier than average. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Initial flow \(= 86\) | B1 (1) | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Five arcs added \(SS_1\), \(SS_2\), \(SS_3\), \(T_1T\) and \(T_2T\) with 2 numbers on each arc | M1 | Five arcs added with at least the values shown |
| Two correct arcs (flow values and capacities) consistent with their values | A1 | |
| CAO for flow values and capacities (including arrows) consistent with their values | A1 (3) |
| Answer | Marks |
|---|---|
| Two numbers on each arc and at least three arcs or six numbers correct | M1 |
| CAO — do give bod since they might well cross these numbers out | A1 (2) |
| Answer | Marks | Guidance |
|---|---|---|
| \(SS_1AT_1T - 3\) or \(SS_1AT_1T\ \ 3\) | M1A1 | One valid flow augmenting route found and a value stated |
| \(SS_1BDT_1T - 3\), \(SS_1BDT_1T\ \ 3\) | A1 | A second correct flow route |
| \(SS_2CET_2T - 2\), \(SS_2BET_2T\ \ 1\) | A1 | Three correct flow routes with correct value stated |
| \(SS_3CFT_2T - 4\), \(SS_2CET_2T\ \ 1\) | CSO flow increased by 12 and no more | |
| \(SS_3CFT_2T\ \ 4\) | (4) |
| Answer | Marks |
|---|---|
| Consistent flow pattern \(\geq 93\) (check each node), one number only per arc, no unnumbered arcs | M1 |
| CAO, showing flow of 98, must follow from their routes | A1 (2) |
| Answer | Marks | Guidance |
|---|---|---|
| The cut through \(S_1A\), \(BD\), \(DE\), \(ET_2\), \(EF\), \(CF\) and \(S_3F\) has value of 98 | DB1 | Must have attempted (e) — at least one number on all but one arc, and made an attempt at a cut |
| Value of the flow is 98 so by max flow – min cut theorem flow is maximal | DB1 (2) | CSO — (e) fully correct showing flow of 98 and correct cut. Must refer to max flow–min cut theorem — all four words |
# Question 6:
## Part (a):
| Initial flow $= 86$ | B1 (1) | CAO |
## Part (b):
| Five arcs added $SS_1$, $SS_2$, $SS_3$, $T_1T$ and $T_2T$ with 2 numbers on each arc | M1 | Five arcs added with at least the values shown |
| Two correct arcs (flow values and capacities) consistent with their values | A1 | |
| CAO for flow values and capacities (including arrows) consistent with their values | A1 (3) | |
## Part (c):
| Two numbers on each arc and at least three arcs or six numbers correct | M1 | |
| CAO — do give bod since they might well cross these numbers out | A1 (2) | |
## Part (d):
| $SS_1AT_1T - 3$ or $SS_1AT_1T\ \ 3$ | M1A1 | One valid flow augmenting route found and a value stated |
| $SS_1BDT_1T - 3$, $SS_1BDT_1T\ \ 3$ | A1 | A second correct flow route |
| $SS_2CET_2T - 2$, $SS_2BET_2T\ \ 1$ | A1 | Three correct flow routes with correct value stated |
| $SS_3CFT_2T - 4$, $SS_2CET_2T\ \ 1$ | | CSO flow increased by 12 and no more |
| $SS_3CFT_2T\ \ 4$ | (4) | |
## Part (e):
| Consistent flow pattern $\geq 93$ (check each node), one number only per arc, no unnumbered arcs | M1 | |
| CAO, showing flow of 98, must follow from their routes | A1 (2) | |
## Part (f):
| The cut through $S_1A$, $BD$, $DE$, $ET_2$, $EF$, $CF$ and $S_3F$ has value of 98 | DB1 | Must have attempted (e) — at least one number on all but one arc, and made an attempt at a cut |
| Value of the flow is 98 so by max flow – min cut theorem flow is maximal | DB1 (2) | CSO — (e) fully correct showing flow of 98 and correct cut. Must refer to max flow–min cut theorem — all four words |
---6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e0c66144-9e34-42fc-9f40-a87a49331483-07_719_1313_246_376}
\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 \begin{enumerate}[label=(\roman*)]
\item Add a supersource, S , and a supersink, T , and corresponding arcs to Diagrams 1 and 2 in the answer book.
\item Enter the flow value and appropriate capacity on each of the arcs you have added to Diagram 1.
\end{enumerate}\item Complete the initialisation of the labelling procedure on Diagram 2 in the answer book by entering values along the new arcs from S to T , and along $\operatorname { arcs } \mathrm { S } _ { 1 } \mathrm {~B}$ and $\mathrm { AT } _ { 1 }$
\item Hence 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 Draw a maximal flow pattern on Diagram 3 in the answer book.
\item Prove that your flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2019 Q6 [14]}}