We will denoted edges in the spanning tree as tree edges and those edges not part of the spanning tree asnontree edges.
The minimum spanning tree problem arises in a wide number of applications both as a “stand alone” problem but also as subproblem in more complex prob-lems.
As an example consider a telecommunication company planning to lay cables to a new neighborhood. In its operations it is constrained to only lay cables along certain connections represented by the edges. At the same time a network that reaches all houses must be build (ie. a spanning tree). For each edge a cost of digging down the cables have been computed. The MST gives us the cheapest solution that connects all houses.
At some few occasions you might meet the maximum spanning tree problem (or as Wolsey calls it the “maximum weight problem”). Solving the maximum spanning tree problem, where we wish to maximize the total cost of the con-stituent edges, can be solved by multiplying all costs with−1 and the solve the minimum spanning problem.
3.1 Optimality conditions
A central concept in understanding and proving the validity of the algorithms for the MST is the concept of acut in an undirected graph. A cutC={X, X′} is a partition of the set of vertices into two subsets. For X⊂V, denote the set of arcs crossing the cut δX={(u, v)∈E :u∈X, v∈V \X}. The notion of a cut is shown in Figure 3.2. Edges that have one endpoint in the setX and the other in the endpointX′ is said tocross the cut.
We say that a cutrespectsa setAof edges if no edge inAcrosses the cut.
Let us use the definition of a cut to establish a mathematical model for the problem.
We define a binary variable xij for each edge (i, j). Let xij=
1 if (i, j) is in the subgraph 0 otherwise
For a spanning tree of n vertices we needn−1 edges. Furthermore, for each possible cutCat least one of the edges crossing the cut must be in the solution
26 The Minimum Spanning Tree Problem
X
X’
Figure 3.2: The cut C defined by the partitioning X ⊂V and X′ =V \X is shown for a graphG. The edges crossing the cut{X, X′}are shown in bold.
– otherwise the subgraph defined by the solution is not connected. Therefore we get the following model:
The Cut-set formulation of the MST
min X
e∈E
wexe
s.t. X
e∈E
xe=n−1 X
e∈δ(S)
xe≥1, ∅ ⊂S⊂V xe∈ {0,1}
Sub tour elimination formulation of the MST
min X
e∈E
wexe
s.t. X
e∈E
xe=n−1 X
e∈γ(S)
xe≤ |S| −1, ∅ ⊂S⊂V xe∈ {0,1}
whereγ(S) ={(i, j) :i∈S, j∈S}.
Note that with the definition of a cut if we delete any tree edge (i, j) from a
3.1 Optimality conditions 27
spanning tree it will partition the vertex set V into two subsets. Furthermore if we insert an edge (i, j) into a spanning tree we will create exactly one cycle.
Finally, for any pair of vertices i and j, the path from i to j in the spanning tree will be uniquely defined (see Figure 3.3).
1 2
Figure 3.3: Adding the edge (1,4) to the spanning tree forms a unique cycle h1,4,5,2,1i
In this chapter we will look at two algorithms for solving the minimum spanning tree problem. Although different they both use the greedy principle in building an optimal solution. The greedy principle advocates making the choice that is best at the moment, and although it in general is not guaranteed to provide optimal solutions it does in this case. In many textbooks on algorithms you will also see the algorithms for the minimum spanning tree problem being used as it is a classical application of the greedy principle.
The greedy strategy shared by both our algorithms can be described by the following “generic” algorithm, which grows the minimum spanning tree one edge at a time. The algorithm maintains a setAwith the following condition:
Prior to each iteration, A is a subset of edges of some minimum spanning tree.
At each iteration we determine an edge (i, j) that can be added to A without breaking the condition stated above. So that if A is a subset of edges of some minimum spanning tree before the iteration thenA∪ {(i, j)}is a subset of edges of some minimum spanning tree before the next iteration.
An edge with this property will be denoted asafeedge. So we get the following selection rule for a “generic” algorithm.
28 The Minimum Spanning Tree Problem
Algorithm 1: The Selection rule
select a cut in Gthat does not contain any selected edges
1
determine a safe edge of the cut-set and select it
2
if there are more than one safe edge select a random one of these
3
So how do we use the selection rule?
• The selection rule is used n−1 times as there are n−1 edges in a tree withnvertices. Each iteration will select exactly one edge.
• Initially none of the edges in the graph are selected. During the process one edge at a time will be selected and when the methods stops the selected edges form a MST for the given graphG.
Now the interesting question is, of course, how do find these safe edges? First, a safe edge must exist. The condition defines that there exists a spanning tree T such thatA⊆T. AsA must be a proper subset ofT there must be an edge (i, j)∈T such that (i, j)6∈A. The edge (i, j) is therefore a safe edge.
In order to come up with a rule for recognizing safe edges we need to define a light edge. A light edge crossing a cut is an edge with the minimum weight of any edge crossing the cut. Note that there can be more than one light edge crossing a cut. Now we can state our rule for recognizing safe edges.
Theorem 3.1 Let G= (V, E, w)be a connected, undirected graph (V, E) with a weight function w : E → R. Let A be a subset of E that is part of some minimum spanning tree forG. Let{S,S}¯ be any cut ofGthat respectsA, and let(i, j)be a light edge crossing the cut{S,S}. Then, edge¯ (i, j)is safe for A.
Proof: LetT be a minimum spanning tree that includesA. IfT contains the light edge (i, j) we are done, so lets assume that this is not the case.
Now the general idea of the proof is to construct another minimum spanning treeT′ that includesA∪ {(i, j)} by using a cut-and-paste technique. This will then prove that (i, j) is a safe edge.
If we look at the graph T∪ {(i, j)} it contains a cycle (see Figure 3.4). Let us call this cycle p. Sincei andj are on opposite sides of the cut {S,S}, there is¯ at least one edge inT on the pathpthat also crosses the cut. Let (k, l) be such an edge. As the cut respectsA (k, l) cannot be inA. Furthermore as (k, l) is
3.1 Optimality conditions 29
i j
l k
S
S’
p
Figure 3.4: The edges in the minimum spanning tree T is shown, but not the edges inG. The edges already inAare drawn extra fat, and (i, j) is a light edge crossing the cut {S, S′ = ¯S}. The edge (k, l) is an edge on the unique path p fromito jin T. A minimum spanning tree T′ that contains (i, j) is formed by removing the edge (k, l) fromT and adding (i, j).
30 The Minimum Spanning Tree Problem
on the unique path in T from ito j T would decompose into two components if we remove (k, l).
Adding (i, j) reconnects the two components thus forming a new spanning tree T′=T\ {(k, l)} ∪ {(i, j)}. The question is whetherT′ is a spanning tree?
Since (i, j) is a light edge (that was one of the initial reasons for picking it) crossing the cut{S,S¯}and (k, l) also crosses the cut minimum spanning tree, (i, j) is safe forA.△
Now we can look at how an execution of the generic algorithm would look like.
The selection rule tells us to pick a cut respecting A and then choose an edge of minimum weight in this cut.
Figure 3.5 illustrates the execution of the generic algorithm. Initially no edges are selected. We can consider any cut we would like. Let us use the cutX ={6}
andX′ =V \X (a). The cheapest edge crossing the cut is (4,6). It is is added to the solution. We can now pick any cut not containing the edge (4,8). We consider the cut X = {1,4,6} (b). Cheapest edge crossing the cut is (4,5) which is added to the solution. Next we consider the cutX ={2}(c). Here the cheapest edge crossing the cut is (2,3) which is added to the solution. Now let us consider the cut X ={1,2,3} (d). The edge (3,5) is now identified as the cheapest and is added to the solution. The next cut we consider isX ={1}(e).
This will add (1,4) to the solution, which has become a spanning tree. We can not find any cuts that does not contain edges in the tree crossing the cut (f).
More conceptually A defines a graph GA = (V, A). GA is a forest, and each of the connected components ofGA is a tree. When the algorithm begins Ais empty and the forests containsntrees, one for each vertex. Moreover, any safe edge (i, j) for Aconnects distinct components ofGA, sinceA∪ {(i, j)}must be acyclic.
The two algorithms in section 3.2 and 3.3 use the following corollary to our theorem.
3.1 Optimality conditions 31
(a) Starting graph
1 2
3
4 5
6 4
4
1
2 3
6 3 2
(b) Step 1
(c) Step 2 (d) Step 3
(e) Step 4
1 2
3
4 5
6 4
4
1
2 3
6 3
2
(f) Step 5
Figure 3.5: The execution of the generic algorithm on our sample graph.
Corollary 3.2 Let G= (V, E, w)be a connected, undirected graph with weight function w:E→R. LetA be a subset ofE that is included in some minimum spanning tree for G, and let C= (VC, EC)be a component in the forest GA = (V, A). If (i, j) is a light edge connecting C to some other component in GA, then (i, j)is safe for A.
32 The Minimum Spanning Tree Problem
Proof: The cut {VC,V¯C} respects A, and (i, j) is a light edge for this cut.
Therefore (i, j) is safe for A. △