| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | State maximum flow along specific routes |
| Difficulty | Moderate -0.5 This is a standard textbook application of the maximum flow algorithm (labelling procedure) with straightforward steps: finding initial flows along given routes, applying the augmenting path method, and verifying with a minimum cut. While multi-part and requiring careful bookkeeping, it follows a well-defined algorithmic procedure taught in D2 with no novel problem-solving required, making it slightly easier than average. |
| 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 |
| Route | Flow |
| \(A B E H\) | |
| \(A C F H\) | |
| \(A D G H\) | |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| ABEH: flow = 8 (min of AB=10, BE=8, EH=12) | B1 | All three values correct |
| ACFH: flow = 5 (min of AC=12, CF=5, FH=8) | ||
| ADGH: flow = 11 (min of AD=14, DG=11, GH=16) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct labelling procedure applied to Figure 4 | M1 | Must use initial flows from (a) |
| Flow-augmenting route identified, e.g. ACFEH or ADGFEH or similar | A1 | Correct route found |
| Correct potential increase/decrease values shown on route | A1 | |
| Second augmenting route found if applicable | A1 | |
| All modifications to flow correctly shown on network | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Maximum flow = 29 | B1 | |
| Correct flow on each edge shown in Figure 5, consistent with maximum flow of 29 | B1 | Must be consistent and feasible |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Cut of value 29 identified, e.g. edges \(\{BE, CF, GH\}\) or \(\{BE, CF, DG\}\) or \(\{AB, AC, AD\}\) | B1 | Must list edges explicitly and value must match stated maximum flow |
# Question 8:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| ABEH: flow = 8 (min of AB=10, BE=8, EH=12) | B1 | All three values correct |
| ACFH: flow = 5 (min of AC=12, CF=5, FH=8) | | |
| ADGH: flow = 11 (min of AD=14, DG=11, GH=16) | | |
## Part (b)(i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct labelling procedure applied to Figure 4 | M1 | Must use initial flows from (a) |
| Flow-augmenting route identified, e.g. ACFEH or ADGFEH or similar | A1 | Correct route found |
| Correct potential increase/decrease values shown on route | A1 | |
| Second augmenting route found if applicable | A1 | |
| All modifications to flow correctly shown on network | A1 | |
## Part (b)(ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Maximum flow = 29 | B1 | |
| Correct flow on each edge shown in Figure 5, consistent with maximum flow of 29 | B1 | Must be consistent and feasible |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Cut of value 29 identified, e.g. edges $\{BE, CF, GH\}$ or $\{BE, CF, DG\}$ or $\{AB, AC, AD\}$ | B1 | Must list edges explicitly and value must match stated maximum flow |8 The network below represents a system of pipes. The capacity of each pipe, in litres per second, is indicated on the corresponding edge.\\
\includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-22_743_977_404_536}
\begin{enumerate}[label=(\alph*)]
\item Find the maximum flow along each of the routes $A B E H , A C F H$ and $A D G H$ and enter their values in the table on Figure 4 opposite.
\item \begin{enumerate}[label=(\roman*)]
\item Taking your answers to part (a) as the initial flow, use the labelling procedure on Figure 4 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 5 opposite, 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{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\begin{tabular}{ | l | l | }
\hline
Route & Flow \\
\hline
$A B E H$ & \\
\hline
$A C F H$ & \\
\hline
$A D G H$ & \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
\end{tabular}
\end{center}
\end{table}
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_746_972_397_845}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_739_971_1311_539}
\end{center}
\end{figure}
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-24_2253_1691_221_153}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2013 Q8 [9]}}