Eulerian cycle: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 32: Line 32:
File:Eulerpath_11.png|Final Step
File:Eulerpath_11.png|Final Step
</gallery>
</gallery>
== Another may be well know Example ==
== Another may well know Example ==
Contains 44 solutions
Contains 44 solutions
[[File:Nikolaus.png]]
[[File:Nikolaus.png]]

Revision as of 15:22, 12 October 2014

Definition

A Eulerian cycle is a cycle in a directed or undirected graph that contains each edge/arc exactly once.

Redundant information for clarification: In the directed case, each arc must have forward orientatin on the cycle.

Input

A strongly connected directed or connected undirected graph.

Output

A Eulerian cycle as an alternating sequence of nodes and edges/arcs or, alternatively, the (correct) message that no such cycle exists.

Known algorithms

Classical eulerian cycle algorithm

Examples

Normal Example

Another may well know Example

Contains 44 solutions Nikolaus.png