Graphs/Euler Tour - Revision history

Admin: Redirected page to Graphs/Euler Circuit

2019-05-02T05:30:37Z

← Older revision		Revision as of 05:30, 2 May 2019
Line 1:		Line 1:
	~~Euler tour/Euler path - a path through a graph that visits every edge of the graph exactly once.~~		#REDIRECT [[Graphs/Euler Circuit]]
	* The following pages all redirect to [[Graphs/Euler Tour]]:
	** [[Euler Tour]]
	** [[Graphs/Euler Tour]]
	** [[Euler Path]]
	** [[Graphs/Euler Path]]

	~~Euler circuit/Euler cycle - an Euler tour that starts and ends at the same vertex.~~
	* The following pages all redirect to [[Graphs/Euler Circuit]]:
	** [[Euler Circuit]]
	** [[Graphs/Euler Circuit]]
	** [[Euler Cycle]]
	** [[Graphs/Euler Cycle]]

	~~=Notes=~~

	~~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~~]]

Admin at 19:20, 29 April 2019

2019-04-29T19:20:14Z

← Older revision		Revision as of 19:20, 29 April 2019
Line 1:		Line 1:
	Euler tour/Euler path - a ~~tour around~~ a graph that visits every edge of the graph exactly once.		Euler tour/Euler path - a path through a graph that visits every edge of the graph exactly once.
	* The following pages all redirect to [[Graphs/Euler Tour]]:		* The following pages all redirect to [[Graphs/Euler Tour]]:
	** [[Euler Tour]]		** [[Euler Tour]]

Admin at 22:51, 27 April 2019

2019-04-27T22:51:54Z

← Older revision		Revision as of 22:51, 27 April 2019
Line 1:		Line 1:
	Euler tour/Euler path - a tour around a graph that visits every edge of the graph exactly once.		Euler tour/Euler path - a tour around a graph that visits every edge of the graph exactly once.
	* [[Euler Tour]], [[Graphs/Euler Tour]]		* The following pages all redirect to [[Graphs/Euler Tour]]:
	* [[Euler Path]], [[Graphs/Euler Path]]		** [[Euler Tour]]
			** [[Graphs/Euler Tour]]
			** [[Euler Path]]
			** [[Graphs/Euler Path]]

	Euler circuit/Euler cycle - an Euler tour that starts and ends at the same vertex.		Euler circuit/Euler cycle - an Euler tour that starts and ends at the same vertex.
	* [[Euler Circuit]], [[Graphs/Euler Circuit]]		* The following pages all redirect to [[Graphs/Euler Circuit]]:
	* [[Euler Cycle]], [[Graphs/Euler Cycle]]		** [[Euler Circuit]]
			** [[Graphs/Euler Circuit]]
			** [[Euler Cycle]]
			** [[Graphs/Euler Cycle]]

	=Notes=		=Notes=

Admin at 22:50, 27 April 2019

2019-04-27T22:50:02Z

← Older revision		Revision as of 22:50, 27 April 2019
Line 1:		Line 1:
			Euler tour/Euler path - a tour around a graph that visits every edge of the graph exactly once.
			* [[Euler Tour]], [[Graphs/Euler Tour]]
			* [[Euler Path]], [[Graphs/Euler Path]]

			Euler circuit/Euler cycle - an Euler tour that starts and ends at the same vertex.
			* [[Euler Circuit]], [[Graphs/Euler Circuit]]
			* [[Euler Cycle]], [[Graphs/Euler Cycle]]

	=Notes=		=Notes=

Admin: /* Notes */

2019-04-26T23:07:15Z

Notes

← Older revision		Revision as of 23:07, 26 April 2019
Line 5:		Line 5:
	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.		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.

	For a graph to be Eulerian, the number of vertices with odd degree '''must''' be 0 or 2.		==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.		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.
Line 11:		Line 13:
	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.		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.

	==Pseudocode==		==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>		<pre>

Admin: /* Notes */

2019-04-26T21:55:40Z

Notes

← Older revision		Revision as of 21:55, 26 April 2019
Line 5:		Line 5:
	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.		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.

	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~~. For a graph to be Eulerian, the number of vertices with odd degree '''must''' be 0 or 2~~.		For a 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.		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.

Admin: /* Notes */

2017-09-09T12:10:28Z

Notes

← Older revision		Revision as of 12:10, 9 September 2017
Line 9:		Line 9:
	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.		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.

	Pseudocode:		==Pseudocode==

	<pre>		<pre>

Admin: /* Related */

2017-09-07T15:44:12Z

@@ Line 53: / Line 53: @@
 =Related=
-Graphs:
+{{TraversalRelated}}
 =Flags=

Admin at 15:43, 7 September 2017

2017-09-07T15:43:01Z

← Older revision		Revision as of 15:43, 7 September 2017
Line 53:		Line 53:
	=Related=		=Related=

	~~Also see~~ [[Tree Traversal/Traversal Method Template]] ~~for a description of a template method pattern. This uses method hooks to re-use code that performs an Euler Tour on a tree.~~		Graphs:
			* [[Graphs/Depth First Traversal]]
			* [[Graphs/Breadth First Traversal]]
			* [[Graphs/Euler Tour]]

			Traversals on trees:
			* [[Trees/Preorder]]
			* [[Trees/Postorder]]
			* [[Trees/Inorder]]

			OOP design patterns:
			* [[Tree Traversal/Traversal Method Template]]

			[[:Category:Traversal]]

	=Flags=		=Flags=
Line 59:		Line 72:
	{{GraphsFlag}}		{{GraphsFlag}}

	[[Category:~~Traversals~~]]		[[Category:Traversal]]

Admin: /* Related */

2017-09-07T13:36:59Z

← Older revision		Revision as of 13:36, 7 September 2017
Line 53:		Line 53:
	=Related=		=Related=

	Also see [[Tree Traversal/Traversal Method Template]] for a description of a template method pattern ~~that~~ uses hooks to re-use Euler Tour ~~code~~.		Also see [[Tree Traversal/Traversal Method Template]] for a description of a template method pattern. This uses method hooks to re-use code that performs an Euler Tour on a tree.

	=Flags=		=Flags=