Discrete Mathematics for Computer Science

378 CHAPTER 6 Graph Theory

6.11.4 Correctness of Kruskal's Weighted Graph Algorithm

Since the order in which the edges are considered is the only difference between this ver-

sion of Kruskal's algorithm and the earlier version for unweighted graphs, the algorithm

correctly finds a spanning tree.

It remains to be proven that this algorithm generates an MCST. Let G = (V, E) be

a weighted, connected graph with weight function c. Let T be a weighted spanning tree

generated by Kruskal's algorithm. Let T 1 be an MCST for G. Let E(T) be the edges of

T and E(T 1 ) be the edges of T 1 .If E(T) = E(TI), then T is also an MCST. If E(T) :

E(T 1 ), let e be a minimum cost edge such that e E E(T) and e 0 E(TI). Observe that

every edge of T with a weight strictly less than the weight of e is included in E(T 1 ) because

of the way that e is chosen.

The graph E(T 1 ) U {e} contains a unique cycle (see Exercise 6 in Section 6.13)-say,

el, e2, e3, ... , ek, e

Let ej be an edge on this cycle such that ej g E(T). The edge ej exists or else the cycle

el, e2,..., ek, e

would also be contained in T, which is a contradiction. If c(ej) < c(e), then ej would

have been included in T by the way that e was chosen. Therefore, c(ej) > c(e).

Now, consider the graph T 2 with edge set E(T 1 ) U (el. Removal of any edge of the

cycle

el, e2, ... , ek, e

will result in a spanning tree. In particular, removing ej results in a spanning tree T3 with

a cost no more than the cost of T 1 since c(ej) > c(e). Since T, is an MCST, T3 must also

be an MCST.

The argument that T 3 is an MCST is worth a more careful look, because it is useful

in other contexts. We started with T 1 being an MCST with weight wt 1. We then showed

that the weight of T 3 -say, wt2-has the property that wt2 < wtl. Now, if wt2 < wtl

we would be contradicting the fact that T 1 is an MCST. Therefore, wt 1 = wt2, and 7T3 has

the same weight as T 1 , which makes T3 an MCST. Notice that we did not claim T 1 was the

only MCST, just one of the possible choices.

After at most I V(Ti) I - I transformations of the sort described, all the edges of T 1

not contained in T will be replaced by edges of T. Hence, T is an MCST.

Rooted Trees

In a family tree, such as that shown in Figure 3.2 (see Section 3.1), there is a clear in-

terpretation of the edges and vertices as being on paths from the root. The relation being

represented precludes thinking of edges as "going both ways." The special tree used to rep-

resent such relations is called a rooted tree. A rooted tree consists of a tree together with

one vertex distinguished as a root. For any vertex in a rooted tree, other than the root, there

is a unique path from the root to the vertex. We view the edges as directed along the path

from the root to a vertex (see Theorem 2 in Section 6.10.2). With this interpretation of di-