HOME

TheInfoList



OR:

In
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, an Eulerian trail (or Eulerian path) is a
trail A trail, also known as a path or track, is an unpaved lane or small road usually passing through a natural area. In the United Kingdom and the Republic of Ireland, a path or footpath is the preferred term for a pedestrian or hiking trail. ...
in a finite graph that visits every
edge Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed ...
exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same
vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...
. They were first discussed by
Leonhard Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries ...
while solving the famous
Seven Bridges of Königsberg The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1736 laid the foundations of graph theory and prefigured the idea of topology. The city of Königsberg in Prussia (n ...
problem in 1736. The problem can be stated mathematically like this: :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? 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. The first complete proof of this latter claim was published posthumously in 1873 by Carl Hierholzer. This is known as Euler's Theorem: :A connected graph has an Euler cycle
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
every vertex has even degree. The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with an Eulerian circuit, and the other is a graph with every vertex of even degree. These definitions coincide for connected graphs. 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. If there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. A graph that has an Eulerian trail but not an Eulerian circuit is called semi-Eulerian.


Definition

An Eulerian trail,Some people reserve the terms ''path'' and ''cycle'' to mean ''non-self-intersecting'' path and cycle. A (potentially) self-intersecting path is known as a trail or an open walk; and a (potentially) self-intersecting cycle, a circuit or a closed walk. This ambiguity can be avoided by using the terms Eulerian trail and Eulerian circuit when self-intersection is allowed. or Euler walk, in an
undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
is a walk that uses each edge exactly once. If such a walk exists, the graph is called traversable or semi-eulerian. An Eulerian cycle, also called an Eulerian circuit or Euler tour, in an undirected graph is a cycle that uses each edge exactly once. If such a cycle exists, the graph is called Eulerian or unicursal. The term "Eulerian graph" is also sometimes used in a weaker sense to denote a graph where every vertex has even degree. For finite
connected graph In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...
s 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. For
directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...
s, "path" has to be replaced with '' directed path'' and "cycle" with ''
directed cycle Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''D ...
''. The definition and properties of Eulerian trails, cycles and graphs are valid for multigraphs as well. 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 In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered p ...
of ''v'' equals the
outdegree In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...
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. Every Eulerian orientation of a connected graph is a strong orientation, an orientation that makes the resulting directed graph strongly connected.


Properties

*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. *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. *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 *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 In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that ...
. Equivalently, a directed graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint
directed cycle Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''D ...
s and all of its vertices with nonzero degree belong to a single strongly connected component. *A directed graph has an Eulerian trail if and only if at most one vertex has at most one vertex has 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.


Constructing Eulerian trails and circuits


Fleury's algorithm

Fleury's algorithm is an elegant but inefficient algorithm that dates to 1883. Consider a graph known to have all edges in the same component and at most two vertices of odd degree. The algorithm starts at a vertex of odd degree, or, if the graph has none, it starts with an arbitrarily chosen vertex. 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. It then moves to the other endpoint of that edge and deletes the edge. 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. While the ''graph traversal'' in Fleury's algorithm is linear in the number of edges, i.e. O(, E, ), we also need to factor in the complexity of detecting
bridge A bridge is a structure built to span a physical obstacle (such as a body of water, valley, road, or rail) without blocking the way underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually someth ...
s. If we are to re-run Tarjan's linear time bridge-finding algorithm after the removal of every edge, Fleury's algorithm will have a time complexity of O(, E, ^2). A dynamic bridge-finding algorithm of allows this to be improved to O(, E, \cdot \log^3 , E, \cdot \log \log , E, ), but this is still significantly slower than alternative algorithms.


Hierholzer's algorithm

Hierholzer's 1873 paper provides a different method for finding Euler cycles that is more efficient than Fleury's algorithm: *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. *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. *Since we assume the original graph is
connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...
, repeating the previous step will exhaust all edges of the graph. By using a data structure such as a
doubly linked list In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the s ...
to maintain the set of unused edges incident to each vertex, to maintain the list of vertices on the current tour that have unused edges, and to maintain the tour itself, the individual operations of the algorithm (finding unused edges exiting each vertex, finding a new starting vertex for a tour, and connecting two tours that share a vertex) may be performed in constant time each, so the overall algorithm takes
linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
, O(, E, ). This algorithm may also be implemented with a
deque In computer science, a double-ended queue (abbreviated to deque, pronounced ''deck'', like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). I ...
. Because it is only possible to get stuck when the deque represents a closed tour, one should rotate the deque by removing edges from the tail and adding them to the head until unstuck, and then continue until all edges are accounted for. This also takes linear time, as the number of rotations performed is never larger than , E, (intuitively, any "bad" edges are moved to the head, while fresh edges are added to the tail)


Counting Eulerian circuits


Complexity issues

The number of Eulerian circuits in '' digraphs'' can be calculated using the so-called
BEST theorem In graph theory, a part of discrete mathematics, the BEST theorem gives a product formula for the number of Eulerian circuits in directed (oriented) graphs. The name is an acronym of the names of people who discovered it: de Bruijn, van Aarden ...
, named after de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte. 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. The latter can be computed as a
determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if a ...
, by the
matrix tree theorem In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial ti ...
, giving a polynomial time algorithm. BEST theorem is first stated in this form in a "note added in proof" to the Aardenne-Ehrenfest and de Bruijn paper (1951). The original proof was
bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
and generalized the
de Bruijn sequence In combinatorial mathematics, a de Bruijn sequence of order ''n'' on a size-''k'' alphabet ''A'' is a cyclic sequence in which every possible length-''n'' string on ''A'' occurs exactly once as a substring (i.e., as a ''contiguous'' subseq ...
s. It is a variation on an earlier result by Smith and Tutte (1941). Counting the number of Eulerian circuits on ''undirected'' graphs is much more difficult. This problem is known to be #P-complete. In a positive direction, a
Markov chain Monte Carlo In statistics, Markov chain Monte Carlo (MCMC) methods comprise a class of algorithms for sampling from a probability distribution. By constructing a Markov chain that has the desired distribution as its equilibrium distribution, one can obtain ...
approach, via the ''Kotzig transformations'' (introduced by
Anton Kotzig Anton Kotzig (22 October 1919 – 20 April 1991) was a Slovak–Canadian mathematician, expert in statistics, combinatorics and graph theory. The Ringel–Kotzig conjecture on graceful labeling of trees is named after him and Gerhard Ringel. ...
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).


Special cases

The
asymptotic formula In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior. As an illustration, suppose that we are interested in the properties of a function as becomes very large. If , then as bec ...
for the number of Eulerian circuits in the
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
s was determined by
McKay McKay, MacKay or Mackay is a Scottish / Irish surname. The last phoneme in the name is traditionally pronounced to rhyme with 'eye', but in some parts of the world this has come to rhyme with 'hey'. In Scotland, it corresponds to Clan Mackay. No ...
and Robinson (1995): : \operatorname(K_n) = 2^\pi^ e^ n^ \bigl(1+O(n^)\bigr). A similar formula was later obtained by M.I. Isaev (2009) for
complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory i ...
s: : \operatorname(K_) = (\frac-1)!^ 2^\pi^ n^ \bigl(1+O(n^)\bigr).


Applications

Eulerian trails are used in
bioinformatics Bioinformatics () is an interdisciplinary field that develops methods and software tools for understanding biological data, in particular when the data sets are large and complex. As an interdisciplinary field of science, bioinformatics combi ...
to reconstruct the
DNA sequence DNA sequencing is the process of determining the nucleic acid sequence – the order of nucleotides in DNA. It includes any method or technology that is used to determine the order of the four bases: adenine, guanine, cytosine, and thymine. T ...
from its fragments. They are also used in
CMOS Complementary metal–oxide–semiconductor (CMOS, pronounced "sea-moss", ) is a type of metal–oxide–semiconductor field-effect transistor (MOSFET) fabrication process that uses complementary and symmetrical pairs of p-type and n-type MOSF ...
circuit design to find an optimal
logic gate A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic ga ...
ordering. There are some algorithms for processing
tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
s that rely on an Euler tour of the tree (where each edge is treated as a pair of arcs). The
de Bruijn sequence In combinatorial mathematics, a de Bruijn sequence of order ''n'' on a size-''k'' alphabet ''A'' is a cyclic sequence in which every possible length-''n'' string on ''A'' occurs exactly once as a substring (i.e., as a ''contiguous'' subseq ...
s can be constructed as Eulerian trails of
de Bruijn graph In graph theory, an -dimensional De Bruijn graph of symbols is a directed graph representing overlaps between sequences of symbols. It has vertices, consisting of all possible sequences of the given symbols; the same symbol may appear multipl ...
s.


In infinite graphs

In an
infinite graph This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...
, 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. 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 In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...
shown, with all vertex degrees equal to four, has no Eulerian line. The infinite graphs that contain Eulerian lines were characterized by . For an infinite graph or multigraph to have an Eulerian line, it is necessary and sufficient that all of the following conditions be met:. * is connected. * has
countable set In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numb ...
s of vertices and edges. * has no vertices of (finite) odd degree. *Removing any finite subgraph from leaves at most two infinite connected components in the remaining graph, and if has even degree at each of its vertices then removing leaves exactly one infinite connected component.


Undirected Eulerian graphs

Euler stated a necessary condition for a graph to be Eulerian as all vertices must have even degree. Hierholzer proved this is a sufficient condition in a paper published in 1873. This leads to the following necessary and sufficient statement for what a graph must have to be Eulerian: An undirected connected graph is Eulerian if and only if every vertex of G has even degree. The following result was proved by Veblen in 1912: An undirected connected graph is Eulerian if and only if it is the disjoint union of some cycles.Hierholzer developed a linear time algorithm for constructing an Eulerian tour in an undirected graph.


Directed Eulerian graphs

It is possible to have a directed graph that has all even degrees but is not Eulerian. This means that even degrees is not a sufficient condition for a digraph to be Eulerian. König proved that a digraph must also have the same number of arcs entering and leaving each vertex to be Eulerian. In other words, the directed graph must be symmetric. A directed and strongly connected graph is Eulerian if and only if every vertex of G is symmetric. Hierholzer's linear time algorithm for constructing an Eulerian tour is also applicable to directed graphs.


Mixed Eulerian graphs

If a mixed graph has even degrees only, it is not guaranteed to be an Eulerian graph. This means that evenness is a necessary but not sufficient condition for a mixed graph to be Eulerian. If a mixed graph is even and symmetric, it is guaranteed to be symmetric. This means that evenness and being symmetric is a necessary condition for a mixed graph to be Eulerian. This is not a necessary and sufficient condition however, because it is possible to construct a graph that is even and not symmetric that is still Eulerian. Ford and Fulkerson proved in 1962 in their book Flows in Networks a necessary and sufficient condition for a graph to be Eulerian, viz., that every vertex must be even and satisfy the balance condition. For every subset of vertices S, the difference between the number of arcs leaving S and entering S must be less than or equal to the number of edges incident with S. This is the balanced set condition. A mixed and strongly connected graph is Eulerian if and only if G is even and balanced. The process of checking if a mixed graph is Eulerian is harder than checking if an undirected or directed graph is Eulerian because the balanced set condition concerns every possible subset of vertices.


See also

* Eulerian matroid, an abstract generalization of Eulerian graphs * Five room puzzle * Handshaking lemma, proven by Euler in his original paper, showing that any undirected connected graph has an even number of odd-degree vertices *
Hamiltonian path In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
– a path that visits each ''vertex'' exactly once. * Route inspection problem, search for the shortest path that visits all edges, possibly repeating edges if an Eulerian path does not exist. *
Veblen's theorem In mathematics, Veblen's theorem, introduced by , states that the set of edges of a finite graph can be written as a union of disjoint simple cycles if and only if every vertex has even degree. Thus, it is closely related to the theorem of that ...
, which states that graphs with even vertex degree can be partitioned into edge-disjoint cycles regardless of their connectivity


Notes


References

*. Translated as . * Euler, L.,
Solutio problematis ad geometriam situs pertinentis
, ''Comment. Academiae Sci. I. Petropolitanae'' 8 (1736), 128–140. *. * Lucas, E., ''Récréations Mathématiques IV'', Paris, 1921. * Fleury, "Deux problemes de geometrie de situation", ''Journal de mathematiques elementaires'' (1883), 257–261. * T. van Aardenne-Ehrenfest and N. G. de Bruijn (1951) "Circuits and trees in oriented linear graphs",
Simon Stevin Simon Stevin (; 1548–1620), sometimes called Stevinus, was a Flemish mathematician, scientist and music theorist. He made various contributions in many areas of science and engineering, both theoretical and practical. He also translated vario ...
28: 203–217. * * W. T. Tutte and C. A. B. Smith (1941) "On Unicursal Paths in a Network of Degree 4",
American Mathematical Monthly ''The American Mathematical Monthly'' is a mathematical journal founded by Benjamin Finkel in 1894. It is published ten times each year by Taylor & Francis for the Mathematical Association of America. The ''American Mathematical Monthly'' is an ...
48: 233–237.


External links

{{Commons category, Eulerian paths
Discussion of early mentions of Fleury's algorithm

''Euler tour''
at
Encyclopedia of Mathematics The ''Encyclopedia of Mathematics'' (also ''EOM'' and formerly ''Encyclopaedia of Mathematics'') is a large reference work in mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structu ...
. Graph theory objects Leonhard Euler