Admin: /* Undirected Graphs */

2019-05-07T22:46:09Z

Undirected Graphs

← Older revision		Revision as of 22:46, 7 May 2019
Line 18:		Line 18:
	According to Skiena:		According to Skiena:

	* An undirected graph contains an Euler cycle iff (1) it is connected, and (2) each vertex is of even degree		* An undirected graph contains an Euler '''cycle''' iff (1) it is connected, and (2) each vertex is of even degree
	* An undirected graph contains an Euler path iff (1) it is connected, and (2) all but two vertices are of even degree. These two		* An undirected graph contains an Euler '''path''' iff (1) it is connected, and (2) all but two vertices are of even degree. These two vertices will be the start and end vertices for the Eulerian path.
	vertices will be the start and end vertices for the Eulerian path.

	==Directed Graphs==		==Directed Graphs==

Admin at 05:29, 2 May 2019

2019-05-02T05:29:38Z

← Older revision		Revision as of 05:29, 2 May 2019
Line 79:		Line 79:
	end		end
	</pre>		</pre>


			=Related=

			{{TraversalRelated}}

			=Flags=

			{{GraphsFlag}}

			[[Category:Traversal]]

Admin at 05:29, 2 May 2019

2019-05-02T05:29:17Z

← Older revision		Revision as of 05:29, 2 May 2019
Line 1:		Line 1:
	~~#REDIRECT~~ [[Graphs/Euler Tour]]		{{EulerPathEulerCycle}}

			=Notes=


			An Euler path of a graph G is a traversal of the graph that visits each '''edge''' of the graph exactly once.

			An Euler tour, Euler circuit, or Euler cycle is an Euler path (i.e., a path that visits each edge once) that '''also''' starts and ends on the same vertex.

			Determining if an Euler path or 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 (edge) 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.

			According to Skiena:

			* An undirected graph contains an Euler cycle iff (1) it is connected, and (2) each vertex is of even degree
			* An undirected graph contains an Euler path iff (1) it is connected, and (2) all but two vertices are of even degree. These two
			vertices will be the start and end vertices for the Eulerian path.

			==Directed Graphs==

			How to check if a directed graph has an Euler tour?

			According to Skienna,

			* A directed graph contains an Euler cycle iff (1) it is strongly-connected, and (2) each vertex has the same in-degree as out-degree
			* A directed graph contains an Euler path iff (1) it is connected, and (2) all vertices except two (x,y) have the same in-degree as out-degree, and (x,y) are vertices with in-degree one less than and one more than out-degree

			==Using DFS==

			DFS can be used to tell if a graph is connected - or, for a directed graph, strongly connected.

			For an undirected graph, a DFS should traverse every node if the graph is connected, so perform a DFS and check to make sure the number of vertices visited matches the number of vertices in the graph. If not, the graph is not connected and no Euler tour or Euler path exists.

			For a directed graph, a random start node is selected, and a DFS is performed to ensure all nodes are reachable by u (start node), then DFS is performed on the transpose of the graph (every edge u,v reversed to v,u) to ensure all nodes can reach u.

			See [[Graphs/DFS]].


			=Code=

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

Admin: Redirected page to Graphs/Euler Tour

2019-04-26T23:05:23Z

Redirected page to Graphs/Euler Tour

New page

#REDIRECT [[Graphs/Euler Tour]]

Graphs/Euler Path - Revision history

Admin: /* Undirected Graphs */

Admin at 05:29, 2 May 2019

Admin at 05:29, 2 May 2019

Admin: Redirected page to Graphs/Euler Tour