| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply both algorithms and compare |
| Difficulty | Moderate -0.8 This is a standard textbook exercise requiring mechanical application of two well-defined algorithms (Kruskal's and Prim's) to find a minimum spanning tree. While it involves multiple parts and careful bookkeeping, it requires no problem-solving insight or novel reasoning—just following algorithmic procedures that students practice repeatedly in D1. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{552f3296-ad61-448b-8168-6709fb359fa2-3_780_1353_248_356}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 represents the distance, in metres, between eight data collection points, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }$, G and H . The data collection points are to be linked by cables.
\begin{enumerate}[label=(\alph*)]
\item Listing the arcs in the order that you select them, find a minimum spanning tree for the network using
\begin{enumerate}[label=(\roman*)]
\item Kruskal's algorithm, stating in addition any arcs you reject,
\item Prim's algorithm, starting from A .
\end{enumerate}\item State the minimum amount of cable needed.
\item Draw your minimum spanning tree using the vertices given in Figure 1 in your answer book.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q3 [8]}}