| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | MST with vertex removed |
| Difficulty | Moderate -0.8 This is a standard textbook application of Prim's algorithm with straightforward execution. Part (a) requires mechanical application of a learned algorithm with no problem-solving insight, and part (b) is a simple modification requiring re-application. The 9 marks reflect length rather than conceptual difficulty—this is routine algorithmic work typical of D1 module questions, making it easier than average A-level maths questions overall. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
The following network shows the lengths, in miles, of roads connecting nine villages, $A$, $B$, ..., $I$.
\includegraphics{figure_3}
\begin{enumerate}[label=(\alph*)]
\item
\begin{enumerate}[label=(\roman*)]
\item Use Prim's algorithm starting from $E$, showing the order in which you select the edges, to find a minimum spanning tree for the network. [4]
\item State the length of your minimum spanning tree. [1]
\item Draw your minimum spanning tree. [2]
\end{enumerate}
\item On a particular day, village $B$ is cut off, so its connecting roads cannot be used.
Find the length of a minimum spanning tree for the remaining eight villages. [2]
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2011 Q3 [9]}}