Euler circle problem

Euler graph decomposed into edge-disjoint circles. An Euler tour of the knot sequence (1, 2, 3, 1, 8, 7, 6, 9, 5, 4, 9, 7, 4, 3, 7, 1) is given in alphabetical order.

An Euler circle (also a closed Euler train , Euler tour or Euler line ) is a cycle in graph theory that contains all edges of a graph exactly once.

An open Euler path (also Euler path or Euler path ) is given if the start and end nodes do not have to be the same , i.e. instead of a cycle , only an edge sequence is required, which contains each edge of the graph exactly once.

A connected graph that has an Euler circle is called an Euler graph . If a graph only contains an Euler path and no Euler circle, it is called a semi-Euler graph . The task of determining whether or not a graph is Eulerian is called the Euler circle problem . It goes back to the Königsberg bridge problem solved by Leonhard Euler in 1736 . The problem also exists for directed graphs and graphs with multiple edges .

Contrary to its name, the Euler's circle is not a circle , at least if the common definition is followed, according to which no knot may be repeated in a circle .

characterization

According to Euler-Hierholzer's theorem, Euler's graphs are easy to characterize.

Let G be a graph in which at most one connected component contains edges. Then the following statements are equivalent

1. G is Eulerian,
2. every node in G has even degree .
3. the set of edges of G is the union of all edges of pairwise disjoint circles .

Analogously , the following statements are equivalent for a directed graph G in which at most one strongly connected component contains edges

1. G is Eulerian,
2. for every node in G the degree of entry and degree of exit are the same.
3. the set of edges of G is the union of all edges of pairwise disjoint directed circles .

Generalization: Eulerweg

An undirected connected graph contains if and only a Eulerweg when two or none of its nodes of odd degree is. If no node has an odd degree, the Euler path is an Euler circle.

Decision problem

The question of whether a given graph exists an Euler circle, can be algorithmically solved relatively easily, since a graph is Eulerian if it coherently and each node has even degree. This can easily be determined in linear time using depth-first search .

Finding an Euler Circle

There are several methods for finding an Euler's circle. The algorithm of Fleury dates back to 1883 and takes a very simple approach, which is why it has a running time of the order has. Hierholzer's algorithm , which calculates an Euler circle in linear time, is more efficient . It is based on the fact that an Eulerian graph can be decomposed into pairs of edge-disjoint circles. ${\displaystyle {\mathcal {O}}(|E|^{2})}$

Hierholzer's algorithm

→ Main article : Hierholzer's algorithm

