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:

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

Flags

Graphs/Euler Circuit

From charlesreid1

Contents

Overview

Algorithm

Undirected Graphs: Fleury's Algorithm

Directed Graphs: Hierholzer's Algorithm

Related

Flags