Informally, the MST problem is to find a free tree T of a given graph G that contains all the vertices of G and has the minimum total weight of the edges of G over all such trees.

Problem Formulation

Let G = (V, E, W) be a weighted connected undirected graph. Find a tree T that contains all the vertices in G and minimize the sum of the weights of the edges (u, v) of T, that is
    

w(T) = ∑ _{(u, v)ÎT}  w(u, v)

Tree that contains every vertex of a connected graph is called spanning tree.

The problem of constructing a minimum spanning tree of MST is computing a spanning tree T with smallest total weight.

Here we discuss (from CLR) Kruskal's algorithm and Prim's algorithm, which are classic application of the greedy strategy. Kruskal's algorithm grows the MST in clusters by considering (greedily) edges in order of their weights. Prim's algorithm, on other hand, grows the MST from single vertex (root), much in the same way as Dijkstra's Shortest-path algorithm.

Applications

As we have mentioned, an MST shows the most economical way of connecting all vertices of weighted graph together using the edges of the graph.

• Connect all computers in a computer science building using least amount of cable.
• Connect all logic circuits of a VLSI chip to the power source using minimum amount of telephone wires.

Note that if the weight in G are distant, then the MST is unique.

Safe Edge

The MST algorithm manages a set of edge A, maintaining the following loop invariant.

Prior to each iteration, A is a subset of some MST

At each step, we determine safe edge that can be added to A with violating this invariant. Note that AÈ{(u, v)} is also a subset of a MST.

Generic-MST(G, w)

A ←{ }
while set A does not form a spanning tree
    do find a safe edge (u, v) for A
        AÎAÈ{(u, v)}
return A

Some Definition

1. A cut (S, V - S) of an undirected graph G = (V, E) is a partition of V. In this example, S = {a, b, d, e} and V-S = {c, f, g, h, i}

2. A cut respects a set A of edges if no edge in A crosses the cut.

3. An edge (u, v) Î E crosses the cut (S, V-S) if one of its endpoint is in S and the other is in V-S). In this example, Edges (b, c), (b, h), (a, h), (d, f) and (e, f) cross the cut (S, V-S).

4. An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut. Note that there can be more than one light edge crossing a cut. In this example, cut namely, the light edge is (d, c)

DIAGRAM

Theorem  Let G be a weighted connected graph, and let S and V-S be partition of the vertices of G. Furthermore, let (u, v) be a light edge. There is A MST that has (u, v) as one of its edges i.e., (u, v) is a safe edge.

Proof

Let T be the MST of G. If T does not contain edge (u, v), the addition of (u, v), the addition of (u, v) to T must create a cycle. Therefore, there is some edge (x, y) of this cycle that is light edge. Moreover by the choice of (u, v), w(u, v) ≤ w(x, y). If we remove (x, y) from TÈ{(u, v)}, we obtained a spanning tree whose total weight is no more than before. Since T was a MST, this new tree must also be MST.

Now we would like to show that if edge weights are unique in the given graph, then there is a unique MST.

One way of showing this is to consider a MST T of a graph G = (V, E) and let L be the sorted list of edge weights of T. Then, simply show that for any other MST say T` of same graph G, the list is also the sorted list of edge weights of T`.

In order to show this first we develop notation. Then apply a substitution argument.

Suppose the sorted list of edges weights for MST T is

        L = b₁, b₂, . . . , b_k

and corresponding list of edges is

                e₁, e₂, . . . , e_k

Suppose that the sorted list of edge weights for any other MST T` is

        L` = c₁, c₂, . . . , c_k

and corresponding list of edges is

                f₁, f₂, . . . , f_k

Note that list L and L` may have duplicate elements. Each list has length k = |V| - 1, where |V| is the cardinality of the set of vertices of G.

Now we wish to show that L = L`. We proceed by a substitution argument. Let i be the first position where e_i f_i, that is, the first position where edge lists differ. Without loss of generality, assume that

        w(e_i) = b_i ≤ c_i = w(f_i)

Let H = T`Èe<sub>i</sub>. If H is a tree, than e<sub>i</sub> is in T` already, so we could have written the list of edges for T` so that e<sub>i</sub>=f<sub>i</sub>. Otherwise H contains a unique cycle C. Consider S = C-T, all the edges in C that are not in T and hence are in T`. Since all the edges in T` of weight less than or equal to b<sub>i</sub> are in T also, all edges in S have weights greater than or equal to c<sub>i</sub>. Let r belongs to S be of minimum weight. Since (T`Èe_i)-r is also a spanning tree, we must have bi grater than or equal to w(r). Hence, w(r)=b_i. We can substitute ei for r in T` without changing L`. Thus also moves the first position where the edge lists differ from the right iterating this substitution, we eventually must terminate with the list of edges identical and hence

L = L`

Thus result implies that if edge weights are unique, then there is a unique MST.