13.4 Trees 881 additional considerations that need to be included in the decision-making process. The most common consideration is the cost of the project. To help analyze these problems, weighted graphs—graphs with costs or distances associated with each edge—and minimum-cost spanning trees are used. A B C 23 48 17 Figure 13.51 Definition: Minimum-Cost Spanning Tree A minimum-cost spanning tree is the least expensive spanning tree of all spanning trees under consideration. Example 4 Determining a Minimum-Cost Spanning Tree Examine the weighted graph in Fig. 13.51. This graph shows the costs, in dollars, associated with each edge. Determine the minimum-cost spanning tree for this graph. Solution There are three spanning trees associated with this graph; they are shown in Fig. 13.52. A B C 48 17 A B C 23 17 A B C 23 48 (b) (a) (c) Figure 13.52 The spanning tree in Fig. 13.52(a) has a cost of $48 $17 $65. + = The spanning tree in Fig. 13.52(b) has a cost of $23 $17 $40. + = The spanning tree in Fig. 13.52(c) has a cost of $23 $48 $71. + = Therefore, the minimum-cost spanning tree is shown in Fig. 13.52(b). It has a cost of $40. 7 Now try Exercise 17 Example 4 will explain how we determine a minimum-cost spanning tree for a weighted graph with three edges. The process used in Example 4 is similar to the brute force method used to determine the optimal solution to traveling salesman problems in Section 13.3. Although this process is easy to carry out for a small graph, such a process would be impossible for graphs with a large number of vertices. Fortunately, we have an algorithm, called Kruskal’s algorithm, to determine the minimum-cost spanning tree. KRUSKAL’S ALGORITHM To construct the minimum-cost spanning tree from a weighted graph: 1. Select the lowest-cost edge on the graph. 2. Select the next lowest-cost edge that does not form a circuit with the first edge. 3. Select the next lowest-cost edge that does not form a circuit with previously selected edges. 4. Continue selecting the lowest-cost edges that do not form circuits with the previously selected edges. 5. When a spanning tree is complete, you have the minimum-cost spanning tree. PROCEDURE
RkJQdWJsaXNoZXIy NjM5ODQ=