Eulerian cycle: Difference between revisions
Jump to navigation
Jump to search
(→Output) |
|||
| Line 1: | Line 1: | ||
== Definition == | == Definition == | ||
A '''eulerian cycle''' is an [[Basic graph definitions#Cycles|ordinary cycle]] in a directed or undirected graph that contains each edge/arc exactly once. | # A '''eulerian cycle''' is an [[Basic graph definitions#Cycles|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 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. | |||
# Directed case: <math>G</math>is strongly connected, and for each node <math>v</math>, the in degree of <math>v</math> equals the out degree of <math>v</math>. | |||
== Input == | == Input == | ||
Revision as of 10:59, 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 in degree of [math]\displaystyle{ v }[/math] equals the out degree 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.