Solution :
Given :
There are five cities in a network and the cost of [tex]\text{building}[/tex] a road directly between [tex]i[/tex] and [tex]j[/tex] is the entry [tex]a_{i,j}[/tex]
[tex]a_{i,j}[/tex] refers to the matrix.
Road cannot be built because there is a mountain.
The given matrix :
[tex]\begin{bmatrix}0 & 3 & 5 & 11 & 9\\ 3 & 0 & 3 & 9 & 8\\ 5 & 3 & 0 & \infty & 10\\ 11 & 9 & \infty & 0 & 7\\ 9 & 8 & 10 & 7 & 0\end{bmatrix}[/tex]
The matrix on the left above corresponds to the weighted graph on the right.
Using the [tex]\text{Kruskal's algorithm}[/tex] we can select the cheapest edge that is not creating a cycle.
Starting with 2 edges of weight 3 and the edge of weight 5 is forbidden but the edge is 7 is available.
The edge of the weight 8 completes a minimum spanning tree and total weight 21.
If the edge of weight 8 had weight 10 then either of the edges of weight 9 could be chosen the complete the tree and in this case there could be 2 spanning trees with minimum value.
