advertisement

Math 160, Chapter 5, Graphs, Euler Circuits Definition 1.1. a) A graph is a finite set of vertices V = {A, B, C, D, E} together with a set of edges E = {AB, AC, BC, DD, DE}, connecting the vertices. Each edge connects two vertices. b) A loop is an edge that connects a vertex to itself. c) A path is a connected sequence of edges starting at one vertex and ending at another (possibly the same). No edge can appear more than once on a path. (A vertex may be visited more than once on a path.) d) A circuit is a path that starts and ends at the same vertex. A reference point for a circuit is a designated starting point. Definition 1.2. a) A connected graph is a graph such that any two vertices can be joined by a path. b) An edge of a connected graph is called a bridge if its removal causes the graph to be disconnected. Definition 1.3. a) An Euler path is a path that covers (contains) every edge of the graph exactly once. b) An Euler circuit is a circuit that covers (contains) every edge of the graph exactly once. Definition 1.4. The degree of a vertex is the number of edges meeting at the vertex. A loop counts as two edges meeting at the vertex. Theorem 1.1. Euler’s Theorem. Let G be a connected graph. Then a) If some vertex has odd degree, then G has no Euler circuit. b) If every vertex has even degree, then G has an Euler circuit. c) If there are exactly two vertices of odd degree, then G has an Euler path that starts at one of these vertices and ends at the other. d) If there are more than two vertices of odd degree, then G has no Euler path. Definition 1.5. An algorithm is a step by step procedure for carrying out a given task. Fleury’s Algorithm for constructing an Euler circuit. 1. First check that every vertex has even degree. If not, there is no Euler circuit. 2. Start at any vertex A. 3. Proceed along any edge that is not a bridge between parts of the graph that still need to be covered (that is, don’t burn your bridges behind you). 4. Keep repeating this process, and eventually you will end up back at A. Fleury’s Algorithm for constructing an Euler path. 1. First identify the two vertices of odd degree, say A and B. 2. Start at A. 3. Proceed along any edge that is not a bridge between parts of the graph that still need to be covered, if possible. If no such edge is left, then cross the bridge. 4. Keep repeating this process, and eventually you will end up at B. Definition 1.6. To Eulerize a graph means to add edges so that the resulting graph has an Euler circuit. 2 Procedure for Eulerizing a graph. 1. Circle all vertices of odd degree. 2. Add edges that duplicate existing edges so that all vertices have even degree. Finding a “circuit”∗ that minimizes duplication of edges. If an Euler circuit exists then this is the optimal solution. Otherwise 1. Eulerize the graph, adding as few edges as possible. 2. Find an Euler circuit on the new Eulerized graph. 3. Now interpret the multiple edges connecting the same vertices as the same edge repeated twice along the circuit. * Note: We put quote marks here because this isn’t a true circuit. A true circuit can cover each edge at most once.