3 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\).
\includegraphics[max width=\textwidth, alt={}, center]{d1e453d6-0abb-4a7e-87c1-28275074dd08-06_832_858_388_591}
- Use Prim's algorithm starting from \(E\), showing the order in which you select the edges, to find a minimum spanning tree for the network.
- State the length of your minimum spanning tree.
- Draw your minimum spanning tree.
- On a particular day, village \(B\) is cut off, so its connecting roads cannot be used.
Find the length of a minimum spanning tree for the remaining eight villages.
(2 marks)
\includegraphics[max width=\textwidth, alt={}, center]{d1e453d6-0abb-4a7e-87c1-28275074dd08-08_2486_1724_221_143}