Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Excursions in Modern Mathematics, 7e: 5.7 - 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.7 - 3Copyright © 2010 Pearson Education, Inc.In this section we will finally answer some of the routing problems raised at the beginning of the chapter. Their common thread is the need to find optimal exhaustive routes in a connected graph.How is this done? Let’s first refresh our memories of what this means. We will use the term exhaustive route to describe a route that travels along the edges of a graph and passes through each and every edge of the graph at least once.Exhaustive RoutesExcursions in Modern Mathematics, 7e: 5.7 - 4Copyright © 2010 Pearson Education, Inc.Such a route could be an Euler circuit (if the graph has no odd vertices) or an Euler path (if the graph has two odd vertices), but for graphs with more than two odd vertices, an exhaustive route will have to recross some of the edges. This follows from Euler’s theorems.We are interested in finding exhaustive routes that recross the fewest number of edges. Why? Exhaustive RoutesExcursions in Modern Mathematics, 7e: 5.7 - 5Copyright © 2010 Pearson Education, Inc.In many applications, each edge represents a unit of cost. The more edges along the route, the higher the cost of the route. In an exhaustive route, the first pass along an edge is a necessary expense, part of the requirements of the job. Any additional pass along that edge represents a wasted expense (these extra passes are often described as deadhead travel). Thus, an exhaustive route that minimizes cost (optimal exhaustive route) is one with the fewest number of deadhead edges.Exhaustive RoutesExcursions in Modern Mathematics, 7e: 5.7 - 6Copyright © 2010 Pearson Education, Inc.We are now going to see how the theory developed in the preceding sections will help us design optimal exhaustive routes for graphs with many (more than two) odd vertices. The key idea is that we can turn odd vertices into even vertices by adding “duplicate” edges in strategic places. This process is called eulerizing the graph. Eulerizing GraphsExcursions in Modern Mathematics, 7e: 5.7 - 7Copyright © 2010 Pearson Education, Inc.The graph represents a 3 block by 3 block street grid consisting of 24 blocks. How can we find an optimal route that covers all theExample 5.22 Covering a 3 by 3 Street Gridedges of the graph and ends back at the starting vertex? Our first step is to identify the odd vertices. This graph has eight odd vertices (B, C, E, F, H, I, K, and L), shown in red.Excursions in Modern Mathematics, 7e: 5.7 - 8Copyright © 2010 Pearson Education, Inc.When we add a duplicate copy of edges BC, EF, HI, and KL, we get this graph. This is a eulerized version of the original graph–its Example 5.22 Covering a 3 by 3 Street Gridvertices are all even, so we know it has an Euler circuit. Moreover, it’s clear we couldn’t have done this with fewer than four duplicate edgesExcursions in Modern Mathematics, 7e: 5.7 - 9Copyright © 2010 Pearson Education, Inc.This figure shows one of the many possible Euler circuits, with the edges numbered in the order they are traveled. The Euler circuit represents an exhaustive closed route alongExample 5.22 Covering a 3 by 3 Street Gridthe edges of the original graph, with the four duplicate edges (BC, EF, HI, and KL) indicating the deadhead blocks where a second pass is required.Excursions in Modern Mathematics, 7e: 5.7 - 10Copyright © 2010 Pearson Education, Inc.The total length of this route is 28 blocks (24 blocks in the grid plus 4 deadhead blocks), and this route is optimal–no matter how clever you are or how hard you try, if you Example 5.22 Covering a 3 by 3 Street Gridwant to travel along each block of the grid and start and end at the same vertex, you will have to pass through a minimum of 28 blocks!Excursions in Modern Mathematics, 7e: 5.7 - 11Copyright © 2010 Pearson Education, Inc.The graph in the figure represents a 4 block by 4 block street grid consisting of 40 blocks. The 12 odd vertices in the graph are shown inExample 5.23 Covering a 4 by 4 Street Gridred. We want to eulerize the graph by adding the least number of edges.Excursions in Modern Mathematics, 7e: 5.7 - 12Copyright © 2010 Pearson Education, Inc.This figure shows how not to do it! This graph violates the cardinal rule of eulerization–you can only duplicate edges that are part ofExample 5.23 Covering a 4 by 4 Street Gridthe original graph. Edges DF and NL are new edges, not duplicates, so this figure is out!Excursions in Modern Mathematics, 7e: 5.7 - 13Copyright © 2010 Pearson Education, Inc.This figure shows a legal eulerization, but it is not optimal, as it is obvious that we could have accomplished the same thing byExample 5.23 Covering a 4 by 4 Street Gridadding fewer duplicate edges.Excursions in Modern Mathematics, 7e: 5.7 - 14Copyright © 2010 Pearson Education, Inc.This figure shows an optimal eulerization of the original graph–one of several possible. Once we have an optimal eulerization, we have the blueprint for an optimal exhaustiveExample 5.23 Covering a 4 by 4 Street Gridclosed route on the original graph. Regardless of the specific details, we now know that the route will travel along 48 blocks–the 40 original blocks in the grid plus 8 deadhead blocks.Excursions in Modern Mathematics, 7e: 5.7 - 15Copyright © 2010 Pearson Education, Inc.In some situations we need to find an exhaustive route, but there is no requirement that it be closed–the route may start and end at different points. In these cases we want to leave two odd vertices on the graph unchanged and change the other odd vertices into even vertices by duplicating appropriate edges of the graph.Open RouteExcursions in Modern Mathematics, 7e: 5.7 - 16Copyright © 2010 Pearson Education, Inc.This process is called a semi-eulerization of the graph. When we strategically choose how to do this so that the number of duplicate edges is as small as possible, we can obtain an optimal exhaustive open route. In