| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Identify specific edge in algorithm |
| Difficulty | Easy -1.2 This is a standard textbook application of Kruskal's algorithm requiring systematic edge selection in ascending order and cycle checking. While it has multiple parts and 11 marks total, it involves purely algorithmic execution with no problem-solving insight or novel reasoning—students simply follow the memorized procedure. D1 content is generally more procedural than pure mathematics modules. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
The network shows 10 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges.
\includegraphics{figure_3}
\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 towns. [6 marks]
\item State the length of your minimum spanning tree. [1 mark]
\item Draw your minimum spanning tree. [3 marks]
\item If Prim's algorithm, starting at $B$, had been used to find the minimum spanning tree, state which edge would have been the final edge to complete the minimum spanning tree. [1 mark]
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2010 Q3 [11]}}