Eulerian cycle: Difference between revisions
Jump to navigation
Jump to search
| Line 7: | Line 7: | ||
It is easy to see (and follows from the [[Classical eulerian cycle algorithm|classical algorithm]]) that a graph <math>G</math> is eulerian if, and only if: | It is easy to see (and follows from the [[Classical eulerian cycle algorithm|classical algorithm]]) that a graph <math>G</math> is eulerian if, and only if: | ||
# Undirected case: <math>G</math> is connected, and each node has even degree. | # Undirected case: <math>G</math> is connected, and each node has even degree. | ||
# Directed case: <math>G</math> is strongly connected, and for each node <math>v</math>, the | # Directed case: <math>G</math> is strongly connected, and for each node <math>v</math>, the indegree of <math>v</math> equals the outdegree of <math>v</math>. | ||
== Input == | == Input == | ||
Revision as of 11:00, 7 November 2014
Definition
- A eulerian cycle is an ordinary cycle in a directed or undirected graph that contains each edge/arc exactly once.
- A directed or undirected graph is called eulerian if it admits a eulerian cycle.
Remark: It is easy to see (and follows from the classical algorithm) that a graph [math]\displaystyle{ G }[/math] is eulerian if, and only if:
- Undirected case: [math]\displaystyle{ G }[/math] is connected, and each node has even degree.
- Directed case: [math]\displaystyle{ G }[/math] is strongly connected, and for each node [math]\displaystyle{ v }[/math], the indegree of [math]\displaystyle{ v }[/math] equals the outdegree of [math]\displaystyle{ v }[/math].
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.