Classical eulerian cycle algorithm: Difference between revisions
(3 intermediate revisions by 2 users not shown) | |||
Line 30: | Line 30: | ||
== Correctness == | == 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>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 delivered if the graph is indeed non-eulerian. Moreover, the graph handed over to a recursive call is Eulerian, if the original graph was Eulerian. | 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>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 delivered in step 5 if the graph is indeed non-eulerian. Moreover, 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>e/a</math> is '''not''' in the output. Since the graph is (strongly) connected, there is a path <math>q</math> from the start node to the | Suppose for a contradiction that some edge/arc <math>e/a</math> is '''not''' in the output. Since the graph is (strongly) connected, there is a path <math>q</math> from the start node of the algorithm to the beginning node of <math>a</math> (an arbitrary endnode of <math>e</math> in the undirected case). Let <math>v</math> be the last node on <math>q</math> processed by any recursive call. Then the subsequent edge/arc on <math>q</math> has not been processed, which contradicts the procedure. | ||
== Complexity == | == Complexity == |
Latest revision as of 08:15, 2 November 2015
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.
Recursion anchor
No edges/arcs leave the start node [math]\displaystyle{ s }[/math] of that recursive call.
Recursive step
For notational convenience, both undirected edges and directed arcs are denoted by parentheses in the following (in the direction in which they are looked at).
- 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. 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 delivered in step 5 if the graph is indeed non-eulerian. Moreover, 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 of the algorithm to the beginning node of [math]\displaystyle{ a }[/math] (an arbitrary endnode of [math]\displaystyle{ e }[/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. So the total complexity of these steps is linear in the number of recursive calls, which is linear in the number of edges/arcs in turn. The total number of iterations of steps 4 and 6, respectively, taken over all recursive calls, is linear in the number of edges/arcs as well.
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.