Classical eulerian cycle algorithm

Another may well know example with 44 solutions

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

For notational convenience, both undirected edges and directed arcs are denoted by parentheses in the following.

1. 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.
2. Initialize [math]\displaystyle{ p }[/math] 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].

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. Obviously, whenever step 4 is finished, it is [math]\displaystyle{ x=s }[/math] and the remaining graph is Eulerian, if the original graph was Eulerian. Consequently, the statement that no Eulerian cycle exists is only deiivered if true, and the graph handed over to a recursive call is Eulerian, if the original graph was Eulerian.

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:

1. Since the graph is (strongly) connected, the number of nodes is asymptotically dominated by the number of edges/arcs and, therefore, irrelevant here.
2. 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