| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| Session | January |
| Marks | 14 |
| 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 network flows question testing routine application of the maximum flow algorithm. Parts (a)-(c) require simple reading/calculation from the diagram, part (d) applies the labelling procedure mechanically (a core D2 algorithm), and part (e) requires recognizing how a vertex capacity constraint affects flow. While multi-part with several marks, it demands only procedural competence with no novel problem-solving or insight beyond textbook exercises. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| - What appears to be a mark distribution row (6 | 4 | 3 |
I appreciate you wanting to clean up mark scheme content, but the text you've provided doesn't contain any actual mark scheme information to process.
You've only provided:
- A question number (6)
- What appears to be a mark distribution row (6 | 4 | 3 | 2 | 0)
Please provide the full mark scheme content that includes:
- The marking criteria/points (M1, A1, B1, etc.)
- Descriptions of what earns each mark
- Any guidance notes
- Unicode symbols that need converting to LaTeX
Once you provide the complete content, I'll clean it up according to your specifications.6 [Figures 4 and 5, printed on the insert, are provided for use in this question.]\\
The network shows the routes along corridors from two arrival gates to the passport control area, $P$, in a small airport. The number on each edge represents the maximum number of passengers that can travel along a particular corridor in one minute.\\
\includegraphics[max width=\textwidth, alt={}, center]{6c407dbf-efe5-49e4-881f-91e7de5c46d9-7_933_1063_552_486}
\begin{enumerate}[label=(\alph*)]
\item State the vertices that represent the arrival gates.
\item Find the value of the cut shown on the network.
\item State the maximum flow along each of the routes UTSP and RQVP.
\item \begin{enumerate}[label=(\roman*)]
\item Taking your answers to part (c) 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 paths 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, illustrate a possible flow along each edge corresponding to this maximum flow.
\end{enumerate}\item On a particular day, there is an obstruction allowing no more than 50 passengers per minute to pass through vertex $V$. State the maximum number of passengers that can move through the network per minute on this particular day.\\
(2 marks)
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2009 Q6 [14]}}