1. Choose any node of the graph and start from there construct a circle in that does not pass through any edge twice. ${\displaystyle v_{0}}$ ${\displaystyle v_{0}}$ ${\displaystyle K}$ ${\displaystyle G}$ ${\displaystyle G}$
2. If there is an Euler circle, break off. Otherwise: ${\displaystyle K}$
3. Now neglect all edges of the circle . ${\displaystyle K}$
4. At the first node of , the degree of which is greater than 0, another circle is now formed, which does not pass through an edge in and does not contain an edge in twice. ${\displaystyle K}$ ${\displaystyle K'}$ ${\displaystyle K}$ ${\displaystyle G}$
5. Add to the second circle by replacing the starting node of with all the nodes of in the correct order. ${\displaystyle K}$ ${\displaystyle K'}$ ${\displaystyle K'}$ ${\displaystyle K'}$
6. Now name the circle you have obtained and continue with step 2. ${\displaystyle K}$

The running time of the algorithm is linear in the number of edges , so it is of the order of magnitude . ${\displaystyle {\mathcal {O}}(|E|)}$

example

A Euler graph with nine nodes is given (see first figure). A cycle from starting node 1 would be, for example, the sequence of nodes shown in blue in the second figure . After removing these edges , nodes 1, 3 and 7 of the cycle formed so far still have a node degree greater than zero, which can be used as starting nodes for the next cycle. The circle can be formed from starting node 3 (see third figure). If you now select node 7 as the starting node, you can form the cycle from the remaining edges . If you now insert in instead of node 7, you get the cycle . If you insert this in place of node 3, you get the possible Euler tour as shown in the last figure. ${\displaystyle C_{blau}=(1,2,3,7,1)}$ ${\displaystyle C_{rot}=(3,1,8,7,4,3)}$ ${\displaystyle C_{gruen}=(7,6,9,5,4,9,7)}$ ${\displaystyle C_{gruen}}$ ${\displaystyle C_{rot}}$ ${\displaystyle (3,1,8,7,6,9,5,4,9,7,4,3)}$ ${\displaystyle C_{blau}}$ ${\displaystyle (1,2,3,1,8,7,6,9,5,4,9,7,4,3,7,1)}$

• 

  Euler graph with nine nodes

• 

  ${\displaystyle C_{blau}=(1,2,3,7,1)}$

• 

  After removing the blue edges , you can create the next cycle starting from node 1, 3 or 7, here from node 3: ${\displaystyle C_{rot}=(3,1,8,7,4,3)}$

• 

  After removing the red edges , you can create the next cycle starting from node 4 or 7, here from node 7: ${\displaystyle C_{gruen}=(7,6,9,5,4,9,7)}$

• 

  Euler's circle with the knot sequence ${\displaystyle (1,2,3,1,8,7,6,9,5,4,9,7,4,3,7,1)}$

Fleury's algorithm

Bridge edges play an important role in Fleury's algorithm. These are edges without which the graph would break down into two components.

The algorithm adds all edges of a graph to an initially empty sequence of edges, so that an Euler circle is created.

1. Choose any node as the current node.
2. Select any edge from the unmarked edges that are incident with the current node . In doing so, edges must first be selected that are not bridging edges in the unmarked graph.
3. Mark the selected edge and add it to the edge sequence.
4. Choose the other node of the selected edge as the new current node.
5. If there are still unmarked edges, go to step 2.

Whether an edge is a bridge edge can be checked using depth first search in runtime . Since one edge is removed per step, iterations are required. The number of edges checked per iteration corresponds to the degree of the current node. Overall, the total number of checked edges can be limited by. The total runtime is thus of the order of magnitude . ${\displaystyle {\mathcal {O}}(|E|)}$ ${\displaystyle \left|E\right|}$ ${\displaystyle {\mathcal {O}}(|E|)}$ ${\displaystyle {\mathcal {O}}(|E|^{2})}$

history

In his work in 1736 on the Königsberg bridge problem , Leonhard Euler asked whether the graph given by the bridges in the city is an Euler graph, i.e. whether an Euler path exists, and answered no, since the graph had nodes with odd degrees. Euler proved that an Euler graph can only have nodes of even degree . He suspected and stated without proof that this was a sufficient condition: A connected graph in which every vertex has even degrees is an Euler graph. A proof of the theorem was first published by Carl Hierholzer in 1873. Hierholzer's algorithm for finding an Euler path is based on the proof .

Guess from Hajos

According to György Hajós' generally unsolved cycle conjecture about circular decomposition of Euler graphs from 1968, Euler graphs with nodes can be decomposed into at most circles. The conjecture was proven for small graphs ( ) in 2017 and for path widths less than or equal to 6. ${\displaystyle n}$ ${\displaystyle {\frac {1}{2}}(n-1)}$ ${\displaystyle n\leq 12}$

Application examples

The Königsberg bridge problem

The Königsberg bridge problem can be expressed in the following graph:

Graph for the Königsberg bridge problem

The circles ( nodes ) are the respective city districts or viewpoints. The lines ( edges ) are the bridges. By trial and error it is found that it is not possible to find a tour of the city in which each bridge is used exactly once. So there is no Euler path and consequently no Euler circle. Why is that?

Euler discovered the following law: If there is an Euler path in a graph G , then a maximum of 2 nodes have odd degrees. In the Königsberg bridge graph there are four nodes with odd degrees. The numbers next to the nodes indicate their degrees in the illustration. That is why the city tour with only one use of each bridge is impossible.

An odd knot is either the beginning or the end of the path over the bridges: zero odd knots would mean that the beginning and end of the path in Königsberg are identical. A path with a beginning and an end would have a maximum of two odd nodes. Ergo it was not possible in Königsberg to cross all bridges in one way only once.

The house of St. Nicholas

The popular children's puzzle “This is Nicholas ' house ”, on the other hand, contains an Euler path, but not an Euler circle, as its graph contains two nodes of degree 3.

Such a Euler way is 1-2-4-3-1-4-5-3-2. Nodes 1 and 2 each have 3 neighbors, so their degree is odd . In order to be able to draw the house in one go, you have to start at one of these two points. A square with diagonals does not contain an Euler path, since all of its nodes have degree 3. In the picture these are only points 1, 2, 3, 4 with the connecting edges.

See also

• Hamilton cycle problem

literature

• Wladimir Velminski: Leonhard Euler. The birth of graph theory . Kulturverlag Kadmos, Berlin 2008, ISBN 978-3-86599-056-3 .
• Reinhard Diestel: graph theory. 3. Edition. Springer, 2006, ISBN 3-540-21391-0 , pp. 23-24

Individual evidence

1. ↑ Hierholzer On the possibility of avoiding a line of lines without repetition and without interruption , Mathematische Annalen, Vol. 6, 1873, pp. 30–32, Online  ( page no longer available , search in web archives )  Info: The link was automatically defective marked. Please check the link according to the instructions and then remove this notice.  
2. ↑ Irene Heinrich, Marco Natale, Manuel Streicher, Hajós' cycle conjecture for small graphs , Arxiv 2017
3. ↑ Elke Fuchs, Laura Gellert, Irene Heinrich: Cycle decompositions of pathwidth-6 graphs , Arxiv 2017