| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | MST with edges pre-included |
| Difficulty | Easy -1.2 This is a standard textbook application of two well-known algorithms (Kruskal's and Prim's) with minimal problem-solving required. Part (a) involves routine execution of memorized procedures, and part (b) tests basic understanding of when to use each algorithm—a common exam question type in D1. The adaptation required is straightforward (start Prim's from a connected component). Significantly easier than average A-level maths questions which typically require more mathematical reasoning. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
\includegraphics{figure_2}
The network in Figure 2 shows the distances, in metres, between 10 wildlife observation points. The observation points are to be linked by footpaths, to form a network along the arcs indicated, using the least possible total length.
\begin{enumerate}[label=(\alph*)]
\item Find a minimum spanning tree for the network in Figure 2, showing clearly the order in which you selected the arcs for your tree, using
\begin{enumerate}[label=(\roman*)]
\item Kruskal's algorithm, [3]
\item Prim's algorithm, starting from $A$. [3]
\end{enumerate}
Given that footpaths are already in place along $AB$ and $FI$ and so should be included in the spanning tree,
\item explain which algorithm you would choose to complete the tree, and how it should be adapted. (You do not need to find the tree.) [2]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2005 Q3 [8]}}