2.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.
- Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
- State the minimum cost of connecting the alarm systems in the nine buildings.
It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
- Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
- Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case.
Since arcs BC and EF already exist, there is no cost for these connections.
- State the new minimum cost of connecting the nine buildings.