7 A complete graph on five vertices is weighted to form a network, as given in the weighted matrix below.
| A | B | C | D | E |
| \cline { 2 - 6 }
A | - | 9 | 5 | 4 | 2 |
| \cline { 2 - 6 }
B | 9 | - | 7 | 5 | 7 |
| \cline { 2 - 6 }
C | 5 | 7 | - | 6 | 8 |
| \cline { 2 - 6 }
D | 4 | 5 | 6 | - | 5 |
| \cline { 2 - 6 }
E | 2 | 7 | 8 | 5 | - |
| \cline { 2 - 6 } | | | | | |
| \cline { 2 - 6 } |
- Apply Prim's algorithm to the copy of this weighted matrix in the Printed Answer Booklet to construct a minimum spanning tree for the five vertices.
Draw your minimum spanning tree, stating the order in which you built the tree and giving its total weight. - (a) Using only the arcs in the minimum spanning tree, which vertex should be chosen to find the smallest total of the weights of the paths from that vertex to each of the other vertices?
(b) State the minimum total for this vertex. - Show that the total number of comparisons needed to find a minimum spanning tree for a \(5 \times 5\) matrix is 16 .
- If a computer takes 4 seconds to find a minimum spanning tree for a network with 100 vertices, how long would it take to find a minimum spanning tree for a network with 500 vertices?