Eulerian cycle: Difference between revisions
Jump to navigation
Jump to search
(→Input) |
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. | ||
== 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> | |||
== Known algorithms == | == Known algorithms == | ||
[[Classical eulerian cycle algorithm]] | [[Classical eulerian cycle algorithm]] | ||
Revision as of 15:09, 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.
Example
Step 1
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8
Step 9
Step 10
Final Step
