Eulerian path

(redirected from Euler tour)

Eulerian path

[ȯi′ler·ē·ən ′path]
(mathematics)
A path that traverses each of the lines in a graph exactly once.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.
Mentioned in ?
References in periodicals archive ?
A path that starts and ends at the same node forms a tour, furthermore, if the tour traverses every edge of G exactly once then it is an Euler tour. A rural postman tour is a tour that traverses a given set of edges at least once.
There is an Euler tour in a directed graph if and only if the directed graph is strongly connected and symmetric.
Note that an Euler tour starting from and ending at the initial state may not be unique; i.e., there may be nonunique sets of maximum-length IDOSs.
It is well known that every connected multigraph G with the degree of each of its vertices being even has an Euler tour; we say that such a multigraph is Eulerian.
Heinrich et al.[9] proved that the graphs in G are the only connected (2,4)-graphs that do not admit a triangle-free Euler tour.
Theorem 10 [9] A connected (2,4)-graph G admits a triangle-free Euler tour if and only if G [??] G.
Clearly, if G [not member of] G is a connected, (2,4)-graph with [absolute value of E(G)] divisible by 3 then we can obtain a [P.sub.4]-decomposition of G by properly segmenting a triangle-free Euler tour in G.
Proof: If G [member of] F, it is easy to check that G does not admit a ([C.sub.2], [C.sub.3])-free Euler tour. Let G [not member of] F be a connected (2,4)-multigraph with [mu](G) [less than or equal to] 2 and let p(G) be the number of parallel edge pairs in G.
After odd vertices are matched, Euler tour is found in the resulting graph.
Given a rooted tree T' = (V, E), the Euler Tour ET(T') of T' is a sequence of nodes.
--Construct the Euler Tour ET(T) or compute the depth of each node.