Eulerian cycle: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 15: Line 15:
== Output ==
== Output ==


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 the graph is not eulerian.


== Known algorithms ==
== Known algorithms ==


[[Classical eulerian cycle algorithm]]
[[Classical eulerian cycle algorithm]]

Revision as of 11:01, 7 November 2014

Definition

  1. A eulerian cycle is an ordinary cycle in a directed or undirected graph that contains each edge/arc exactly once.
  2. 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:

  1. Undirected case: [math]\displaystyle{ G }[/math] is connected, and each node has even degree.
  2. 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 the graph is not eulerian.

Known algorithms

Classical eulerian cycle algorithm