Classical eulerian cycle algorithm: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 4: Line 4:


''' Type of algorithm:''' recursion with an arbitrarily chosen start node<math>s\in V</math> as an additional input. Before the proper recursive procedure is invoked, the output sequence <math>S</math> is initialized so as to contain the start node <math>s</math> and nothing else.
''' Type of algorithm:''' recursion with an arbitrarily chosen start node<math>s\in V</math> as an additional input. Before the proper recursive procedure is invoked, the output sequence <math>S</math> is initialized so as to contain the start node <math>s</math> and nothing else.
'''Break condition:''' No edges/arcs leave the start node <math>s</math>.


== Induction basis ==
== Induction basis ==

Revision as of 09:09, 12 October 2014

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: The output sequence [math]\displaystyle{ S }[/math] of nodes and arcs is initialized so as to contain the start node [math]\displaystyle{ s }[/math] and nothing else.

Induction step

If no edges/arcs leave the start node has

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.