| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm in matrix form |
| Difficulty | Moderate -0.8 This is a straightforward application of Prim's algorithm in matrix form with only 5 vertices. The method is algorithmic and routine for D1 students—simply follow the procedure of selecting minimum edges connecting to the growing tree. No problem-solving insight or novel thinking is required, just careful execution of a learned algorithm. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Durness | Helmsdale | Inverness | Thurso | Wick | |
| Durness | - | 68 | 123 | 81 | 92 |
| Helmsdale | 68 | - | 102 | 72 | 64 |
| Inverness | 123 | 102 | - | 148 | 127 |
| Thurso | 81 | 72 | 148 | - | 48 |
| Wick | 92 | 64 | 127 | 48 | - |
| Answer | Marks | Guidance |
|---|---|---|
| 282 km | A1 | (6) |
| (b) | 282 km | A1 |
**(a)** Order: 4, 3, 5, 1, 2 (Durness, Helmsdale, Inverness, Thurso, Wick)
Distance matrix with shortest paths:
- T—W: 48
- W—H: 64
- H—D: 68
- H—I: 102
| 282 km | A1 | (6) |
**(b)** | 282 km | A1 | (6) |
---\begin{enumerate}
\item This question should be answered on the sheet provided.
\end{enumerate}
A cable TV company wishes to link 5 villages in the Scottish Highlands. The table below shows the shortest distances, in kilometres, between these 5 villages.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Durness & Helmsdale & Inverness & Thurso & Wick \\
\hline
Durness & - & 68 & 123 & 81 & 92 \\
\hline
Helmsdale & 68 & - & 102 & 72 & 64 \\
\hline
Inverness & 123 & 102 & - & 148 & 127 \\
\hline
Thurso & 81 & 72 & 148 & - & 48 \\
\hline
Wick & 92 & 64 & 127 & 48 & - \\
\hline
\end{tabular}
\end{center}
(a) Starting at Thurso, use Prim's algorithm to find a minimum spanning tree.
You should make your method clear, indicating the order in which you selected the arcs in your final tree.\\
(b) Calculate the minimum total length of cable required.\\
\hfill \mbox{\textit{Edexcel D1 Q1 [6]}}