| Euler Cycle |
Article Index for Euler |
Website Links For Path |
Information AboutEuler Cycle |
| CATEGORIES ABOUT EULERIAN PATH | |
| graph theory | |
|
In the Mathematical field of Graph Theory , an Eulerian path is a Path in a graph which visits each Edge exactly once. They were first discussed by Leonhard Euler while solving the famous Seven Bridges Of Königsberg problem in 1736 . Mathematically the problem can be stated like this: :Given the graph on the right, is it possible to construct a path (or a Cycle , i.e. a path starting and ending on the same Vertex ) which visits each edge exactly once? Graphs which allow the construction of so called Eulerian cycles are called '''Eulerian graphs'''. Euler observed that a necessary condition for the existence of Eulerian cycles is that all vertices in the graph have an even Degree , and that for an Eulerian path either all, or all but two, vertices have an even degree; this means the Königsberg graph is ''not'' Eulerian. Carl Hierholzer published the first complete characterization of Eulerian graphs in 1873 , by proving that in fact the Eulerian graphs are exactly the graphs which are connected and where every vertex has an even degree. DEFINITION An Eulerian path, '''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'''. 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'''. For Directed Graph s path has to be replaced with Directed Path and cycle with Directed Cycle . The definition and properties of Eulerian paths, cycles and graphs are valid for Multigraph s as well. NOTES 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'''. That is why it is best to use the terms Eulerian trail and Eulerian circuit to avoid any potential confusion. PROPERTIES
CONSTRUCTING EULERIAN PATHS AND CYCLES Consider a graph known to have all edges in the same component and at most two vertices of odd degree. We can construct an Eulerian path or cycle out of this graph by using Fleury's algorithm, which dates to 1883 . We start with a vertex of odd degree—if the graph has none, then start with any vertex. At each step we move across an edge whose deletion does not result in more than one connected component, unless we have no choice, then we delete that edge. At the end of the algorithm there are no edges left, and the sequence of edges we moved across forms an Eulerian cycle if the graph has no vertices of odd degree or an Eulerian path if there are two vertices of odd degree. COUNTING EULERIAN CIRCUITS IN DIGRAPHS The number of Eulerian circuits in digraphs can be calculated using the so called BEST-theorem, named after De '''B'''ruijn , Van Aardenne-'''E'''hrenfest , '''S'''mith and '''T'''utte . Given a Eulerian digraph ''G'' := (''V'', ''E''), the number of non-equivalent Eulerian circuits in the graph is : or equivalently : with ''C'' any Cofactor of the Laplacian Matrix of ''G''. SEE ALSO EXTERNAL LINKS
REFERENCES
|
|
|