| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Identify specific edge in algorithm |
| Difficulty | Moderate -0.5 This is a standard Decision Maths question requiring application of well-defined algorithms (Kruskal's and Prim's) with no novel problem-solving. Part (d) requires understanding of how Prim's algorithm progresses from a specific vertex, which is slightly more demanding than mechanical application, but still routine for D1 students who have practiced these algorithms. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(DF=1.2\) | B1 | 9 edges |
| \(IH=1.8\) | M1 | SCA |
| \(BC=2.1\) | ||
| \(AJ\) or \(2.2\) | A1 | \(AJ\) 4th |
| \(EF=2.4\) | ||
| \(HG=2.6\) | A1 | \(HG\) 6th |
| \(GF=2.7\) | ||
| \(AB=2.8\) | ||
| \(JI=2.9\) | A1 | All correct |
| Total: 5 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(20.7\) | B1 | |
| Total: 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| MST diagram drawn | M1 | MST – connected (7+ edges) |
| Correct diagram | A1 | |
| Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(EF\) (or \(2.4\)) | M1, A1 | for \(BC\), \(DF\), \(EF\) |
| Total: 2 |
## Question 3:
### Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $DF=1.2$ | B1 | 9 edges |
| $IH=1.8$ | M1 | SCA |
| $BC=2.1$ | | |
| $AJ$ or $2.2$ | A1 | $AJ$ 4th |
| $EF=2.4$ | | |
| $HG=2.6$ | A1 | $HG$ 6th |
| $GF=2.7$ | | |
| $AB=2.8$ | | |
| $JI=2.9$ | A1 | All correct |
| **Total: 5** | | |
### Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $20.7$ | B1 | |
| **Total: 1** | | |
### Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| MST diagram drawn | M1 | MST – connected (7+ edges) |
| Correct diagram | A1 | |
| **Total: 2** | | |
### Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $EF$ (or $2.4$) | M1, A1 | for $BC$, $DF$, $EF$ |
| **Total: 2** | | |
---3 The diagram shows 10 bus stops, $A , B , C , \ldots , J$, in Geneva. The number on each edge represents the distance, in kilometres, between adjacent bus stops.\\
\includegraphics[max width=\textwidth, alt={}, center]{92175666-ef7a-4dca-9cdb-ebde1b40b2c9-03_595_1362_422_331}
The city council is to connect these bus stops to a computer system which will display waiting times for buses at each of the 10 stops. Cabling is to be laid between some of the bus stops.
\begin{enumerate}[label=(\alph*)]
\item Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the 10 bus stops.
\item State the minimum length of cabling needed.
\item Draw your minimum spanning tree.
\item If Prim's algorithm, starting from $A$, had been used to find the minimum spanning tree, state which edge would have been the final edge to complete the minimum spanning tree.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2008 Q3 [10]}}