Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Excursions in Modern Mathematics, 7e: 5.1 - 2Copyright © 2010 Pearson Education, Inc. 5 The Mathematics of Getting Around5.1 Euler Circuit Problems5.2 What Is a Graph?5.3 Graph Concepts and Terminology5.4 Graph Models5.5 Euler’s Theorems5.6 Fleury’s Algorithm5.7 Eulerizing GraphsExcursions in Modern Mathematics, 7e: 5.1 - 3Copyright © 2010 Pearson Education, Inc.Our story begins in the 1700s in the medieval town of Königsberg, in Eastern Europe. At the time, Königsberg was divided by a river into four separate sections, which were connected to one another by seven bridges. The old map of Königsberg shown on the next slide gives the layout of the city in 1735, the year a brilliant young mathematician named Leonhard Euler came passing through.Euler Paths and CircuitsExcursions in Modern Mathematics, 7e: 5.1 - 4Copyright © 2010 Pearson Education, Inc.Euler Paths and CircuitsExcursions in Modern Mathematics, 7e: 5.1 - 5Copyright © 2010 Pearson Education, Inc.While visiting Königsberg, Euler was told of an innocent little puzzle of disarming simplicity: Is it possible for a person to take a walk around town in such a way that each of the seven bridges is crossed once, but only once? Euler, perhaps sensing that something important lay behind the frivolity of the puzzle, proceeded to solve it by demonstrating that indeed such a walk was impossible. But he actually did much more!Euler Paths and CircuitsExcursions in Modern Mathematics, 7e: 5.1 - 6Copyright © 2010 Pearson Education, Inc.Euler laid the foundations for what was at the time a totally new type of geometry, which he called geometris situs (“the geometry of location” ). From these modest beginnings, the basic ideas set forth by Euler eventually developed and matured into one of the most important and practical branches of modern mathematics, now known as graph theory.Euler Paths and CircuitsExcursions in Modern Mathematics, 7e: 5.1 - 7Copyright © 2010 Pearson Education, Inc.The theme of this chapter is the question of how to create efficient routes for the delivery of goods and services–such as mail delivery, garbage collection, police patrols, newspaper deliveries, and, most important, late-night pizza deliveries–along the streets of a city, town, or neighborhood. These types of management science problems are known as Euler circuit problems.Euler Paths and CircuitsExcursions in Modern Mathematics, 7e: 5.1 - 8Copyright © 2010 Pearson Education, Inc.What is a routing problem? To put it in the most general way, routing problems are concerned with finding ways to route the delivery of goods and/or services to an assortment of destinations. The goods or services in question could be packages, mail, newspapers, pizzas, garbage collection, bus service, and so on. The delivery destinations could be homes, warehouses, distribution centers, terminals, and the like. Routing ProblemsExcursions in Modern Mathematics, 7e: 5.1 - 9Copyright © 2010 Pearson Education, Inc.The existence question is simple: Is an actual route possible? For most routing problems, the existence question is easy to answer, and the answer takes the form of a simple yes or no. When the answer to the existence question is yes, then a second question–the optimization question–comes into play. Of all the possible routes, which one is the optimal route? Optimal here means “the best” when measured against some predetermined variable such as cost, distance, or time.Two Basic QuestionsExcursions in Modern Mathematics, 7e: 5.1 - 10Copyright © 2010 Pearson Education, Inc.The common thread in all Euler circuit problems is what we might call, for lack of a better term, the exhaustion requirement–the requirement that the route must wind its way through . . . everywhere. Thus, in an Euler circuit problem, by definition every single one of the streets (or bridges, or lanes, or highways) within a defined area (be it a town, an area of town, or a subdivision) must be covered by the route. We will refer to these types of routes as exhaustive routes.Euler Circuit ProblemsExcursions in Modern Mathematics, 7e: 5.1 - 11Copyright © 2010 Pearson Education, Inc.After a rash of burglaries, a private security guard is hired to patrol the streets of the Sunnyside neighborhood shown next. The security guard’s assignment is to make an exhaustive patrol, on foot, through the entire neighborhood. Obviously, he doesn’t want to walk any more than what is necessary. His starting point is the southeast corner across from the school (S)–that’s where he parks his car.Example 5.1 Walking the ‘Hood’Excursions in Modern Mathematics, 7e: 5.1 - 12Copyright © 2010 Pearson Education, Inc.(This is relevant because at the end of his patrol he needs to come back to S to pick up his car.)Example 5.1Walking the ‘Hood’Excursions in Modern Mathematics, 7e: 5.1 - 13Copyright © 2010 Pearson Education, Inc.Being a practical person, the security guard would like the answers to two questions. (1) Is it possible to start and end at S, cover every block of the neighborhood, and pass through each block just once? (2) If some of the blocks will have to be covered more than once, what is an optimal route that covers the entire neighborhood? (Optimal here means “with the minimal amount of walking.”) Example 5.1 Walking the ‘Hood’Excursions in Modern Mathematics, 7e: 5.1 - 14Copyright © 2010 Pearson Education, Inc.A mail carrier has to deliver mail in the same Sunnyside neighborhood. The difference between the mail carrier’s route and the security guard’s route is that the mail carrier must make two passes through blocks with houses on both sides of the street and only one pass through blocks with houses on only one side of the street; and where there are no homes on either side of the street, the mail carrier does not have to walk at all.Example 5.2 Delivering the MailExcursions in Modern Mathematics, 7e: 5.1 - 15Copyright © 2010 Pearson Education, Inc.Example 5.2 Delivering the MailExcursions in Modern Mathematics, 7e: 5.1 - 16Copyright © 2010 Pearson Education, Inc.In addition, the mail carrier has no choice as to her starting and ending points–she has to start and end her route at the local post office (P). Much like the security guard, the mail carrier wants to find the optimal