Minimum Spanning Tree Concept

Definition: For a connected undirected graph G = <V, E>, its spanning tree is a subgraph which is a tree including all vertices of G.

A graph may contain many spanning trees.

Definition: For a connected, undirected, weighted graph, its Minimum Spanning Tree (MST) is a spanning tree with the minimum sum of weights of its edges, among all spanning trees of the graph.

A graph may contain more than one MST.

The MST problem consists in finding a MST in a given weighted undirected graph. It is an example of a so called optimization problem. In such problems, we have a problem itself, solution constraints and an objective function. It is necessary to find a solution that satisfies the constraints and brings the maximum (or minimum) value to the objective function. Here a solution is a subset of edges of an original graph. The solution constraint is that the selected graph edges should make a spanning tree. The objective function is W(T_j) = where is the weight of edge #i included in spanning tree T_j.

Note: The total number of edges in any spanning tree is one less than the number of vertices in the original graph.

Many real life problems are formally stated in terms of finding a MST in a weighted graph:

- Suppose, an airline company carries passengers between n given airports. If the objective is to minimize the total cost of flights for the company, then the flight routs may be planned as edges of a MST in a complete graph with n vertices.

- Suppose, n new settlements are constructed in an unpopulated plain area. It is necessary to bring the electrical power to all new settlements, to keep the electrical equipment only within settlements, and to spend the minimum sum of money on the project. Here settlements (the graph vertices) should be connected by electrical lines that make a MST in a complete graph. The edges of the complete graph are just straight lines on a map.

- The servers of a network may be connected as a MST to pass a message at a minimum cost, etc.

A completegraph of n vertices contains n^n-2 different spanning trees. Hence, it is not feasible to find a MST for an arbitrary graph by generating all its spanning trees (brute force approach). The number of such trees can be prohibitive. Several effective algorithms have been designed to solve this problem. Their time efficiency is in Θ(|V|²) or better.

Kruskal’s algorithm (Kruskal J., 1956) constructs a MST for a given undirected connected weighted graph.

The idea of Kruskal’s algorithm:

Any tree of |V| vertices should contain |V| - 1 edges. So |V| - 1 edges of graph G<V, E, W> are included in its MST in ascending order of weights of edges. A current edge is not included if it makes a loop with the edges previously included in the MST.

Kruskal’s algorithm.

Input: Undirected connected weighted graph G = <V, E, W>.

Output: Subgraph T_M = < V_M, E_M, W_M> that is a MST for G.

{ V_M = {Ø}; E_M = {Ø}; W_M = {Ø};

Arrange edges of E in G in ascending order of their weights.

while (|E_M| < |V| - 1)

{ if(current minimum weight edge e = {x, y} from E makes a cycle with edges in E_M)

skip e;

else

add e to T_M: V_M = {V_M}È{x}È {y}; E_M = {E_M}È{x, y}; W_M = {W_M}È{w(x, y)};

}

} //Kruskal’s algorithm