FindEulerianCycle

FindEulerianCycle[g]

finds an Eulerian cycle in the graph g.

FindEulerianCycle[g,k]

finds at most k Eulerian cycles.

FindEulerianCycle[{vw,},]

uses rules vw to specify the graph g.

Details

Background & Context

  • 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 Eulerian 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 Bruijn 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.

Examples

open allclose all

Basic Examples  (2)

Find an Eulerian cycle:

Show the cycle:

Find several Eulerian cycles:

Scope  (8)

FindEulerianCycle works with undirected graphs:

Directed graphs:

Multigraphs:

Find several Eulerian cycles:

Find all Eulerian cycles:

Use rules to specify the graph:

FindEulerianCycle returns an empty result for non-Eulerian graphs:

FindEulerianCycle works with large graphs:

Applications  (7)

The seven bridges of the city of Königsberg over the river Pregel cannot all be traversed in a single trip without doubling back, with the additional requirement that the trip ends in the same place it began:

Trace out the figure of an envelope without lifting the pen and without going over the same line twice:

The graph is not Eulerian:

Since there are two odd-degree vertices, an augmented Eulerian graph is constructed by joining the odd-degree vertices via a new vertex (to avoid multiple edges):

Find an Eulerian cycle in the augmented graph:

Rotate the edges of the cycle until the edges involving the vertex become the last ones:

Show the Eulerian path:

Find the most optimal scheduling of a conference room for the following meetings:

The graph of participants with edges connecting attendees of the same meeting:

There is no optimal schedule allowing two consecutive meetings to share a participant:

Add virtual meetings between participants with an odd number of meetings:

A possible scheduling:

Graph-based assembly of a circular genome "ATGGCGTGCA" with vertices as (k-1)-mers and edges as k-mers:

Reconstruct the genome:

Construct a k-ary de Bruijn sequence from an Eulerian cycle:

De Bruijn sequence:

Find the order of vertices visited along a directed cycle:

Pick the source vertex of each edge:

Find an Eulerian cycle of the Dutch windmill graph:

Label the edges visited along the Eulerian cycle:

Properties & Relations  (6)

Use GraphData for an extensive collection of Eulerian graphs:

Non-Eulerian graphs:

Test whether a graph has an Eulerian cycle using EulerianGraphQ:

A connected undirected graph with vertices of even degree has an Eulerian cycle:

An undirected graph has an Eulerian cycle if it can be decomposed into edge-disjoint cycles:

The line graph of an undirected Eulerian graph has an Eulerian cycle:

A directed graph with in-degree and out-degree equal for each vertex has an Eulerian cycle:

Neat Examples  (1)

Find an Eulerian cycle:

Dynamically highlight a cycle:

Introduced in 2010
 (8.0)
 |
Updated in 2012
 (9.0)
2014
 (10.0)
2015
 (10.3)