Classical eulerian cycle algorithm

General information

Algorithmic problem: Eulerian cycle

Type of algorithm: recursion with an arbitrarily chosen start node[math]\displaystyle{ s\in V }[/math] as an additional input. Before the proper recursive procedure is invoked, the output sequence [math]\displaystyle{ S }[/math] is initialized so as to contain the start node [math]\displaystyle{ s }[/math] and nothing else.

Break condition: No edges/arcs leave the start node [math]\displaystyle{ s }[/math].

Induction basis

Abstract view: Nothing to do.

Induction step

In the following, both undirected edges and directed arcs are denoted by parentheses.

1. Let [math]\displaystyle{ p }[/math] be a (dynamically growing</math>) path, represented in [math]\displaystyle{ p }[/math] as an alternating sequence of nodes and edges/arcs.
2. Initialize so as to contain [math]\displaystyle{ s }[/math] and nothing else.
3. Set [math]\displaystyle{ x:=s }[/math].
4. While there are edges/arcs leaving [math]\displaystyle{ x }[/math]:
   1. Choose one such arc [math]\displaystyle{ (x,y) }[/math].
   2. Remove [math]\displaystyle{ (x,y) }[/math] from the graph.
   3. Append [math]\displaystyle{ (x,y) }[/math] and then [math]\displaystyle{ y }[/math] to [math]\displaystyle{ p }[/math].
   4. Set [math]\displaystyle{ x:=y }[/math].
5. If [math]\displaystyle{ x\neq s }[/math], terminate the algorithm with the statement that no Eulerian cycle exists.
6. Otherwise: For each node [math]\displaystyle{ v }[/math] on [math]\displaystyle{ p }[/math] that still has leaving edges/arcs,:
   1. Call the procedure recursively with [math]\displaystyle{ v }[/math] as the start node, giving path [math]\displaystyle{ p' }[/math].
   2. Replace [math]\displaystyle{ v }[/math] in [math]\displaystyle{ p }[/math] by [math]\displaystyle{ p' }[/math].

Complexity

Statement: oth for directed and undirected graphs, the asymtptotic complexity is [math]\displaystyle{ \mathcal{O}(n+m) }[/math], where [math]\displaystyle{ n }[/math] is the number of nodes and [math]\displaystyle{ m }[/math] the number of edges/ars.

Proof:

Remark

Of course, the edges/arcs need not be removed permanently. However, when an edge/arc is processed, it must be hidden from the algorithm up to its termination to achieve the linear bound on the complexity.