FindEulerianCycle

FindEulerianCycle[g]
finds an Eulerian cycle in the graph g.

FindEulerianCycle[g,k]
finds at most k Eulerian cycles.

DetailsDetails

Background
Background

  • FindEulerianCycle attempts to find one or more distinct Eulerian cycles, also called Eulerian circuits, Eulerian tours, or Euler tours in a graph. The cycles are returned as a list of edge lists or as if none exist. An Euler cycle (more properly called a circuit when the cycle is identified using a explicit path with particular endpoints) is a consecutive sequence of distinct edges such that the first and last edge coincide at their endpoints and in which each edge appears exactly once. Eulerian cycles may be used to reconstruct genome sequences, construct de Bruijin sequences, and to find optimal conference scheduling.
  • FindEulerianCycle[g,k] attempts to find k Eulerian cycles, where the count specification k may be omitted (in which case it is taken as 1), may be a positive integer, or may be All. Eulerian cycles need not be simple cycles, i.e. there can be a repeated vertex in a cycle (unlike Hamiltonian cycles, which are always simple).
  • A graph possessing an Eulerian cycle is known as an Eulerian graph. However, some care is needed in interpreting the term, since some authors define an Euler (as opposed to "Eulerian") graph as a different object, namely a graph for which all vertices are of even degree. The latter definition is motivated by Euler's correct (but unproved by him) observation that a connected simple graph possesses an Eulerian circuit if and only if it has no vertices of odd degree. Eulerian cycles are therefore mathematically easier to study than Hamiltonian cycles. While the number of connected Euler graphs on nodes is equal to the number of connected Eulerian graphs on nodes, the counts are different for disconnected graphs since there exist disconnected graphs having multiple disjoint cycles with each node even but for which no single cycle passes through all edges.
  • EulerianGraphQ can be used to determine if a graph is Eulerian. Functions for finding other sorts of cycles include FindCycle and FindHamiltonianCycle.
Introduced in 2010
(8.0)
| Updated in 2014
(10.0)