| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | State number of edges formula |
| Difficulty | Easy -1.8 Part (a) tests direct recall of the fundamental MST formula (n-1 edges), requiring no calculation or problem-solving. Part (b) applies Prim's algorithm mechanically to a small network—a standard textbook exercise with clear steps. This is significantly easier than average A-level questions which typically require multi-step reasoning or problem-solving. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| 10 | B1 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| \(n - 1\) | B1 | 1 |
| Answer | Marks |
|---|---|
| Condone candidates attempting all of part (b) together / in different order |
| Answer | Marks | Guidance |
|---|---|---|
| Using Prim's: \(AB\), \(BC\), \(BD\), \(CF\), \(DG\) or \(FJ\), \(GK\) or \(JK\), \(KH\) or \(KI\), \(KI\) or \(IE\), \(EI\) or \(KH\) | M1 | |
| \(BD\) 3rd | A1 | |
| \(CF\) 4th | A1 | |
| A1 | ||
| All correct (10 edges) | B1 | 5 |
| Answer | Marks | Guidance |
|---|---|---|
| (Length =) 155 | B1 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Spanning tree with at least 8 edges. Any cycle scores M0 | M1 | |
| Correct and labelled | A1 | 2 |
| Alternative: \(FJ\) instead of \(DG\): [diagram showing spanning tree with alternative edge] | ||
| Total | 10 |
## 3(a)(i)
| 10 | B1 | 1 |
## 3(a)(ii)
| $n - 1$ | B1 | 1 |
## 3(b)
| Condone candidates attempting all of part (b) together / in different order | | |
## 3(b)(i)
| Using Prim's: $AB$, $BC$, $BD$, $CF$, $DG$ or $FJ$, $GK$ or $JK$, $KH$ or $KI$, $KI$ or $IE$, $EI$ or $KH$ | M1 | |
| $BD$ 3rd | A1 | |
| $CF$ 4th | A1 | |
| | A1 | |
| All correct (10 edges) | B1 | 5 |
## 3(b)(ii)
| (Length =) 155 | B1 | 1 |
## 3(b)(iii)
| Spanning tree with at least 8 edges. Any cycle scores M0 | M1 | |
| Correct and labelled | A1 | 2 |
| | | Alternative: $FJ$ instead of $DG$: [diagram showing spanning tree with alternative edge] |
| Total | | 10 |3
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item State the number of edges in a minimum spanning tree of a network with 11 vertices.
\item State the number of edges in a minimum spanning tree of a network with $n$ vertices.
\end{enumerate}\item The following network has 11 vertices, $A , B , \ldots , K$. The number on each edge represents the distance, in miles, between a pair of vertices.\\
\includegraphics[max width=\textwidth, alt={}, center]{4c5c963b-0183-4dc7-9054-b2c7a3eb8c1b-03_1468_1239_721_404}
\begin{enumerate}[label=(\roman*)]
\item Use Prim's algorithm, starting from $A$, to find a minimum spanning tree for the network.
\item Find the length of your minimum spanning tree.
\item Draw your minimum spanning tree.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2008 Q3 [10]}}