- This question should be answered on the sheet provided in the answer booklet.
A school wishes to link 6 computers. One is in the school office and one in each of rooms \(\mathrm { A } , B , C , D\) and \(E\). Cables need to be laid to connect the computers. The school wishes to use a minimum total length of cable.
The table shows the shortest distances, in metres, between the various sites.
| Office | Room \(A\) | Room \(B\) | Room \(C\) | Room \(D\) | Room \(E\) |
| Office | - | 8 | 16 | 12 | 10 | 14 |
| Room \(A\) | 8 | - | 14 | 13 | 11 | 9 |
| Room \(B\) | 16 | 14 | - | 12 | 15 | 11 |
| Room \(C\) | 12 | 13 | 12 | - | 11 | 8 |
| Room \(D\) | 10 | 11 | 15 | 11 | - | 10 |
| Room \(E\) | 14 | 9 | 11 | 8 | 10 | - |
- Starting at the school office, use Prim's algorithm to find a minimum spanning tree. Indicate the order in which you select the edges and draw your final tree.
(5 marks) - Using your answer to part (a), calculate the minimum total length of cable required.
(1 mark)