882 CHAPTER 13 Graph Theory Note that in Example 5, all the edges selected were connected to edges we had already selected. However, that will not always be the case. When we select the edges in Example 6, some will be disconnected at the time we select them. We now will apply our knowledge of minimum-cost spanning trees. Note that in examples and exercises, the graphs need not be drawn to scale. Example 5 Using Kruskal’s Algorithm Use Kruskal’s algorithm to determine the minimum-cost spanning tree for the weighted graph shown in Fig. 13.53. The numbers along the edges in Fig. 13.53 represent dollars. Solution We begin by selecting the lowest-cost edge of the graph, edge AG, which is $11 (see Fig. 13.54). Next we select the next lowest-cost edge that does not form a circuit, edge GE, which is $23. Once again, looking for the lowest-cost edge that does not form a circuit, we select edge EC, which is $31. The result of our first three selections is shown in Fig. 13.54. Looking at the original weighted graph in Fig. 13.53, we see that the next lowest-cost edge is edge AC, which is $38. However, selecting edge AC would create a circuit among vertices A C E , , ,and G, so we must not select edge AC. Instead, we select edge GH, which is $47, since it is the next lowest-cost edge and its selection does not lead to a circuit; see Fig. 13.55. Next, we select edge HF, which is $48. The next lowest-cost edge not yet selected is edge EF, which is $50. However, this edge would create a circuit among vertices E F H , , ,and G. Instead, we select edge CD, which is $53, followed by selecting edge DB, which is $57. The result of our selections thus far is shown in Fig. 13.56. Notice that the graph in Fig. 13.56 is a spanning tree. According to Kruskal’s algorithm, the tree in Fig. 13.56 is the minimum-cost spanning tree for the original weighted graph. 7 Now try Exercise 21 A 61 B G 47 50 23 31 62 71 11 57 48 38 53 H F D E C Figure 13.53 A B G 11 31 H F D E C 23 Figure 13.54 A B G 47 23 11 31 48 H F D E C Figure 13.55 A B G 47 23 31 11 57 48 53 H F D E C Figure 13.56 Example 6 An Application Using Kruskal’s Algorithm Recall from Example 3 that Stonewood College is considering the construction of awnings over a select number of sidewalks on campus. The distances, in feet, between buildings are shown in the weighted graph in Fig. 13.57. a) Determine the shortest series of sidewalks to cover so that students would be able to move between any buildings shown without being exposed to the elements. b) The cost of the awnings is $51 per foot regardless of where they are placed on campus. What will it cost to cover the sidewalks determined in part (a)? Solution a) Stonewood College is seeking a minimum-cost spanning tree for the weighted graph shown in Fig. 13.57. To determine the minimum-cost spanning tree, we use Kruskal’s algorithm. First, we select the edge MH, since it has the shortest distance and therefore has the lowest cost. We next select the edge TC, since it has the second shortest distance and it doesn’t form a circuit with our previously selected edge (see Fig. 13.58). Our third and fourth choices will be edge ST and edge MA, respectively, since these edges have the next shortest distances and they do not form a circuit with previously selected edges. The result of our first four selections is shown in Fig. 13.58. The next lowest-cost edge is edge AH. However, selection of edge AH would form a circuit with vertices A H, , and M. Instead, we choose edge SM, the next lowest-cost edge, since it does not form a circuit with the previously S M H C L E T A 148 201 42 86 68 54 222 124 217 206 278 351 275 304 Figure 13.57 68 54 H M S C L A E T 86 42 Figure 13.58
RkJQdWJsaXNoZXIy NjM5ODQ=