5 The Mathematics of Getting Around 5 1 Euler Circuit Problems 5 2 What Is a Graph 5 3 Graph Concepts and Terminology 5 4 Graph Models 5 5 Euler s Theorems 5 6 Fleury s Algorithm 5 7 Eulerizing Graphs Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 2 Euler Paths and Circuits 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 Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 3 Euler Paths and Circuits Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 4 Euler Paths and Circuits 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 Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 5 Euler Paths and Circuits 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 Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 6 Euler Paths and Circuits 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 Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 7 Routing Problems 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 Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 8 Two Basic Questions 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 Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 9 Euler Circuit Problems 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 Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 10 Example 5 1 Walking the Hood 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 Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 11 Example 5 1 Walking the Hood This is relevant because at the end of his patrol he needs to come back to S to pick up his car Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 12 Example 5 1 Walking the Hood 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 Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 13 Example 5 2 Delivering the Mail 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 Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 14 Example 5 2 Delivering the Mail Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 15 Example 5 2 Delivering the Mail 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 route that would allow her to cover the neighborhood with the least amount of walking Put yourself in her shoes and you would do the same good weather or bad she walks this route 300 days a year Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 1 16 Example 5 3 The Seven Bridges of K nisberg Figure 5 2 a shows an old map of the city of K nigsberg and its seven bridges Fig 5 2 b shows a modernized version of the very same layout We opened the chapter with