Editing Eulerian path (section)

== Constructing Eulerian trails and circuits ==
[[File:Eulerian_path_puzzles.svg|thumb|Using Eulerian trails to solve puzzles involving drawing a shape with a continuous stroke: {{olist
    |As the [[:de:Haus vom Nikolaus|Haus vom Nikolaus puzzle]] has two odd-degree vertices (orange), the trail must start at one and end at the other.
    |A variant with four odd-degree vertices has no solution.
    |If there are no odd-degree vertices, the trail can start anywhere and forms an Eulerian cycle.
    |Loose ends are considered vertices of degree 1.
    |The graph must also be connected.
}}]]

=== Fleury's algorithm ===
'''Fleury's algorithm''' is an elegant but inefficient algorithm that dates to 1883.<ref>{{citation|first=Pierre-Henry<!-- See https://hsm.stackexchange.com/questions/12633/who-was-fleury-and-what-was-his-first-name -- in the publication, the "M." in "M. Fleury" is just short for monsieur, and should not be listed as Fleury's first initial -->|last=Fleury|title=Deux problèmes de Géométrie de situation|language=fr|url=https://books.google.com/books?id=l-03AAAAMAAJ&pg=PA257|journal=Journal de mathématiques élémentaires|series=2nd ser.|volume=2|year=1883|pages=257–261}}.</ref> Consider a graph known to have all edges in the same component and at most two vertices of odd degree. The algorithm starts at a vertex of odd degree, or, if the graph has none, it starts with an arbitrarily chosen vertex. At each step it chooses the next edge in the path to be one whose deletion would not disconnect the graph, unless there is no such edge, in which case it picks the remaining edge left at the current vertex. It then moves to the other endpoint of that edge and deletes the edge. At the end of the algorithm there are no edges left, and the sequence from which the edges were chosen forms an Eulerian cycle if the graph has no vertices of odd degree, or an Eulerian trail if there are exactly two vertices of odd degree.

While the ''graph traversal'' in Fleury's algorithm is linear in the number of edges, i.e. <math>O(|E|)</math>, we also need to factor in the complexity of detecting [[Bridge (graph theory)|bridge]]s. If we are to re-run [[Robert Tarjan|Tarjan]]'s linear time [[Bridge (graph theory)#Tarjan's bridge-finding algorithm|bridge-finding algorithm]]<ref>{{citation
 | last = Tarjan | first = R. Endre | author-link = Robert Tarjan
 | doi = 10.1016/0020-0190(74)90003-9
 | year = 1974
 | issue = 6
 | journal = Information Processing Letters
 | mr = 0349483
 | pages = 160–161
 | title = A note on finding the bridges of a graph
 | volume = 2}}.</ref> after the removal of every edge,  Fleury's algorithm will have a time complexity of <math>O(|E|^2)</math>. A dynamic bridge-finding algorithm of {{harvtxt|Thorup|2000}} allows this to be improved to <math>O(|E| \cdot \log^3 |E| \cdot \log \log |E|)</math>, but this is still significantly slower than alternative algorithms.

=== Hierholzer's algorithm ===
[[Carl Hierholzer|Hierholzer]]'s 1873 paper provides a different method for finding Euler cycles that is more efficient than Fleury's algorithm:
*Choose any starting vertex ''v'', and follow a trail of edges from that vertex until returning to ''v''. It is not possible to get stuck at any vertex other than ''v'', because the even degree of all vertices ensures that, when the trail enters another vertex ''w'' there must be an unused edge leaving ''w''. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
*As long as there exists a vertex ''u'' that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from ''u'', following unused edges until returning to ''u'', and join the tour formed in this way to the previous tour.
*Since we assume the original graph is [[connected graph|connected]], repeating the previous step will exhaust all edges of the graph.
By using a data structure such as a [[doubly linked list]] to maintain the set of unused edges incident to each vertex, to maintain the list of vertices on the current tour that have unused edges, and to maintain the tour itself, the individual operations of the algorithm (finding unused edges exiting each vertex, finding a new starting vertex for a tour, and connecting two tours that share a vertex) may be performed in constant time each, so the overall algorithm takes [[linear time]], <math>O(|E|)</math>.<ref>{{citation|title=Eulerian Graphs and Related Topics: Part 1, Volume 2|volume=50|series=Annals of Discrete Mathematics|first=Herbert|last=Fleischner|publisher=Elsevier|year=1991|isbn=978-0-444-89110-5|contribution=X.1 Algorithms for Eulerian Trails|pages=[https://archive.org/details/euleriangraphsre0001flei/page/ X.1–13]|url=https://archive.org/details/euleriangraphsre0001flei/page/}}.</ref>

This algorithm may also be implemented with a [[Double-ended queue|deque]]. Because it is only possible to get stuck when the deque represents a closed tour, one should rotate the deque by removing edges from the tail and adding them to the head until unstuck, and then continue until all edges are accounted for. This also takes linear time, as the number of rotations performed is never larger than <math>|E|</math> (intuitively, any "bad" edges are moved to the head, while fresh edges are added to the tail)
{{Hamiltonian_platonic_graphs.svg}}