- This question should be answered on the sheet provided.
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.
| 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 | - |
- 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.
- Calculate the minimum total length of cable required.