Hierholzer's algorithm
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 .
- Choose any node of the graph and start from there construct a subcircle in that does not pass through any edge twice.
- If there is an Euler's circle, break off. Otherwise:
- Now neglect all edges of the sub-circle .
- 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.
- Insert into the second circle by replacing the starting point of with all the points of in the correct order.
- Now name the circle you have obtained and continue with step 2.
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.
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