| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Standard +0.8 This is a comprehensive multi-source/multi-sink max flow problem requiring supersource/supersink construction, flow augmentation, and cut verification. While methodical, it demands careful bookkeeping across multiple diagrams, understanding of the labeling algorithm, and proof via min-cut max-flow theorem—significantly more demanding than routine single-source problems but still following standard D2 procedures. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Part (a) | Initial flow = 93 | B1 |
| (1) | ||
| Part (b) | Adds supersource \(S\) plus arcs \(SA(49)\) and \(SB(57)\) | M1, A1 |
| b1A1: CAO all arcs and numbers correct. | ||
| Adds supersink \(T\) plus arcs \(HT(20)\) and \(IT(85)\) | M1, A1, A1 | |
| (3) | ||
| Part (d) | E.g. \(SACDGIT - 2\) and \(SACDFIT - 3\) | M1, A1, A1 |
| Maximum flow = 98 | A1 | |
| (3) | ||
| Part (e) | E.g. | M1, A1 |
| (2) | ||
| Part (f) | Max flow = min cut, cut through \(CH, CF, DF, FG, GI\) | M1, A1 |
| (2) | f1A1: cut correct – may be drawn. Must have shown a correct flow of 98 in (e). Refer to max flow-min cut theorem all four words. | |
| Total | 13 marks |
| **Part (a)** | Initial flow = 93 | B1 | |
|---|---|---|---|
| | | **(1)** | |
| **Part (b)** | Adds supersource $S$ plus arcs $SA(49)$ and $SB(57)$ | M1, A1 | b1M1: All relevant arcs added OR all arcs and numbers from supersource OR from supersink correct. |
| | | | b1A1: CAO all arcs and numbers correct. |
| | Adds supersink $T$ plus arcs $HT(20)$ and $IT(85)$ | M1, A1, A1 | |
| | | **(3)** | |
| **Part (d)** | E.g. $SACDGIT - 2$ and $SACDFIT - 3$ | M1, A1, A1 | d1M1: One valid flow augmenting route (from $S$ to $T$) found and a value stated. d1A1: cut correct – may be drawn. Must have shown a correct flow of 98 in (e). Refer to max flow-min cut theorem all four words. |
| | | | |
| | Maximum flow = 98 | A1 | |
| | | **(3)** | |
| **Part (e)** | E.g. | M1, A1 | e1M1: Consistent flow pattern $> 95$ – condone $S$ and $T$'s presence. Must have exactly one number on each arc. e1A1: CAO must follow from their routes (allow if routes in (d) do not include $S$ and/or $T$). |
| | | **(2)** | |
| **Part (f)** | Max flow = min cut, cut through $CH, CF, DF, FG, GI$ | M1, A1 | f1M1: Must have attempted (e) and made an attempt at a cut. |
| | | **(2)** | f1A1: cut correct – may be drawn. Must have shown a correct flow of 98 in (e). Refer to max flow-min cut theorem all four words. |
| | **Total** | **13 marks** | |
**Notes for Question 6:**
- a1B1: CAO
- b1M1: All relevant arcs added OR all arcs and numbers from supersource OR from supersink correct.
- b1A1: CAO all arcs and numbers correct.
- c1M1: 2 numbers and arrows on each arc.
- c1A1: CAO Condone 4 errors.
- c2A1: CAO.
- d1M1: One valid flow augmenting route (from $S$ to $T$) found and a value stated.
- d1A1: Flow increased by 5 and no more.
- d2A1: CAO 98 (allow if seen in (f) but must be clearly labelled as the maximum flow)
- e1M1: Consistent flow pattern $> 95$ – condone $S$ and $T$'s presence. Must have exactly one number on each arc.
- e1A1: CAO must follow from their routes (allow if routes in (d) do not include $S$ and/or $T$).
- f1M1: Must have attempted (e) and made an attempt at a cut.
- f1A1: cut correct – may be drawn. Must have shown a correct flow of 98 in (e). Refer to max flow-min cut theorem all four words.
**Examples of flow augmenting routes:**
- $SACDGFIT$ (3), $SACDGIT$ (2)
- $SBEDGFIT$ (3), $SBEDGIT$ (2)
- $SBEDGFIT$ (3), $SACDGIT$ (2)
- $SACDGFIT$ (3), $SBEDGIT$ (2)
---6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{0af7fd3e-68af-41fc-883b-3bc2589035bb-7_816_1138_178_459}
\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 On Diagram 1 and Diagram 2 in the answer book, add a supersource S and a supersink T . On Diagram 1, show the minimum capacities of the arcs you have added.
\item Complete the initialisation of the labelling procedure on Diagram 2 in the answer book by entering values on the arcs to S and T and on $\operatorname { arcs } \mathrm { CD }$, DE , DG , FG, FI and GI.
\item Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
\item Show your maximum flow on Diagram 3 in the answer book.
\item Prove that your flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2013 Q6 [13]}}