DOC PREVIEW
UK MA 111 - LECTURE NOTES

This preview shows page 1-2-23-24 out of 24 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Excursions in Modern Mathematics, 7e: 5.5 - 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.5 - 3Copyright © 2010 Pearson Education, Inc.In this section we are going to develop the basic theory that will allow us to determine if a graph has an Euler circuit, an Euler path, or neither. This is important because, as we saw in the previous section, what are Euler circuit or Euler path questions in theory are real-life routing questions in practice. The three theorems we are going to see next (all thanks to Euler) are surprisingly simple and yet tremendously useful. Euler’s TheroemsExcursions in Modern Mathematics, 7e: 5.5 - 4Copyright © 2010 Pearson Education, Inc.■ If a graph is connected and every vertex is even, then it has an Euler circuit (at least one, usually more).■ If a graph has any odd vertices, then it does not have an Euler circuit. EULER’S CIRCUIT THEOREMExcursions in Modern Mathematics, 7e: 5.5 - 5Copyright © 2010 Pearson Education, Inc.Here is how we can use Euler’s circuit theorem. First we make sure the graph is connected. (If it isn’t, then no matter what else, an Euler circuit is impossible.) If the graph is connected, then we start checking the degrees of the vertices, one by one. As soon as we hit an odd vertex, we know that an Euler circuit is out of the question. If there are no odd vertices, then we know that the answer is yes–the graph does have an Euler circuit! How to Use the TheoremExcursions in Modern Mathematics, 7e: 5.5 - 6Copyright © 2010 Pearson Education, Inc.Figure 5-15 illustrates the three possible scenarios. The graph in Fig. 5-15(a) cannotIllustration using the Theoremhave an Euler circuit for the simple reason that it is disconnected.Excursions in Modern Mathematics, 7e: 5.5 - 7Copyright © 2010 Pearson Education, Inc.The graph in Fig. 5-15(b) is connected, but we can quickly spot odd vertices (C is one Illustration using the Theoremof them; there are others). This graph has no Euler circuits.Excursions in Modern Mathematics, 7e: 5.5 - 8Copyright © 2010 Pearson Education, Inc.But the graph in Fig. 5-15(c) is connected and all the vertices are even. This graphIllustration using the Theoremdoes have Euler circuits.Excursions in Modern Mathematics, 7e: 5.5 - 9Copyright © 2010 Pearson Education, Inc.The basic idea behind Euler’s circuit theorem is that as we travel along an Euler circuit, every time we go through a vertex we use up two different edges at that vertex–one to come in and one to go out. We can keep doing this as long as the vertices are even. A single odd vertex means that at some point we are going to come into it and not be able to get out.Summary of the TheoremExcursions in Modern Mathematics, 7e: 5.5 - 10Copyright © 2010 Pearson Education, Inc.■ If a graph is connected and has exactly two odd vertices, then it has an Euler path (at least one, usually more). Any such path must start at one of the odd vertices and end at the other one.■ If a graph has more than two odd vertices, then it cannot have an Euler path.EULER’S PATH THEOREMExcursions in Modern Mathematics, 7e: 5.5 - 11Copyright © 2010 Pearson Education, Inc.Back to the Königsberg bridges problem. In Example 5.15 we saw that the layout of theExample 5.18 The Seven Bridges of Königsberg: Part 3bridges in the old city can be modeled by the graph in Fig. 5-16(a). This graph has four odd vertices; thus, neither an Euler circuit nor an Euler path can exist.Excursions in Modern Mathematics, 7e: 5.5 - 12Copyright © 2010 Pearson Education, Inc.We now have an unequivocal answer to the puzzle: There is no possible way anyone can walk across all the bridges without having to recross some of them!How many bridges will need to be recrossed?It depends. If we want to start and end in the same place, we must recross at least two of the bridges. Example 5.18 The Seven Bridges of Königsberg: Part 3Excursions in Modern Mathematics, 7e: 5.5 - 13Copyright © 2010 Pearson Education, Inc.One of the many possible routes is shown inExample 5.18 The Seven Bridges of Königsberg: Part 3Fig. 5-16(b). In this route the bridge connecting L and D is crossed twice, and so is one of the two bridges connecting A and R.Excursions in Modern Mathematics, 7e: 5.5 - 14Copyright © 2010 Pearson Education, Inc.If we are allowed to start and end in different Example 5.18 The Seven Bridges of Königsberg: Part 3places, we can do it by recrossing just one of the bridges. One possible route starting at A, crossing bridge LD twice, and ending at R is shown in Fig.5-16(c).Excursions in Modern Mathematics, 7e: 5.5 - 15Copyright © 2010 Pearson Education, Inc.The graph in Fig. 5-17(a) is connected, andExample 5.19 Child’s Play: Part 2the vertices are all even. By Euler’s circuit theorem we know that the graph has an Euler circuit, which implies that the original line drawing has a closed unicursal tracing.Excursions in Modern Mathematics, 7e: 5.5 - 16Copyright © 2010 Pearson Education, Inc.The graph in Fig. 5-17(b) is connected andExample 5.19 Child’s Play: Part 2has exactly two odd vertices (C and D).By Euler’s path theorem,the graph has an Euler path (open unicursal tracing). Moreover, we now know that the path has to start at C and end at D, or vice versa.Excursions in Modern Mathematics, 7e: 5.5 - 17Copyright © 2010 Pearson Education, Inc.The graph in Fig. 5-17(c) has four oddExample 5.19 Child’s Play: Part 2vertices (A, B, C, and D), so it has neither an Euler path nor an Euler circuit.Excursions in Modern Mathematics, 7e: 5.5 - 18Copyright © 2010 Pearson Education, Inc.The full power of Euler’s theorems is best appreciated when the graphs get bigger. Example 5.19 Child’s Play: Part 2The graph in Fig. 5-17(d) is not extremely big, but we can no longer “eyeball” an Euler circuit or path.Excursions in Modern Mathematics, 7e: 5.5 - 19Copyright © 2010 Pearson Education, Inc.On the other hand, a quick check of the degrees of the vertices shows that K and I are odd vertices and all the rest are even. We are Example 5.19 Child’s Play: Part 2now in


View Full Document
Download LECTURE NOTES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LECTURE NOTES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LECTURE NOTES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?