A minimum spanning tree (MST) of a weighted graph is a spanning tree where the sum of edge weights is minimized among all possible spanning trees. The minimum spanning tree connects all vertices in the graph with the minimum total weight while maintaining no cycles.
Properties
Weight Minimization:
Where is the weight of edge .
Key Characteristics:
- Unique minimum weight - If all edge weights are distinct, the minimum spanning tree is unique
- Multiple MSTs - If some edges have equal weights, multiple minimum spanning trees may exist with the same total weight
- Optimal connectivity - Provides the least expensive way to connect all vertices
- Spanning tree properties - Contains edges for vertices and is acyclic