884 CHAPTER 13 Graph Theory Did You Know? Data Networks In our current “information age,” data networks support so many daily conveniences that we probably don’t even realize a network is involved. Each time we use a smartphone, fly in an airplane, send an e-mail, or use the Internet, we are using some form of modern data network. Each of these networks can be represented as a graph with many vertices and edges. It might surprise you to know that data networks predate the twentieth century. The most well-known example of a primitive data network is the electromagnetic telegraph used in the nineteenth century in the United States and around the world prior to the invention of the telephone. An even older example of a data network is the optical telegraph (with nearly 1000 stations) used in the eighteenth century all across Europe. Perhaps the oldest, yet maybe the slowest, form of data network is one still in use today: the writing and sending of letters! Rodan/Shutterstock A B E G 9 8 16 D Figure 13.63 A B E G 9 8 16 26 D Figure 13.64 Next, study the distances given in Table 13.5. The shortest distance listed in the table is between Denver and Englewood, 8 miles. The next shortest distance is between Aurora and Denver, 9 miles. Thus we include edge DE and edge AD, respectively, as shown in Fig. 13.62. The next shortest distance is between Aurora and Englewood, 15 miles. However, inclusion of edge AE would create a circuit among vertices A D, , and E; therefore, we do not include edge AE. Instead, we note that the next shortest distance is between Denver and Golden, 16 miles, and that including edge DG does not create any circuits. Thus, we include edge DG as shown in Fig. 13.63. The next shortest distance is between Englewood and Golden, 21 miles. However, inclusion of edge EG would create a circuit among vertices D E, , and G; therefore, we do not include edge EG. Instead we note that the next shortest distance is between Boulder and Golden, 26 miles, and that including edge BG does not create any circuits. Thus, we include edge BG as shown in Fig. 13.64. Now try Exercise 29 We now have a spanning tree. According to Kruskal’s algorithm, Fig. 13.64 shows the minimum-cost spanning tree. Fig. 13.64 represents the bicycle trails that join the given cities with the shortest total distance. b) From Fig. 13.64, we can see that there are 8 9 16 26, + + + or 59 miles of bicycle trails needed. At a cost of $5500 per mile, the cost to create these trails is $5500 59, × or $324,500. 7 Exercises SECTION 13.4 Warm Up Exercises In Exercises 1– 6, fill in the blanks with an appropriate word, phrase, or symbol(s). 1. A connected graph in which each edge is a bridge is called a(n) _______. Tree 2. If you remove any edge in a tree, it creates a(n) _______ graph. Disconnected 3. A tree does not have any Euler or Hamilton _______. Circuits 4. A tree that is created from another graph by removing edges while still maintaining a path to each vertex is called a(n) _______ tree. Spanning 5. The least expensive spanning tree of all spanning trees under consideration is called the _______ spanning tree. Minimum-cost 6. To determine the minimum-cost spanning tree for a weighted graph, we can use _______ algorithm. Kruskal’s
RkJQdWJsaXNoZXIy NjM5ODQ=