13.4 Trees 883 We can also use Kruskal’s algorithm to build a minimum-cost spanning tree from information that is not given in graph form. We demonstrate this in our next example. selected edges (see Fig. 13.59). Our next lowest-cost edge will be edge CL. Note that edge CL does not form a circuit with the previously selected edges. The result of all our selections so far is shown in Fig. 13.59. We note that the next lowest-cost edge is edge TA, but selecting this edge would create a circuit with vertices S M A , , ,and T. So we select edge AE. The result of our selections so far is shown in Fig. 13.60. From Fig. 13.60, we can see that we have formed a spanning tree. According to Kruskal’s algorithm, this graph is the minimum-cost spanning tree. Therefore, Fig. 13.60 shows which sidewalks should be covered with awnings. Covering these sidewalks will provide protection to students at the lowest cost to Stonewood College. b) From Fig. 13.60, we see that there are 148 42 68 86 54 217 + + + + + + 201 816 = feet of sidewalks that need to be covered. At $51 per foot, the cost to cover these sidewalks is $51 816 $41,616. × = 7 Now try Exercise 27 S C L E M H A T 148 201 68 86 54 42 Figure 13.59 S T M A H C L E 201 217 86 68 54 148 42 Figure 13.60 Example 7 Colorado Bicycle Paths The Colorado Parks and Recreation Association wishes to build bicycle trails that connect the cities of Aurora, Boulder, Denver, Englewood, and Golden. The approximate distances, in miles, between these cities are given in Table 13.5. Kruskal’s Algorithm Table 13.5 Aurora Boulder Denver Englewood Golden Aurora * 42 9 15 30 Boulder 42 * 34 41 26 Denver 9 34 * 8 16 Englewood 15 41 8 * 21 Golden 30 26 16 21 * a) Use Kruskal’s algorithm to determine the minimum-cost spanning tree that would link each city and create the shortest total distance for the bicycle trails. b) If the cost of building the bicycle trails is $5500 per mile, determine the cost of building the bicycle trails determined in part (a). Solution a) To begin constructing the minimum-cost spanning tree, we draw five labeled vertices that represent the five cities as shown in Fig. 13.61. Note that the exact location of the vertices is unimportant and the distance between the vertices does not need to be drawn to scale. A B E G D Figure 13.61 A B E G 9 8 D Figure 13.62 Instructor Resources for Section 13.4 in MyLab Math • Objective-Level Videos 13.4 • Animation: Kruskal's Algorithm • PowerPoint Lecture Slides 13.4 • MyLab Exercises and Assignments 13.4 • Chapter 13 Projects
RkJQdWJsaXNoZXIy NjM5ODQ=