Minimum Spanning Trees

Document last modified:

Overview

Minimum spanning trees are used extensively in networking to determine the minimum path from one point to all others on the network. Transparent bridges on local area networks use MST algorithms to determine which networks should be used for broadcasting frames and which should not.

Problem

A town has a set of houses and a set of roads.
A road connects 2 and only 2 houses.
A road connecting houses u and v has a repair cost w(u, v).
Goal: Repair enough (and no more) roads such that

everyone stays connected: can reach every house from all other houses, and

total repair cost is minimum.

Model as a graph:

Undirected graph G = (V, E).

Weight w(u, v) on each edge (u, v) ∈ E

Find T | E such that

T connects all vertices (T is a spanning tree), and

is minimized.

A spanning tree whose weight is minimum over all spanning trees is called a minimum spanning tree, or MST.

Example of such a graph (edges in MST are shaded) :

In this example, there is more than one MST. Replace edge (b, c ) by (a, h). Get a different spanning tree with the same weight.

Growing a minimum spanning tree

Some properties of an MST:

|V| − 1 edges.

no cycles.

might not be unique.

Building a MST solution

Build a set A of edges that will eventually be an MST.

Initially, A has no edges.

As we add edges to A, maintain loop invariant:

A | MST

Add only edges that maintain the invariant.

Edge (u, v) is safe for A if and only if A | {(u, v)}⊆ MST

So add only safe edges to A.

Safe edge means it is in a MST

Generic MST algorithm

GENERIC-MST(G,w)
    A ← ∅
    while A is not a spanning tree
            find an edge (u, v) that is safe for A
            A ← A | {(u, v)}
    return A

Use the loop invariant to show that this generic algorithm works.

Initialization: The empty set trivially satisfies the loop invariant, A | MST.

Maintenance: Since we add only safe edges, A remains a subset of some MST.

Termination: By maintenance, all edges added to A are safe, in an MST; at termination, A is a spanning tree that is also an MST.

Finding a safe edge

How do we find safe edges?

Example

Edge (h, g) has the lowest weight of any edge in the graph. Is it safe for A = ∅?

Intuitively: Let S ⊂ V be any set of vertices that includes h but not g (so that g is in V − S).

In any MST, there has to be one edge (at least) that connects S with V − S.

Why not choose the edge with minimum weight?

(h, g) is the minimum edge so is part of the MST therefore safe.

Below (c, d) is minimum edge that connects S and V-S, so is safe.

Definitions

Let S ⊂ V and A | E.

Black vertices in S, white in V-S.

Edge (u, v) is safe for A if and only if A | {(u, v)}⊆ MST

A cut (S, V − S) is a partition of vertices into disjoint sets S and V − S.

Edge (u, v) ∈ E crosses cut (S, V − S) if one endpoint is in S and the other is in V − S.

(b, h) crosses.

A cut respects A if and only if no edge in A crosses the cut.

A is MST with edges shaded. No edge in A crosses the cut.

An edge is a light edge crossing a cut if and only if its weight is minimum over all edges crossing the cut. For a given cut, there can be more than one light edge crossing it.

(d, c) light edge, weight 7.

Question - Which edge should be added to A next?

Theorem

Let

A ⊆ MST

(S, V − S) be a cut that respects A, i.e. no edge in A crosses the cut

(u, v) be a light edge crossing (S, V − S), light edge is a minimum weight edge crossing cut.

Implies (u, v) ⊆ A.

Then (u, v) is safe for A.

A | {(u, v)} ⊆ MST

Proof

Let T be an MST that includes A.

If T contains (u, v), done since (u, v) ∈ MST.

Assume that T does not contain (u, v).

Will construct a different MST T' that includes A | {(u, v)} showing its a safe edge.

Recall: a tree has unique path between each pair of vertices.

Since T is an MST, it contains a unique path p between u and v.

Path p must cross the cut (S, V − S) at least once since T spans all vertices.

Let (x, y) be an edge of p that crosses the cut. Note that if only (x, y) crosses then (u,v)=(x,y) and we'd be done.

(u, v) is a light edge, must have w(u, v) ≤ w(x, y).

Black vertices in S, white in V-S.

Except for the dashed edge (u, v) , all edges shown are in T.

A is some subset of the edges of T, but A cannot contain any edges that cross the cut (S, V − S) , since this cut respects A .

Shaded edges are in A.

Since the cut respects A, edge (x, y) is not in A.

To form T' from T :

Remove (x, y). Breaks T into two components.

Add (u, v). Reconnects.

So T' = T − {(x, y)} | {(u, v)}.

T' is a spanning tree.

w(u, v) ≤ w(x, y)                (u, v) is a light edge

w(T') = w(T) − w(x, y) + w(u, v)
        ≤ w(T)

w(T') ≤ w(T), and T is a MST, then T' must be a MST.

Need to show that (u, v) is safe for A:

A | T and (x, y) ⊆ A ⇒ A | T'

A | {(u, v)} | T'

Since T' is an MST, and (u, v) is a light edge, (u, v) is safe for A.

GENERIC-MST(G,w)
    A ← ∅
    while A is not a spanning tree
            find an edge (u, v) that is safe for A
            A ← A | {(u, v)}
    return A

A is a forest containing connected components. Initially, A is empty and each component is a single vertex.

Any safe edge merges two of these components into one. Each component is a tree.

Since an MST has exactly |V| − 1 edges, the while loop iterates |V| − 1 times. Equivalently, after adding |V|−1 safe edges, we’re down to just one component, the MST.

Corollary 23.2

If

A | MST of G = (V, E)

C = (V_C, E_C) is a connected component in the forest G_A = (V, A)

(u, v) is a light edge connecting C to some other component in G_A

i.e., (u, v) is a light edge crossing the cut (V_C, V − V_C)

then (u, v) is safe for A.

Proof Set S = V_C in the theorem.                     (corollary)

The theorem naturally leads to the algorithm called Kruskal’s algorithm to solve the minimum-spanning-tree problem.

Essence that if A | MST, then after adding a safe edge, A | MST.