COMS 482: unofficial class blog

Minimum Spanning Tree (MST):

Given a connected graph G=(V,E), a spanning tree is a connected subgraph on V. A minimal spanning tree is a spanning tree with the minimal number of edges.

“A spanning tree is a tree.”

To not be a tree, it must (a) be not connected or (b) have a cycle. By definition, (a) is false, because an MST is defined as a connected subgraph. For (b), if a cycle exists we can erase any edge in the cycle and still maintain connectedness.

Each edge has a cost. The minimum spanning tree is a least total cost tree. For example:

MST Algorithm:

• Choose all edges, dropping expensive edges until you have a complete tree
• Choose least cost edges that do not make a cycle (Kruskal’s)
• Build a single tree, always adding least cost edges (Prim’s)

Kruskal’s Algorithm:

Sort edges by cost
T = {}
for e in edges do
    if e does not create a cycle then
        add e to T
    endif
endfor

Prim’s Algorithm:

Choose a start vertex s
T = {s}
While there is a vertex not in T do
    choose least cost edge from T to some vertex not in T
    add this edge to T
endwhile

“Kruskal’s algorithm produces an MST”

Let k₁, … , k_n-1 be edges added by Kruskal’s algorithm in the order added. Assume k₁, … , k_n-1 is not an MST. Then let k_i be the first edge added that makes it impossible to extend k₁, … , k_i to an MST. Consider a true MST that uses k₁, … , k_i-1. Let k₁, … , k_i-1,m_i, …, m_n-1 be the true MST. If we add k_i to k₁, … , k_i-1,m_i, …, m_n-1 (true MST) then we get a cycle. This cycle contains some edge m_j where j >= i. The cycle cannot be all k’s because Kruskal’s algorithm would not have added k.

Consider the graph from adding k_i and removing m_j in k₁, … , k_i-1,m_i, …, m_n-1. We still have a spanning tree, with three cases:

1. |k_i| < |m_j| => Contradiction, because the new tree has less cost than the true MST
2. |k_i| > |m_j| => Contradiction, because m_j would have been chosen by Kruskal's algorithm before k_i.
3. |k_i| = |m_j| => Contradiction, because now both trees are MST and have the same cost, but k_i was chosen to not be in an MST with k₁, … , k_i.