| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | January |
| Marks | 15 |
| 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 max-flow/min-cut problem from Decision Mathematics with clearly structured parts guiding students through the algorithm. Part (b) asks only to state maximum flows along specific simple routes (straightforward inspection), requiring no optimization or complex reasoning—just reading capacities along given paths. While the full question involves labelling procedures, this specific part is routine application of basic network flow concepts, making it easier than average A-level material. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Surname | Other Names | |||||||||||
| Centre Number | Candidate Number | |||||||||||
| Candidate Signature | ||||||||||||
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(15 + 0 + 14 + 7 + 9 = 45\) | B1 | Total: 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Maximum flow \(\leq 45\) | M1 | \(\leq\) their value or \(< 45\) |
| Correct | A1 | Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(SABT\) flow 10; \(SDET\) flow 14; \(SFT\) flow 9 | B1, B1 | One correct; two more correct; Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Additional route with correct flow | M1, A1 | |
| One more correct route and flow | A1 | |
| Table complete | A1 | Correct total flow of 40 on network (may use double edges) strict |
| Correct use of potential and used flows; values correctly updated | M1, A1 | Total: 6 |
| Routes: \(SABT\ 10\); \(SDET\ 14\); \(SFT\ 9\); \(SADFT\ 6\); \(SADFET\ 1\) | Several possibilities |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Maximum flow \(= 40\) | B1 | |
| Network showing flow of 40 | B1 | Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Cut through saturated arcs \(AB, BD, DE, DF, SF\) | M1 | |
| Minimum cut shown to be 40 with statement linking to maximum flow | A1 | Total: 2 |
## Question 6:
### Part (a)(i):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $15 + 0 + 14 + 7 + 9 = 45$ | B1 | Total: 1 |
### Part (a)(ii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum flow $\leq 45$ | M1 | $\leq$ their value or $< 45$ |
| Correct | A1 | Total: 2 |
### Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $SABT$ flow 10; $SDET$ flow 14; $SFT$ flow 9 | B1, B1 | One correct; two more correct; Total: 2 |
### Part (c)(i):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Additional route with correct flow | M1, A1 | |
| One more correct route and flow | A1 | |
| Table complete | A1 | Correct total flow of 40 on network (may use double edges) **strict** |
| Correct use of potential and used flows; values correctly updated | M1, A1 | Total: 6 |
| Routes: $SABT\ 10$; $SDET\ 14$; $SFT\ 9$; $SADFT\ 6$; $SADFET\ 1$ | | Several possibilities |
### Part (c)(ii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum flow $= 40$ | B1 | |
| Network showing flow of 40 | B1 | Total: 2 |
### Part (c)(iii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Cut through saturated arcs $AB, BD, DE, DF, SF$ | M1 | |
| Minimum cut shown to be 40 with statement linking to maximum flow | A1 | Total: 2 |6 [Figures 2 and 3, printed on the insert, are provided for use in this question.]\\
The diagram shows a network of pipelines through which oil can travel. The oil field is at $S$, the refinery is at $T$ and the other vertices are intermediate stations. The weights on the edges show the capacities in millions of barrels per hour that can flow through each pipeline.\\
\includegraphics[max width=\textwidth, alt={}, center]{be283950-ef4c-482f-94cb-bdb3def9ff6d-06_956_1470_593_283}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Find the value of the cut marked $C$ on the diagram.
\item Hence make a deduction about the maximum flow of oil through the network.
\end{enumerate}\item State the maximum possible flows along the routes $S A B T , S D E T$ and $S F T$.
\item \begin{enumerate}[label=(\roman*)]
\item Taking your answer to part (b) as the initial flow, use a labelling procedure on Figure 2 to find the maximum flow from $S$ to $T$. Record your routes and flows in the table provided and show the augmented flows on the network diagram. (6 marks)
\item State the value of the maximum flow, and, on Figure 3, illustrate a possible flow along each edge corresponding to this maximum flow.
\item Prove that your flow in part (c)(ii) is a maximum.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
Surname & & & & & & \multicolumn{2}{|c|}{Other Names} & & & & & \\
\hline
\multicolumn{2}{|c|}{Centre Number} & & & & & & \multicolumn{2}{|l|}{Candidate Number} & & & & \\
\hline
\multicolumn{3}{|l|}{Candidate Signature} & & & & & & & & & & \\
\hline
\end{tabular}
\end{center}
\section*{General Certificate of Education \\
January 2007 \\
Advanced Level Examination}
\section*{MATHEMATICS \\
Unit Decision 2}
MD02
\section*{Insert}
Insert for use in Questions 1 and 6.\\
Fill in the boxes at the top of this page.\\
Fasten this insert securely to your answer book.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D2 2007 Q6 [15]}}