Minimum Spanning Tree

Minimum Spanning Tree (MST) is a subset of edges in a weighted, connected, and undirected graph that connects all the vertices with the minimum possible total edge weight, without forming any cycles.

1 Definition

Given an undirected graph G = (V, E), where:

• V is the set of vertices.
• E is the set of edges with weights.

A minimum spanning tree satisfies:

• It includes all vertices from V.
• It forms a tree (i.e., a connected acyclic subgraph).
• The sum of edge weights is minimized.

2 Properties

• A graph with N vertices has exactly N-1 edges in its MST.
• A connected graph may have multiple MSTs if different edge sets have the same total weight.
• Removing any edge from an MST disconnects the graph.
• Adding an edge to an MST creates a cycle.

3 Example

Consider the following weighted graph:

Vertex Pair	Edge Weight
A - B	4
A - C	3
B - C	1
B - D	2
C - D	5

One possible MST for this graph consists of the edges:

• B - C (1)
• B - D (2)
• A - C (3)

Total MST weight: 1 + 2 + 3 = 6

4 Algorithms

Several algorithms exist to find the minimum spanning tree efficiently:

• Kruskal's Algorithm
  • Sorts all edges by weight and adds them one by one, ensuring no cycles are formed.
• Prim's Algorithm
  • Grows the MST from an arbitrary starting vertex by adding the smallest edge connecting it to a new vertex.
• Borůvka's Algorithm
  • Adds the smallest edge from each component to another component until a single tree remains.

5 Implementation

A simple implementation of Kruskal's algorithm in Python:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            self.parent[root_u] = root_v

def kruskal_mst(edges, n):
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst = []
    
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))

    return mst

edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 5)]
mst = kruskal_mst(edges, 4)
print("Minimum Spanning Tree:", mst)

6 Applications

• Network Design
  • Used in designing efficient communication, power, and transportation networks.
• Approximation Algorithms
  • Forms the basis for solving hard problems like the Traveling Salesman Problem (TSP).
• Cluster Analysis
  • Used in hierarchical clustering techniques.

7 See Also

• Graph Theory
• Shortest Path Problem
• Kruskal’s Algorithm
• Prim’s Algorithm
• Borůvka’s Algorithm