|
|
| (3 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| =Notes=
| | #REDIRECT [[Graphs/Euler Circuit]] |
| | |
| An Euler tour of a graph G is a traversal of the graph (a walk) that visits each '''edge''' of the graph once.
| |
| | |
| This is not always possible to do - and, in fact, determining if an Euler tour of a graph exists is precisely the problem that led Euler to create the subject of graph theory in the first place. Euler was trying to tackle the Bridge of Königsberg problem, which was to determine if there is a walk through the different parts of Königsberg, connected by seven bridges, that requires the walker to cross each bridge exactly once.
| |
| | |
| ==Undirected Graphs==
| |
| | |
| For an undirected graph to be Eulerian, the number of vertices with odd degree '''must''' be 0 or 2.
| |
| | |
| Note that this is a special case of the [[First Theorem of Graph Theory]], which states that the number of vertices with odd degree '''must''' be even.
| |
| | |
| A graph G on which an Euler tour is possible is said to be an Eulerian graph. A connected graph is Eulerian if and only if it has either 2 or 0 vertices of odd degree.
| |
| | |
| ==Directed Graphs==
| |
| | |
| How to check if a directed graph has an Euler Tour?
| |
| | |
| A directed graph has an Euler Tour if following conditions are true:
| |
| | |
| 1. All vertices with nonzero degree belong to a single strongly connected component.
| |
| | |
| 2. The in-degree and out-degree of every vertex is same.
| |
| | |
| ==Euler Tour Pseudocode==
| |
| | |
| <pre>
| |
| C = empty cycle at vertex 0
| |
| while G has unmarked edges:
| |
| u = any vertex on C with unmarked edges
| |
| C2 = empty list of edges
| |
| v = u
| |
| do:
| |
| e = unmarked edge of v
| |
| mark e
| |
| append e to C2
| |
| v = other endpoint of e
| |
| while v is not u
| |
| Splice C2 into C at u
| |
| end while
| |
| | |
| </pre>
| |
| | |
| ==Fleury's Algorithm==
| |
| | |
| <pre>
| |
| v = v0
| |
| F = E
| |
| C = trivial path at v[0]
| |
| while G has unmarked edges
| |
| if v has unmarked edge that is not a bridge of V,F
| |
| then e = unmarked edge of v that is not a bridge of V,F
| |
| else e = any unmarked edge of v
| |
| mark e
| |
| append e to C
| |
| F = F - e
| |
| v = other endpoint of e
| |
| end
| |
| </pre>
| |
| | |
| ==Using DFS==
| |
| | |
| Euler tours can be found in directed graphs by using a depth-first search tree (see [[Graphs/DFS]]). | |
| | |
| Start by constructing a DFS tree. Next, begin traversing the graph at the root of the DFS tree. Traverse the edges in '''reverse''' direction; any edge that leads back to the root node should be used '''last'''.
| |
| | |
| =Related=
| |
| | |
| {{TraversalRelated}}
| |
| | |
| =Flags=
| |
| | |
| {{GraphsFlag}}
| |
| | |
| [[Category:Traversal]]
| |