| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | MST with variable edge weight |
| Difficulty | Standard +0.3 This is a standard D1 question combining routine application of Prim's and Dijkstra's algorithms with a straightforward inequality involving a variable edge weight. Part (b)(ii) requires minimal insight—students simply compare the new route distance to the original shortest path. The algorithms are mechanical procedures well-practiced at this level, and the inequality setup is direct. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
3 [Figure 1, printed on the insert, is provided for use in part (b) of this question.]\\
The diagram shows a network of roads. The number on each edge is the length, in kilometres, of the road.\\
\includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-03_716_1303_559_388}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Prim's algorithm, starting from $A$, to find a minimum spanning tree for the network.
\item State the length of your minimum spanning tree.
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm on Figure 1 to find the shortest distance from $A$ to $J$.
\item A new road, of length $x \mathrm {~km}$, is built connecting $I$ to $J$. The minimum distance from $A$ to $J$ is reduced by using this new road. Find, and solve, an inequality for $x$.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2006 Q3 [14]}}