| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Moderate -0.5 This is a standard textbook application of max-flow algorithm with supersource/supersink setup. Part (a) requires routine network modification (2 marks), parts (b) and (c) follow algorithmic procedures taught directly in D2. While multi-part, each step is procedural with no novel problem-solving required, making it slightly easier than average A-level questions. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree7.04e Route inspection: Chinese postman, pairing odd nodes7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Supersource \(S\) connected to \(R_1\) and \(R_2\) with edges of capacity \(\infty\) (or sufficiently large value) | B1 | Accept any large capacity or uncapacitated edges from supersource |
| Supersink \(T\) connected from \(T_1\), \(T_2\), \(T_3\) with edges of capacity \(\infty\) (or sufficiently large value) | B1 | Both supersource and supersink needed with correct directed edges |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct identification of a flow augmenting route from initial flow | M1 | Must use labelling procedure |
| Correct bottleneck/flow value identified for each route | A1 | |
| Further augmenting routes found and correct flows recorded in table | M1 | |
| Flows correctly updated on network diagram | A1 | Follow through from routes found |
| All augmenting routes found, reaching maximum flow | A1 | All 5 marks dependent on correct method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Maximum flow \(= 62\) | B1 | |
| Correct flow values shown on Figure 4 consistent with maximum flow of 62 | B1 | Must be consistent with stated maximum flow |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Cut of value 62 identified | M1 | Must match stated maximum flow value |
| Correct edges of cut listed, e.g. \(AT_1\), \(DT_1\), \(DT_2\), \(ET_2\), \(ET_3\), \(CT_3\) | A1 | All edges must be correct and complete |
# Question 7:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Supersource $S$ connected to $R_1$ and $R_2$ with edges of capacity $\infty$ (or sufficiently large value) | B1 | Accept any large capacity or uncapacitated edges from supersource |
| Supersink $T$ connected from $T_1$, $T_2$, $T_3$ with edges of capacity $\infty$ (or sufficiently large value) | B1 | Both supersource and supersink needed with correct directed edges |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct identification of a flow augmenting route from initial flow | M1 | Must use labelling procedure |
| Correct bottleneck/flow value identified for each route | A1 | |
| Further augmenting routes found and correct flows recorded in table | M1 | |
| Flows correctly updated on network diagram | A1 | Follow through from routes found |
| All augmenting routes found, reaching maximum flow | A1 | All 5 marks dependent on correct method |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum flow $= 62$ | B1 | |
| Correct flow values shown on Figure 4 consistent with maximum flow of 62 | B1 | Must be consistent with stated maximum flow |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Cut of value 62 identified | M1 | Must match stated maximum flow value |
| Correct edges of cut listed, e.g. $AT_1$, $DT_1$, $DT_2$, $ET_2$, $ET_3$, $CT_3$ | A1 | All edges must be correct and complete |7 Figure 2 shows a network of pipes.
Water from two reservoirs, $R _ { 1 }$ and $R _ { 2 }$, is used to supply three towns, $T _ { 1 } , T _ { 2 }$ and $T _ { 3 }$.\\
In Figure 2, the capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow.
\begin{enumerate}[label=(\alph*)]
\item Add a supersource, supersink and appropriate weighted edges to Figure 2. (2 marks)
\item \begin{enumerate}[label=(\roman*)]
\item Use the initial flow and the labelling procedure on Figure 3 to find the maximum flow through the network.
You should indicate any flow augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
\item State the value of the maximum flow and, on Figure 4, illustrate a possible flow along each edge corresponding to this maximum flow.
\end{enumerate}\item Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-18_1077_1246_1475_395}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_1049_1264_308_386}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_835_1011_1738_171}
\end{center}
\end{figure}
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_688_524_1448_1302}
\end{center}
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-20_2256_1707_221_153}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2013 Q7 [11]}}