860 CHAPTER 13 Graph Theory In our first two sections on graph theory, we introduced key concepts and theory that allowed us to represent physical settings as graphs and to solve some problems relating to these settings. We solved problems dealing with the bridges of Königsberg, a vacation in the southwestern United States, the doorways of a gym, and the street blocks involved in a neighborhood crime stopper program. Although these problems are very different, they are all related because in each case a graph is used to represent a physical setting. There are many other examples of how Euler paths and Euler circuits can be applied to real-life problems, including problems that deal with the most efficient route for a snowplow or a street sweeper. Another example of a path problem is found in the classic arcade games Pac-Man and Ms. Pac-Man (Fig. 13.34). In both these games, the ideal path (disregarding the ghosts) is an Euler path. We are now at vertex F with choices of edge FC, edge FJ, or edge FI. Notice that edge FI is a bridge (it connects vertices A E, , and I to the rest of the untraced graph). We can therefore choose either edge FC or edge FJ. Let us choose edge FC, which will put us at vertex C (see Fig. 13.32). At vertex C, our only choice is edge CG. A H E B C D I J K F G 1 2 3 4 5 6 7 8 9 10 11 12 Start here Figure 13.32 We are now at vertex G and have to choose between edge GJ and edge GG (which is a loop): see Fig. 13.32. Since GJ is a bridge, we choose the edge GG. We then are back at vertex G. Here and throughout the rest of our circuit we only have one choice at each of the remaining vertices. We trace each of these remaining edges to get the result given in Fig. 13.33. A H E B C D I J K F G 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Start here Figure 13.33 The circuit given in Fig. 13.33 gives one possible Euler circuit that would provide the residents of Greenbriar with one way to cover each street block exactly one time starting and ending at vertex A. Fleury’s algorithm could be used to determine many alternative circuits. You will be asked to determine several such alternative circuits in Exercises 47 through 50. 7 Now try Exercise 39 Figure 13.34 The game Ms. Pac-Man ArcadeImages/Alamy Stock Photo Instructor Resources for Section 13.2 in MyLab Math • Objective-Level Videos 13.2 • Animation: Euler Circuits • PowerPoint Lecture Slides 13.2 • MyLab Exercises and Assignments 13.2
RkJQdWJsaXNoZXIy NjM5ODQ=