| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm from vertex |
| Difficulty | Moderate -0.8 This is a straightforward application of Prim's algorithm, a standard D1 procedure requiring systematic execution from a given starting vertex. While it involves multiple steps across 11 vertices, it demands only algorithmic recall and careful bookkeeping rather than problem-solving insight or conceptual understanding. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
1 The following network shows the lengths, in miles, of roads connecting 11 villages, $A , B , \ldots , K$.\\
\includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-2_915_1303_591_365}
\begin{enumerate}[label=(\alph*)]
\item Starting from $G$ and showing your working at each stage, use Prim's algorithm to find a minimum spanning tree for the network.
\item State the length of your minimum spanning tree.
\item Draw your minimum spanning tree.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2009 Q1 [10]}}