Minimum Spanning Tree

Summary

---

This lecture will be about graphs. A tree is a graph which is connected with no cycles.

Note

A graph is a tree if and only if is connected and .

Definition

A spanning tree of a graph is a tree with .

A graph can have exponentially many spanning trees; in general, they need not be unique.

Lemma

A graph has a spanning tree if and only if is connected.

Proof

Clearly, connectedness is necessary. For sufficiency, initialize . While there exists a cycle , remove an arbitrary edge from . Then return .

Subclaim 1: this algorithm always terminates. This is easy to understand, as there are a finite number of edges. Subclaim 2: When the algorithm terminates, is a spanning tree. This is because we removed all cycles and everything is still reachable.

We can also construct the proof the other way: start with no edges and slowly build up our spanning tree. Both take time. We want to do better.

Minimum Spanning Tree (MST) Problem

Our input is a connected graph and edge weights . We output a spanning tree of G minimizing

Greedy Meta-Algorithm

We have . Initialize . While is not a spanning tree, find a safe edge , add to , and return . The key is how we determine “safe”-ness.

Our key invariant is that is a subset of some MST. Safety means we maintain the invariant.

Theorem

Let be a strict subset of some MST. Let:

• be a cut such that no edge of crosses the cut
• be a minimum-weight edge crossing the cut.

Then is a subset of some MST, i.e. is safe.

Proof

Let be an MST containing . If , done. Suppose . Since is connected, there’s a path in connecting the endpoints of . Since and , the path must have some edge crossing the cut .

Subclaim 1: is a spanning tree. It has edges, and removing disconnects into two components that reconnects (both cross the same cut). Subclaim 2: , so is an MST. Since is a minimum-weight edge crossing the cut, .

The Exchange Property of Spanning Trees

Lemma (Cycle Perspective)

Let be a connected graph, be a spanning tree of , and . Then:

• there is a unique path connecting in
• forms a cycle (called the fundamental cycle of w.r.t. )
• , the subgraph is a spanning tree.

Lemma (Cut Perspective)

Let be a connected graph, be a spanning tree of , and . Then

• has two components (disconnected)

• , the subgraph is a spanning tree.

Proof

Kruskal’s Algorithm

We modify our meta-algorithm to be rigorous. Kruskal’s Algorithm grows a bunch of small trees and then merges them together. We will analyze the slower but intuitive version.

The idea is to maintain that is a forest. We get our weighted connected and initialize . While such that has no cycles, pick such an edge of minimum weight and add to .

The fast version uses the observation that has no cycles iff connects two distinct connected components. So we need a data structure for fast lookups of whether two vertices are in the same component. We use the union-find data structure. Sort in increasing order of weight (). For each edge (in sorted order), if and are in different components, add to and union the two components. Each find/union is amortized.

The overall runtime is .

Prim’s Algorithm

Here, we grow a single tree and absorb isolated vertices at every step. The slow but intuitive version: initialize , pick a starting vertex , and set . While , pick an edge with of minimum weight, add to and to . This never introduces cycles since .

To make this fast, for each vertex we maintain , the weight of the cheapest edge connecting to the current tree. We need a priority queue supporting:

• Insert(v, d(v))
• DeleteMin()
• DecreaseKey(v, d(v))

Initialize by inserting all vertices with (except ). While the queue is non-empty:

1. DeleteMin() to extract the closest vertex
2. Add the edge to
3. For each neighbor of still in the queue, if , call DecreaseKey(v, w(u,v)) and set

We perform inserts, DeleteMins, and at most DecreaseKeys. With a binary heap, each operation is , giving . With a Fibonacci heap, DecreaseKey is amortized, improving the total to .