Eulerian cycle: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 16: Line 16:


[[Classical eulerian cycle algorithm]]
[[Classical eulerian cycle algorithm]]
== Example ==
<gallery>
File:Eulerpath_1.png|Step 1
File:Eulerpath_2.png|Step 2
File:Eulerpath_3.png|Step 3
File:Eulerpath_4.png|Step 4
File:Eulerpath_5.png|Step 5
File:Eulerpath_6.png|Step 6
File:Eulerpath_7.png|Step 7
File:Eulerpath_8.png|Step 8
File:Eulerpath_9.png|Step 9
File:Eulerpath_10.png|Step 10
File:Eulerpath_11.png|Final Step
</gallery>

Revision as of 15:48, 17 October 2014

Another may well know example with 44 solutions

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