Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 8] GRAPH THEORY 165

Fig. 8-18

Minimum Spanning Trees

SupposeGis a connected weighted graph. That is, each edge ofGis assigned a nonnegative number called
theweightof the edge. Then any spanning treeTofGis assigned a total weight obtained by adding the weights
of the edges inT.Aminimal spanning treeofGis a spanning tree whose total weight is as small as possible.
Algorithms 8.2 and 8.3, which appear in Fig. 8-19, enable us to find a minimal spanning treeTof a connected
weighted graphGwhereGhas n vertices. (In which case T must haven−1 vertices.)

Fig. 8-19

The weight of a minimal spanning tree is unique, but the minimal spanning tree itself is not. Different minimal
spanning trees can occur when two or more edges have the same weight. In such a case, the arrangement of the
edges in Step 1 of Algorithms 8.2. or 8.3 is not unique and hence may result in different minimal spanning trees
as illustrated in the following example.

EXAMPLE 8.2 Find a minimal spanning tree of the weighted graphQin Fig. 8-20(a). Note thatQhas six
vertices, so a minimal spanning tree will have five edges.

(a) Here we apply Algorithm 8.2.

First we order the edges by decreasing weights, and then we successively delete edges without disconnecting

Quntil five edges remain. This yields the following data:

Edges BC AF AC BE CE BF AE DF BD

Weight 8 7 7 7 6 5 4 4 3

Delete Yes Yes Yes No No Yes