Eulerian cycle: Difference between revisions
Jump to navigation
Jump to search
| Line 18: | Line 18: | ||
== Examples == | == Examples == | ||
== Normal | == Normal example == | ||
<gallery> | <gallery> | ||
File:Eulerpath_1.png|Step 1 | File:Eulerpath_1.png|Step 1 | ||
| Line 32: | Line 32: | ||
File:Eulerpath_11.png|Final Step | File:Eulerpath_11.png|Final Step | ||
</gallery> | </gallery> | ||
== Another may 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
Step 1
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8
Step 9
Step 10
Final Step
Another may well know Example
Contains 44 solutions
