From charlesreid1

(Redirected from Graphs/Euler Tour)

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

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

Overview

An Euler Circuit is an Euler path or Euler tour (a path through the graph that visits every edge of the graph exactly once) that starts and ends at the same vertex.


Algorithm

Undirected Graphs: Fleury's Algorithm

To print the Euler Circuit of an undirected graph (if it has one), you can use Fleury's Algorithm [1].

This algorithm is O(E^2) (where E is number of edges).

Step 1:

  • Check that the graph has 0 or 2 odd vertices
  • If there are any other number of odd vertices, no Euler circuit exists

Step 2:

  • If there are 0 odd vertices, start at any node on the graph
  • If there are 2 odd vertices, start at one of the odd vertices

Step 3:

  • Follow edges one at a time.
  • Edges can be classified as bridges (edges that lead to "dead end" nodes with only one edge) or non-bridges
  • If you have a choice among multiple edges, choose the non-bridges first, leave the bridge edge for last.

Step 4:

  • Stop when you run out of edges.

Directed Graphs: Hierholzer's Algorithm

To print the Euler circuit on a directed graph, use the Hierholzer algorithm. It was published in 1873.

This algorithm is O(E) (where E is number of edges).

Links:

Setup: ensure an Euler path can exist

  • There should be a single vertex in graph which has (indegree + 1 == outdegree), this is the Euler path start vertex
  • There should be a single vertex in graph which has (indegree == outdegree + 1), this is the Euler path end vertex
  • Rest all vertices should have (indegree==outdegree)
  • If any of above conditions fail, an Euler path cannot exist.

NOTE: What about the case of an Euler Cycle? Then all vertices have indegree==outdegree, but there is not a start/end vertex.

Setup: turn the Euler path into an Euler cycle

  • If no edge from B to A exists, create an edge B -> A
  • Now indegree == outdegree for all vertices

Algorithm:

  • Choose any vertex v and push it onto the stack
  • While stack is not empty, look at top vertex u on stack.
  • If u has an unvisited edge (e.g., to vertex w), push the destination vertex w onto the stack, and mark the edge u-w as visited.
  • If u has no unvisited edges, pop u off the stack and print it.
  • When the stack is empty, you have printed sequence of vertices corresponding to Eulerian cycle

Clean-up:

  • Check the length of the Eulerian cycle printed has a sufficient number of edges or not.
  • If number of edges in cycle matches number of edges in graph, it is an Eulerian cycle.
  • If number of edges in cycle mismatches number of edges in graph, the original graph may be disconnected (no Euler cycle/path exists)

Euler cycle vs Euler path:

  • If no directed edge B -> A existed in the original graph, remove that edge from the graph and from the cycle to obtain the Euler path

Related

Graphs:

Traversals on trees:

Breadth-first search and traversal on trees:

  • BFS - breadth first search
  • BFT - breadth first traversal

Depth-first search and traversal on trees:

  • DFS - depth first search
  • DFT - depth first traversal

OOP design patterns:

Category:Traversal

Flags