Minimum Spanning Tree

Summary

We found a greedy algorithm to construct MSTs by partitioning graphs and using cut edges

Contents

• MST Problem
  • Tree Properties
• Kruskal’s Algorithm
  • Kruskal’s Correctness
• Cuts
  • Cut Property

MST Problem

Given: Undirected graph G, with weights w for e in E.

Goal: Find minimal size, connected subgraph with min weight

Tree Properties

Tree
connected, acyclic graph

Basic properties:

• n vertices = n-1 edges
• exactly 1 path between every pair of vertices
  • if there are 0 paths, tree is not connected
  • if there are 2 or more, there is a cycle
• Any connected $G=(V,E) \text{ with } \lvert E \rvert = \lvert V \rvert - 1$ is a tree

Kruskal’s Algorithm

Sort edges by lowest weight, iterate over edges, add them to the tree if you can

We cannot add the edge of weight 6 since it would create a cycle

It takes O(mlogn) time to sort edges by weight

It takes O(logn) time to find if adding an edge creates a cycle

• Using Union-Find data structure
• Searches to see if nodes are in same component

Kruskal’s Correctness

Assume by induction tree X is correct so far

$x \subset T$ where T is MST

If for some edge e, we don’t add e to x, x is still MST.

If for some edge e, we do add e to x, $x \bigcup e \subset T'$ where T’ is a MST

We know T’ is minimum becuase e is of minimum (remaining) weight

Cuts

Cut
S set of edges that partition the vertices into two sets

Cut Property

For an undirected Graph G

• Take $X \subset E$ where $X \subset T$ for an MST T
• Take $S \subset T$ where no edge is in the $\text{cut}\left(S,\bar{S}\right)$
• Look at all edges of G in $\text{cut}\left(S,\bar{S}\right)$
• Let $e^*$ be a minimum weight edge in cut

Then $X \bigcup e^* \subset T'$ where T’ is an MST

If we start with disjoint subsets and only consider minimal edges going between them adding the edge will create a new MST