Euler and Hamilton Paths & Circuits PDF

 Definition - Graph A graph is any collection of Dots (Vertices) Arcs/Lines (Edges) that join the points Examples 2  Two Special Cases 1. Loops A...

 Definition - Graph A graph is any collection of Dots (Vertices) Arcs/Lines (Edges) that join the points Examples 2  Two Special Cases 1. Loops A 2. Isolated Points D B C We will avoid isolated points 3  Euler Paths and Circuits The Seven bridges of Königsberg C c D A a d B b  Euler Paths and Circuits An Euler path is a path using every edge of the graph G exactly once. An Euler circuit is an Euler path that returns to its start. C Does this graph have an Euler circuit? D A N B o. Euler Circuits in Graphs Here is an euler circuit for this graph: (1,8,3,6,8,7,2,4,5,6,2,3,1)  Example Which of the following graphs has an Euler circuit? a b a b a b e e d c d c c d e yes no no (a, e, c, d, e, b, a)  The Degree of a Vertex The degree of a vertex is the number of times the vertex is touched by an edge Degree Evenness/ A A oddness E B B C D C D E Counting vertices, edges, degrees applet 13 This graph has 1. 6 edges, 4 vertices (exactly 2 of which are odd) 2. 4 edges, 6 vertices (all of which are odd) 3. 6 edges, 4 vertices (all of which are odd) 4. 4 edges, 4 vertices (exactly 2 of which are odd) Ans: 14 This graph has E A 1. 8 edges, 5 vertices (none of which are odd) C 2. 8 edges, 5 vertices (exactly 2 of which are odd) B 3. 8 edges, 5 vertices (exactly 4 of which are odd) 4. 8 edges, 5 vertices (all of which are odd) D ANS: 15  7 bridges 2 islands SPLAT! Arrrgh! Expletive deleted! Ouc h! 16  7 bridges 2 islands I did it! But… 17  7 bridges 2 islands I did it! I did it! And … 18  Draw a graph with A. 4 vertices (all odd) and 5 edges B. 4 vertices (all odd) and 3 edges (no loops) 19  Draw a graph with C. 3 vertices (exactly 1 even) and 4 edges D. 3 vertices (exactly 1 odd) and 4 edges 20 All vertices of a graph could be odd 1. True 2. False Ans: 1 21 All vertices of a graph could be even 1. True 2. False 22 Consider the following floor plan. The open space represents a door that one can pass through. Represent the floor plan as a graph. 6.1 Introduction to Graphs 23 6.1 Introduction to Graphs 24  Example Which of the following graphs has an Euler circuit? a b a b a b e e d c d c c d e yes no no (a, e, c, d, e, b, a)  Example Which of the following graphs has an Euler path? a b a b a b e e d c d c c d e yes no yes (a, e, c, d, e, b, a ) (a, c, d, e, b, d, a, b) 6.1 Introduction to Graphs 27 6.1 Introduction to Graphs 28 6.1 Introduction to Graphs 29 6.1 Introduction to Graphs 30 6.1 Introduction to Graphs 31 6.1 Introduction to Graphs 32 6.1 Introduction to Graphs 33 6.1 Introduction to Graphs 34 6.1 Introduction to Graphs 35 6.1 Introduction to Graphs 36 Euler vs. Hamilton Paths & Circuits On the surface, there is a one-word difference between Euler paths/circuits and Hamilton paths/circuits: The former covers all edges; the latter covers all vertices. But oh my, what a difference that one word makes! Example 6.1 Hamilton versus Euler The figure shows a graph that (1) has Euler circuits (the vertices are all even) and (2) has Hamilton circuits. One such Hamilton circuit is A, F, B, C, G, D, E, A – there are plenty more. Summary  Euler Paths and Circuits The Seven bridges of Königsberg C c D A a d B b Leonhard Euler (“Oiler”) 1706 - 1783 41 6.1 Introduction to Graphs 42 6.1 Introduction to Graphs 43 6.1 Introduction to Graphs 44 6.1 Introduction to Graphs 45  Hamilton Circuits Yes; this is a circuit that passes through each vertex exactly once.  13-B The Traveling Salesman Problem Which path is a Hamilton circuit? A a) A B C D D C B b) A B C D A c) A B C A D d) A B C A  Finding Hamilton Circuits G1 has a Hamilton circuit: a, b, c, d, e, a G2 does not have a Hamilton circuit, but does have a Hamilton path: a, b, c, d G3 has neither. Euler Path 49 Euler Circuit 50  Genealogy Abraham Lincoln Bathsheba Thomas Herring Lincoln James Nancy Hanks Hanks 16th President Abraham Lincoln Lucy Shipley Vertices = Edges = 51 Constellations Vertices = Edges = 52