5.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ba22b22e-c0d5-438d-821b-88619eacdb5d-6_687_1171_223_447}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{figure}
The numbers on the \(17 \operatorname { arcs }\) in the network shown in Figure 5 represent the distances, in km , between nine nodes, A, B, C, D, E, F, G, H and J.
- Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
- Starting at G , use Prim's algorithm to find a minimum spanning tree. You must clearly state the order in which you select the arcs of your tree.
- Find the weight of the minimum spanning tree.
A connected graph V has \(n\) nodes. The sum of the degrees of all the nodes in V is \(m\). The graph T is a minimum spanning tree of V .
- Write down, in terms of \(m\), the number of arcs in V .
- Write down, in terms of \(n\), the number of \(\operatorname { arcs }\) in T .
- Hence, write down an inequality, in terms of \(m\) and \(n\), comparing the number of arcs in T and V.