Eulerian path

From Wikipedia for FEVERv2
Jump to navigation Jump to search

In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Eulerian path_sentence_0

Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. Eulerian path_sentence_1

They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. Eulerian path_sentence_2

The problem can be stated mathematically like this: Eulerian path_sentence_3

Eulerian path_description_list_0

  • Given the graph in the image, is it possible to construct a path (or a cycle; i.e., a path starting and ending on the same vertex) that visits each edge exactly once?Eulerian path_item_0_0

Euler proved that a necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an even degree, and stated without proof that connected graphs with all vertices of even degree have an Eulerian circuit. Eulerian path_sentence_4

The first complete proof of this latter claim was published posthumously in 1873 by Carl Hierholzer. Eulerian path_sentence_5

This is known as Euler's Theorem: Eulerian path_sentence_6

Eulerian path_description_list_1

  • A connected graph has an Euler cycle if and only if every vertex has even degree.Eulerian path_item_1_1

The term Eulerian graph has two common meanings in graph theory. Eulerian path_sentence_7

One meaning is a graph with an Eulerian circuit, and the other is a graph with every vertex of even degree. Eulerian path_sentence_8

These definitions coincide for connected graphs. Eulerian path_sentence_9

For the existence of Eulerian trails it is necessary that zero or two vertices have an odd degree; this means the Königsberg graph is not Eulerian. Eulerian path_sentence_10

If there are no vertices of odd degree, all Eulerian trails are circuits. Eulerian path_sentence_11

If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. Eulerian path_sentence_12

A graph that has an Eulerian trail but not an Eulerian circuit is called semi-Eulerian. Eulerian path_sentence_13

Definition Eulerian path_section_0

An Eulerian trail, or Euler walk in an undirected graph is a walk that uses each edge exactly once. Eulerian path_sentence_14

If such a walk exists, the graph is called traversable or semi-eulerian. Eulerian path_sentence_15

An Eulerian cycle, Eulerian circuit or Euler tour in an undirected graph is a cycle that uses each edge exactly once. Eulerian path_sentence_16

If such a cycle exists, the graph is called Eulerian or unicursal. Eulerian path_sentence_17

The term "Eulerian graph" is also sometimes used in a weaker sense to denote a graph where every vertex has even degree. Eulerian path_sentence_18

For finite connected graphs the two definitions are equivalent, while a possibly unconnected graph is Eulerian in the weaker sense if and only if each connected component has an Eulerian cycle. Eulerian path_sentence_19

For directed graphs, "path" has to be replaced with directed path and "cycle" with directed cycle. Eulerian path_sentence_20

The definition and properties of Eulerian trails, cycles and graphs are valid for multigraphs as well. Eulerian path_sentence_21

An Eulerian orientation of an undirected graph G is an assignment of a direction to each edge of G such that, at each vertex v, the indegree of v equals the outdegree of v. Such an orientation exists for any undirected graph in which every vertex has even degree, and may be found by constructing an Euler tour in each connected component of G and then orienting the edges according to the tour. Eulerian path_sentence_22

Every Eulerian orientation of a connected graph is a strong orientation, an orientation that makes the resulting directed graph strongly connected. Eulerian path_sentence_23

Properties Eulerian path_section_1

Eulerian path_unordered_list_2

  • An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component.Eulerian path_item_2_2
  • An undirected graph can be decomposed into edge-disjoint cycles if and only if all of its vertices have even degree. So, a graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint cycles and its nonzero-degree vertices belong to a single connected component.Eulerian path_item_2_3
  • An undirected graph has an Eulerian trail if and only if exactly zero or two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component.Eulerian path_item_2_4
  • A directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree, and all of its vertices with nonzero degree belong to a single strongly connected component. Equivalently, a directed graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint directed cycles and all of its vertices with nonzero degree belong to a single strongly connected component.Eulerian path_item_2_5
  • A directed graph has an Eulerian trail if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph.Eulerian path_item_2_6

Constructing Eulerian trails and circuits Eulerian path_section_2

Fleury's algorithm Eulerian path_section_3

Fleury's algorithm is an elegant but inefficient algorithm that dates to 1883. Eulerian path_sentence_24

Consider a graph known to have all edges in the same component and at most two vertices of odd degree. Eulerian path_sentence_25

The algorithm starts at a vertex of odd degree, or, if the graph has none, it starts with an arbitrarily chosen vertex. Eulerian path_sentence_26

At each step it chooses the next edge in the path to be one whose deletion would not disconnect the graph, unless there is no such edge, in which case it picks the remaining edge left at the current vertex. Eulerian path_sentence_27

It then moves to the other endpoint of that edge and deletes the edge. Eulerian path_sentence_28

