5 The diagram represents canals connecting five cities. Canal lengths (shown on the arcs) are in km.
\includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-5_410_990_306_539}
- Draw a network in your answer book with nodes representing the five cities and arcs representing direct canal connections, i.e. canal connections which do not involve passing through another city.
The company operating the canal system wishes to close some canals to save money, whilst preserving the connectivity.
- Starting at A, use Prim's algorithm on your answer to part (i) to find a minimum connector for the network. Give the order in which you include arcs. Draw your minimum connector and give its total length.
Consider the original network together with an extra vertex, X , at the junction of four arcs.
\includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-5_405_987_1361_539} - Draw the minimum connector which results from applying Prim's algorithm, starting at A , to this network. Give the length of that minimum connector. Hence advise the company on which canals to close.
- Give a reason why the company might face objections to such closures.