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.
- Let [math]\displaystyle{ p }[/math] be a (dynamically growing) path, represented in [math]\displaystyle{ p }[/math] as an alternating sequence of nodes and edges/arcs.
- Initialize [math]\displaystyle{ p }[/math] so as to contain [math]\displaystyle{ s }[/math] and nothing else.
- Set [math]\displaystyle{ x:=s }[/math].
- While there are edges/arcs leaving [math]\displaystyle{ x }[/math]:
- Choose one such arc [math]\displaystyle{ (x,y) }[/math].
- Remove [math]\displaystyle{ (x,y) }[/math] from the graph.
- Append [math]\displaystyle{ (x,y) }[/math] and then [math]\displaystyle{ y }[/math] to [math]\displaystyle{ p }[/math].
- Set [math]\displaystyle{ x:=y }[/math].
- If [math]\displaystyle{ x\neq s }[/math], terminate the algorithm with the statement that no Eulerian cycle exists.
- Otherwise: For each node [math]\displaystyle{ v }[/math] on [math]\displaystyle{ p }[/math] that still has leaving edges/arcs,:
- Call the procedure recursively with [math]\displaystyle{ v }[/math] as the start node, giving path [math]\displaystyle{ p' }[/math].
- Replace [math]\displaystyle{ v }[/math] in [math]\displaystyle{ p }[/math] by [math]\displaystyle{ p' }[/math].
Correctness
Since each edge/arc is removed immediately when it is processed, no edge/arc occurs twice in the output. Obviously, steps 4.3 and 6.2 ensure that the order in which the nodes and edges/arcs occur in the output yields a correct path. Step 5 ensures that the path grows to a cycle, unless this is impossible. In that case, no eulerian cycle exists because, obviously, the remaining graph is always Eulerian at the moment of a recursively call, if the original graph was Eulerian. In summary, it suffices to show that all arcs are in the output.
Suppose for a contradiction that some edge/arc [math]\displaystyle{ e/a }[/math] is not in the output. Since the graph is (strongly) connected, there is a path [math]\displaystyle{ q }[/math] from the start node to the tail of [math]\displaystyle{ e/a }[/math] (an arbitrary endnode of [math]\displaystyle{ e/a }[/math] in the undirected case). Let [math]\displaystyle{ v }[/math] be the last node on [math]\displaystyle{ q }[/math] processed by any recursive call. Then the subsequent edge/arc on [math]\displaystyle{ q }[/math] has not been processed, which contradicts the procedure.
Complexity
Statement: Both for directed and undirected graphs, the asymtptotic complexity is linear in the number of edges/ars.
Proof: We assume that all data structures are implemented in the obvious appropriate way. First note that steps 1, 2, 3, and 5 take constant time each. The total number of iterations of steps 4 and 6, respectively, taken over all recursive calls, is linear in the number of edges/arcs.
Remarks:
- Since the graph is (strongly) connected, the number of nodes is asymptotically dominated by the number of edges/arcs and, therefore, irrelevant here.
- 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. A boolean edge/arc label to indicate whether this edge/arc has already been processed, does not suffice.
Example
Step 1
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8
Step 9
Step 10
Final Step
