Definition
An Eulerian trail, or Euler walk in an undirected graph is a path that uses each edge exactly once. If such a path exists, the graph is called traversable or semi-eulerian.
An Eulerian cycle, 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 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.
For directed graphs, "path" has to be replaced with directed path and "cycle" with directed cycle.
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 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. Every Eulerian orientation of a connected graph is a strong orientation, an orientation that makes the resulting directed graph strongly connected.
Read more about this topic: Eulerian Path
Famous quotes containing the word definition:
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)
“Was man made stupid to see his own stupidity?
Is God by definition indifferent, beyond us all?
Is the eternal truth man’s fighting soul
Wherein the Beast ravens in its own avidity?”
—Richard Eberhart (b. 1904)
“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)