2. Kruskal's algorithm finds a minimum spanning tree for a connected graph with \(n\) vertices.
- Explain the terms
- connected graph,
- tree,
- spanning tree.
- Write down, in terms of \(n\), the number of arcs in the minimum spanning tree.
The table below shows the lengths, in km, of a network of roads between seven villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G .
| A | B | C | D | E | F | G |
| A | - | 17 | - | 19 | 30 | - | - |
| B | 17 | - | 21 | 23 | - | - | - |
| C | - | 21 | - | 27 | 29 | 31 | 22 |
| D | 19 | 23 | 27 | - | - | 40 | - |
| E | 30 | - | 29 | - | - | 33 | 25 |
| F | - | - | 31 | 40 | 33 | - | 39 |
| G | - | - | 22 | - | 25 | 39 | - |
- Complete the drawing of the network on Diagram 1 in the answer book by adding the necessary arcs from vertex C together with their weights.
- Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
- State the weight of the minimum spanning tree.