Eulerian cycle: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 12: | Line 12: | ||
A Eulerian cycle as an alternating sequence of nodes and edges/arcs or, alternatively, the (correct) message that no such cycle exists. | 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]] | |||
== Example == | == Example == | ||
| Line 27: | Line 31: | ||
File:Eulerpath_11.png|Final Step | File:Eulerpath_11.png|Final Step | ||
</gallery> | </gallery> | ||
Revision as of 15:11, 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
Example
Step 1
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8
Step 9
Step 10
Final Step
