| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | MST with edges pre-included |
| Difficulty | Moderate -0.3 This is a standard MST question using Prim's algorithm with a straightforward modification in part (d). While it requires systematic application of the algorithm and careful tracking of edges, it's a routine textbook exercise with no novel problem-solving required. The constraint in part (d) is a common variation that simply requires comparing two MSTs, making it slightly easier than average for A-level. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
3 A theme park has 11 rides, $A , B , \ldots K$. The network shows the distances, in metres, between pairs of rides. The rides are to be connected by cabling so that information can be collated. The manager of the theme park wishes to use the minimum amount of cabling.\\
\includegraphics[max width=\textwidth, alt={}, center]{a1290c22-f28d-42aa-89d5-10d60ca4741c-03_988_1575_488_248}
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting from $A$, to find the minimum spanning tree for the network.
\item State the length of cabling required.
\item Draw your minimum spanning tree.
\item The manager decides that the edge $A E$ must be included. Find the extra length of cabling now required to give the smallest spanning tree that includes $A E$.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2005 Q3 [11]}}