At the end of the algorithm there are no edges left, and the sequence from which the edges were chosen forms an Eulerian cycle if the graph has no vertices of odd degree, or an Eulerian trail if there are exactly two vertices of odd degree. Eulerian path_sentence_29

Hierholzer's algorithm Eulerian path_section_4

Hierholzer's 1873 paper provides a different method for finding Euler cycles that is more efficient than Fleury's algorithm: Eulerian path_sentence_30

Eulerian path_unordered_list_3

  • Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.Eulerian path_item_3_7
  • As long as there exists a vertex u that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u, and join the tour formed in this way to the previous tour.Eulerian path_item_3_8
  • Since we assume the original graph is connected, repeating the previous step will exhaust all edges of the graph.Eulerian path_item_3_9

Counting Eulerian circuits Eulerian path_section_5

Complexity issues Eulerian path_section_6

The number of Eulerian circuits in digraphs can be calculated using the so-called BEST theorem, named after de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte. Eulerian path_sentence_31

The formula states that the number of Eulerian circuits in a digraph is the product of certain degree factorials and the number of rooted arborescences. Eulerian path_sentence_32

The latter can be computed as a determinant, by the matrix tree theorem, giving a polynomial time algorithm. Eulerian path_sentence_33

BEST theorem is first stated in this form in a "note added in proof" to the Aardenne-Ehrenfest and de Bruijn paper (1951). Eulerian path_sentence_34

The original proof was bijective and generalized the de Bruijn sequences. Eulerian path_sentence_35

It is a variation on an earlier result by Smith and Tutte (1941). Eulerian path_sentence_36

Counting the number of Eulerian circuits on undirected graphs is much more difficult. Eulerian path_sentence_37

This problem is known to be #P-complete. Eulerian path_sentence_38

In a positive direction, a Markov chain Monte Carlo approach, via the Kotzig transformations (introduced by Anton Kotzig in 1968) is believed to give a sharp approximation for the number of Eulerian circuits in a graph, though as yet there is no proof of this fact (even for graphs of bounded degree). Eulerian path_sentence_39

Special cases Eulerian path_section_7

The asymptotic formula for the number of Eulerian circuits in the complete graphs was determined by McKay and Robinson (1995): Eulerian path_sentence_40

A similar formula was later obtained by M.I. Isaev (2009) for complete bipartite graphs: Eulerian path_sentence_41

Applications Eulerian path_section_8

Eulerian trails are used in bioinformatics to reconstruct the DNA sequence from its fragments. Eulerian path_sentence_42

They are also used in CMOS circuit design to find an optimal logic gate ordering. Eulerian path_sentence_43

There are some algorithms for processing trees that rely on an Euler tour of the tree (where each edge is treated as a pair of arcs). Eulerian path_sentence_44

The de Bruijn sequences can be constructed as Eulerian trails of de Bruijn graphs. Eulerian path_sentence_45

In infinite graphs Eulerian path_section_9

In an infinite graph, the corresponding concept to an Eulerian trail or Eulerian cycle is an Eulerian line, a doubly-infinite trail that covers all of the edges of the graph. Eulerian path_sentence_46

It is not sufficient for the existence of such a trail that the graph be connected and that all vertex degrees be even; for instance, the infinite Cayley graph shown, with all vertex degrees equal to four, has no Eulerian line. Eulerian path_sentence_47

The infinite graphs that contain Eulerian lines were characterized by . Eulerian path_sentence_48

For an infinite graph or multigraph G to have an Eulerian line, it is necessary and sufficient that all of the following conditions be met: Eulerian path_sentence_49

Eulerian path_unordered_list_4

  • G is connected.Eulerian path_item_4_10
  • G has countable sets of vertices and edges.Eulerian path_item_4_11
  • G has no vertices of (finite) odd degree.Eulerian path_item_4_12
  • Removing any finite subgraph S from G leaves at most two infinite connected components in the remaining graph, and if S has even degree at each of its vertices then removing S leaves exactly one infinite connected component.Eulerian path_item_4_13

See also Eulerian path_section_10

Eulerian path_unordered_list_5

  • Eulerian matroid, an abstract generalization of Eulerian graphsEulerian path_item_5_14
  • Five room puzzleEulerian path_item_5_15
  • Handshaking lemma, proven by Euler in his original paper, showing that any undirected connected graph has an even number of odd-degree verticesEulerian path_item_5_16
  • Hamiltonian path – a path that visits each vertex exactly once.Eulerian path_item_5_17
  • Route inspection problem, search for the shortest path that visits all edges, possibly repeating edges if an Eulerian path does not exist.Eulerian path_item_5_18
  • Veblen's theorem, that graphs with even vertex degree can be partitioned into edge-disjoint cycles regardless of their connectivityEulerian path_item_5_19


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Eulerian path.