Eulerian cycle: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 17: | Line 17: | ||
[[Classical eulerian cycle algorithm]] | [[Classical eulerian cycle algorithm]] | ||
== Example == | == Examples == | ||
== Normal Example == | |||
<gallery> | <gallery> | ||
File:Eulerpath_1.png|Step 1 | File:Eulerpath_1.png|Step 1 | ||
| Line 31: | Line 32: | ||
File:Eulerpath_11.png|Final Step | File:Eulerpath_11.png|Final Step | ||
</gallery> | </gallery> | ||
== Another may be well know Example == | |||
Contains 44 solutions | |||
[[File:Nikolaus.png]] | |||
Revision as of 15:21, 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 be well know Example
Contains 44 solutions
