2.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-03_920_1259_262_395}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
Figure 3 represents nine computer terminals, A, B, C, D, E, F, G, H and J, at Pearsonby School. The school wishes to connect them to form a single computer network. The number on each arc represents the cost, in pounds, of connecting the corresponding computer terminals.
- Use Prim's algorithm, starting at B , to find the minimum spanning tree for the computer network. You must clearly state the order in which you select the arcs of your tree.
(3) - State the minimum cost of connecting the nine computer terminals.
(1)
It is discovered that some computer terminals are already connected. There are already direct connections along BD and FJ, as shown in bold in Diagram 1 in the answer book. It is decided to use these connections. - Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BD and FJ. You must list the arcs in the order that you consider them. In each case, state whether or not you are adding the arcs to your spanning tree.
(3)
(Total 7 marks)