Hierholzer's algorithm

Euler graph with nine nodes

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

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

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

The Euler tour thus determined in alphabetical order or with the knot sequence ${\displaystyle (1,2,3,1,8,7,6,9,5,4,9,7,4,3,7,1)}$

The algorithm of Hierholzer is an algorithm in the field of graph theory , one with a undirected graph Euler circles determined. It goes back to ideas from Carl Hierholzer .

Prerequisite: Let be a connected graph that only has nodes with even degrees . ${\displaystyle G=(V,E)}$

1. Choose any node of the graph and start from there construct a subcircle 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's circle, break off. Otherwise: ${\displaystyle K}$
3. Now neglect all edges of the sub-circle . ${\displaystyle K}$
4. At the first corner point of , the degree of which is greater than 0, another subcircle is created that does not pass through any edge in and does not contain any edge in twice. ${\displaystyle K}$ ${\displaystyle K'}$ ${\displaystyle K}$ ${\displaystyle G}$
5. Insert into the second circle by replacing the starting point of with all the points 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 complexity of the algorithm is linear in the number of edges.

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 cycles formed so far still have a node degree greater than zero, which can be used as starting nodes for the next cycle. You can form the circle from starting node 3 (red in the third figure). If you now choose 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)}$

literature

• Carl Hierholzer: About the possibility of driving around a line of lines without repetition and without interruption . Mathematische Annalen VI (1873), 30–32. [1]
• Sven Oliver Krumke, Hartmut Noltemeier: Graph theory concepts and algorithms. Teubner, Wiesbaden 2005, ISBN 3-519-00526-3 , pp. 45-48

Web links

• Visualization applet