Past exam question: 2078 Chaitra (Regular), Q11
Open in the Padhaiko appExplain the concept of minimum spanning tree (MST) and find MST for the following graph using Kruskal's algorithm:
[figure: undirected weighted graph on 9 vertices A, B, C, D, E, F, G, H, I with edges A-B(4), A-H(7), B-C(18), B-H(11), C-D(7), C-I(2), D-E(9), D-F(14), E-F(10), F-G(2), G-H(1), G-I(6), H-I(7)]
Solution
Concept of Minimum Spanning Tree (MST): For a connected, undirected, weighted graph , a spanning tree is an acyclic connected subgraph that includes all vertices using exactly edges. A Minimum Spanning Tree (MST) is a spanning tree whose total edge weight is minimum among all possible spanning trees.
Kruskal's Algorithm — Sorted Edge List: With , the MST must contain edges. Sort all edges in non-decreasing order of weight and add each edge if it does not create a cycle:
| Edge | Weight | Action | Reason |
|---|---|---|---|
G-H | 1 | Accept | Connects {G, H} |
C-I | 2 | Accept | Connects {C, I} |
F-G | 2 | Accept | Connects {F, G, H} |
A-B | 4 | Accept | Connects {A, B} |
G-I | 6 | Accept | Merges {F, G, H} and {C, I} |
A-H | 7 | Accept | Merges {A, B} and {C, F, G, H, I} |
C-D | 7 | Accept | Connects D |
H-I | 7 | Reject | H and I already connected (cycle H-G-I-H) |
D-E | 9 | Accept | Connects E (8 edges reached — MST complete) |
Remaining Edges & Total Cost Verification:
- Edges
E-F(10),B-H(11),D-F(14),B-C(18)are skipped because 8 edges already span all 9 vertices. - Total MST Weight:
- MST: A spanning tree of a connected weighted graph with minimum total edge weight using edges.
- Selected MST Edges (Kruskal's):
G-H(1),C-I(2),F-G(2),A-B(4),G-I(6),A-H(7),C-D(7),D-E(9). - Total Minimum Weight: .