Euler path - a path around a graph that visits every edge of the graph exactly once.

The following pages all redirect to Graphs/Euler Path:
- Euler Path
- Graphs/Euler Path

Euler circuit/Euler cycle - an Euler path that starts and ends at the same vertex.

The following pages all redirect to Graphs/Euler Circuit:

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

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

Fleury's Algorithm

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

Flags

Graphs/Euler Path

From charlesreid1

Contents