| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Count alternative MSTs |
| Difficulty | Standard +0.3 This is a standard MST question using Prim's algorithm with a straightforward application. Parts (a)-(c) are routine algorithmic execution. Part (d) requires identifying edges with equal weights that could be swapped, which adds mild problem-solving but remains accessible for D1 level—slightly above average due to the counting aspect. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| \(AB = 5.5\), \(BC = 8\), \(AI = 9\), \(BD = 13\), \(DE = 9\), \(DG = 11\), \(DF, EF, GF = 12\), \(IH = 16.5\) | B1, M1, A1, A1, A1 | SCA; AI 3rd; BD 4th; All correct (5 marks total) |
| Answer | Marks | Guidance |
|---|---|---|
| \(84\) | B1 | (1 mark total) |
| Answer | Marks | Guidance |
|---|---|---|
| Minimum spanning tree with 8 edges correctly labelled (including \(DF\) or \(GF\) instead of \(EF\)) | M1, B1, A1 | (3 marks total) |
| Answer | Marks | Guidance |
|---|---|---|
| \(2\) | B1 | (1 mark total) |
**1(a)**
| $AB = 5.5$, $BC = 8$, $AI = 9$, $BD = 13$, $DE = 9$, $DG = 11$, $DF, EF, GF = 12$, $IH = 16.5$ | B1, M1, A1, A1, A1 | SCA; AI 3rd; BD 4th; All correct (5 marks total) |
**1(b)**
| $84$ | B1 | (1 mark total) |
**1(c)**
| Minimum spanning tree with 8 edges correctly labelled (including $DF$ or $GF$ instead of $EF$) | M1, B1, A1 | (3 marks total) |
**1(d)**
| $2$ | B1 | (1 mark total) |1 The following network shows the lengths, in miles, of roads connecting nine villages.\\
\includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-02_856_1251_568_374}
\begin{enumerate}[label=(\alph*)]
\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.
\item State the number of other spanning trees that are of the same length as your answer in part (a).
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2007 Q1 [10]}}