Eulerian cycle: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 1: | Line 1: | ||
[[File:Nikolaus.png|200px|thumb|right|Another may well know example with 44 solutions]] | |||
== Definition == | == Definition == | ||
A '''Eulerian cycle''' is a cycle in a directed or undirected graph that contains each edge/arc exactly once. | 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. | Redundant information for clarification: In the directed case, each arc must have forward orientatin on the cycle. | ||
| Line 32: | Line 32: | ||
File:Eulerpath_11.png|Final Step | File:Eulerpath_11.png|Final Step | ||
</gallery> | </gallery> | ||
Revision as of 15:26, 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
