Discrete Mathematics for Computer Science

376 CHAPTER 6 Graph Theory

6.11.3 Kruskal's Algorithm for Weighted Graphs

Figure 6.36 shows a graph that models a communication network where the length of the

communication link is a measure of the cost associated with joining the two vertices.

The Communication Network Problem is to find a set of edges from this graph such that

all the cities are connected and the sum of the lengths of the edges is a minimum. To make

this problem clear, we introduce the notion of a value or a weight for a graph.

Boston

Minneapolis Cleveland

412. 341 486 216

207437 109

Philadelphia

294/ 71224

San Francisco 187. Louis Richmond

•/ ..1--•' Atlanta

Dallas

Figure 6.36 Communication network.

Definition 2. Let G = (V, E) be a graph. A weighted graph is a graph G together with

a function F : E -* R. The weight, or cost, or value, of an edge e is just F (e). The weight

of a subgraph H of G is W(H) = -eEE(H) F(e).

Example 1. Let the values shown on the edges of G be their weights.

Y3 4 3

1

2

5 5 4

Determine the weight of the 4-cycle with vertices 1, 2, 5, and 6. Calculate the weight of G.

Solution. W(l-2-5-6)= 1+2+1+3=7, whereas W(G) = 1+3+3+5+

1+3+2+4=22. 0

Since the cost of constructing a communication link is often proportional to the dis-

tance between the sites being connected, a weighted graph, with weights equal to the dis-

tance between the locations represented by the ends of an edge, is a good model for a

network when deciding which links to construct. The problem is to find a good spanning

tree. To measure how good a spanning tree is, one sums the weights of all the edges in-

cluded in the spanning tree. By the previous definition, this is the weight of the tree. When

the edge weights represent costs, the smaller the weight (cost), the better the tree. Thus,

the problem is to find a spanning tree of minimum weight for the network. A spanning tree

of minimum weight is called a minimum cost spanning tree (MCST).