Classical eulerian cycle algorithm: Difference between revisions
| 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.