Graph Magics



Eulerian Path and Circuit


Task:

Given an undirected or a directed graph, find a path or circuit that passes through each edge exactly once.

Solution:

First let's see the conditions for an undirected graph:

  • An undirected graph has an eulerian circuit if and only if it is connected and each vertex has an even degree (degree is the number of edges that are adjacent to that vertex).
  • An undirected graph has an eulerian path if and only if it is connected and all vertices except 2 have even degree. One of those 2 vertices that have an odd degree must be the start vertex, and the other one must be the end vertex.
For a directed graph we have:
  • A directed graph has an eulerian circuit if and only if it is connected and each vertex has the same in-degree as out-degree.
  • A directed graph has an eulerian path if and only if it is connected and each vertex except 2 have the same in-degree as out-degree, and one of those 2 vertices has out-degree with one greater than in-degree (this is the start vertex), and the other vertex has in-degree with one greater than out-degree (this is the end vertex).

Algorithm for undirected graphs:

  1. Start with an empty stack and an empty circuit (eulerian path).
    - If all vertices have even degree - choose any of them.
    - If there are exactly 2 vertices having an odd degree - choose one of them.
    - Otherwise no euler circuit or path exists.
  2. If current vertex has no neighbors - add it to circuit, remove the last vertex from the stack and set it as the current one. Otherwise (in case it has neighbors) - add the vertex to the stack, take any of its neighbors, remove the edge between selected neighbor and that vertex, and set that neighbor as the current vertex.
  3. Repeat step 2 until the current vertex has no more neighbors and the stack is empty.


  4. Note
    that obtained circuit will be in reverse order - from end vertex to start vertex.
Algorithm for directed graphs:
  1. Start with an empty stack and an empty circuit (eulerian path).
    - If all vertices have same out-degrees as in-degrees - choose any of them.
    - If all but 2 vertices have same out-degree as in-degree, and one of those 2 vertices has out-degree with one greater than its in-degree, and the other has in-degree with one greater than its out-degree - then choose the vertex that has its out-degree with one greater than its in-degree.
    - Otherwise no euler circuit or path exists.
  2. If current vertex has no out-going edges (i.e. neighbors) - add it to circuit, remove the last vertex from the stack and set it as the current one. Otherwise (in case it has out-going edges, i.e. neighbors) - add the vertex to the stack, take any of its neighbors, remove the edge between that vertex and selected neighbor, and set that neighbor as the current vertex.
  3. Repeat step 2 until the current vertex has no more out-going edges (neighbors) and the stack is empty.


  4. Note
    that obtained circuit will be in reverse order - from end vertex to start vertex.
Both algorithms will give you the tour in reverse order, i.e. from the end vertex to the start vertex.
As you can see - the algorithms are very similar.

Complexity:

The complexity of both algorithms is O(N+M), where N is the number of vertices and M is the number of edges.


Sample Execution:



Given:

A sample undirected graph made in Graph Magics.

Below execution steps of this algorithm are shown (all images are created in Graph Magics).

Legend:
- current vertex is surrounded by red color

Starting state:

Stack: empty
Location: none
Circuit: empty


Download this graph (viewable with Graph Magics)



Because all vertices have even degrees, we can select any vertex as start point. Let it be 1.

Current state:

Stack: empty
Location: 1
Circuit: empty

Go to vertex 2 (a neighbor of 1), add 1 to the stack, delete the edge between 1 and 2.

Current state:

Stack: 1
Location: 2
Circuit: empty


Go to vertex 3, add 2 to the stack, delete the edge between 2 and 3.

Current state:

Stack: 1, 2
Location: 3
Circuit: empty

Go to vertex 4, add 3 to the stack, delete the edge between 3 and 4.

Current state:

Stack: 1, 2, 3
Location: 4
Circuit: empty

Go to vertex 2, add 4 to the stack, delete the edge between 4 and 2.

Current state:

Stack: 1, 2, 3, 4
Location: 2
Circuit: empty

Go to vertex 8, add 2 to the stack, delete the edge between 2 and 8.

Current state:

Stack: 1, 2, 3, 4, 2
Location: 8
Circuit: empty

Go to vertex 1, add 8 to the stack, delete the edge between 8 and 1.

Current state:

Stack: 1, 2, 3, 4, 2, 8
Location: 1
Circuit: empty

Go to vertex 6, add 1 to the stack, delete the edge between 1 and 6.

Current state:

Stack: 1, 2, 3, 4, 2, 8, 1
Location: 6
Circuit: empty

Go to vertex 9, add 6 to the stack, delete the edge between 6 and 9.

Current state:

Stack: 1, 2, 3, 4, 2, 8, 1, 6
Location: 9
Circuit: empty

Go to vertex 1, add 9 to the stack, delete the edge between 9 and 1.

Current state:

Stack: 1, 2, 3, 4, 2, 8, 1, 6, 9
Location: 1
Circuit: empty

Because vertex 1 (current location) has no more neighbors left - we add it to the circuit, take the vertex from the top of the stack (i.e. vertex 9), and set it as the current location.

Current state:

Stack: 1, 2, 3, 4, 2, 8, 1, 6
Location: 9
Circuit: 1

Vertex 9 has no neighbors left. Thus we add it to the end of the circuit, remove vertex 6 from the stack and set it as the current location.

Current state:

Stack: 1, 2, 3, 4, 2, 8, 1
Location: 6
Circuit: 1, 9

Vertex 6 has no nieghbors left. Add it to the circuit, remove 1 from the stack and set it as the current location.

Current state:

Stack: 1, 2, 3, 4, 2, 8
Location: 1
Circuit: 1, 9, 6

Add 1 to the circuit, go to vertex 8 and remove it from the sack.

Current state:

Stack: 1, 2, 3, 4, 2
Location: 8
Circuit: 1, 9, 6, 1

Now 8 has still some more neighbors left. We take one of them - let it be 5.
Add 8 to the stack, go to vertex 5 and delete the edge between these two vertices.

Current state:

Stack: 1, 2, 3, 4, 2, 8
Location: 5
Circuit: 1, 9, 6, 1

Go to vertex 7, add 5 to the stack and delete the edge between these two vertices.

Current state:

Stack: 1, 2, 3, 4, 2, 8, 5
Location: 7
Circuit: 1, 9, 6, 1

Go to vertex 8, add 7 to the stack and delete the edge between these two vertices.

Current state:

Stack: 1, 2, 3, 4, 2, 8, 5, 7
Location: 8
Circuit: 1, 9, 6, 1

Note that no more edges are left, so next steps will only take last vertex from the stack and will add it to the circuit.

Add 8 to the circuit, return to vertex 7 and remove it from the stack.

Current state:

Stack: 1, 2, 3, 4, 2, 8, 5
Location: 7
Circuit: 1, 9, 6, 1, 8

Add 7 to the circuit, return to 5 and remove it from the stack.

Current state:

Stack: 1, 2, 3, 4, 2, 8
Location: 5
Circuit: 1, 9, 6, 1, 8, 7

Add 5 to the circuit, return to 8 and remove it from the stack.

Current state:

Stack: 1, 2, 3, 4, 2
Location: 8
Circuit: 1, 9, 6, 1, 8, 7, 5

Add 8 to the circuit, return to 2 and remove it from the stack.

Current state:

Stack: 1, 2, 3, 4
Location: 2
Circuit: 1, 9, 6, 1, 8, 7, 5, 8


Add 2 to the circuit, return to 4 and remove it from the stack.

Current state:

Stack: 1, 2, 3
Location: 4
Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2


Add 4 to the circuit, return to 3 and remove it from the stack.

Current state:

Stack: 1, 2
Location: 3
Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2, 4


Add 3 to the circuit, return to 2 and remove it from the stack.

Current state:

Stack: 1
Location: 2
Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2, 4, 3


Add 2 to the circuit, return to 1 and remove it from the stack.

Current state:

Stack:
Location: 1
Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2, 4, 3, 2


The stack is empty and 1 has no more neighbors. So this is the last point in this eulerian tour.
Finally add 1 to the circuit.

Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2, 4, 3, 2, 1

Here the order doesn't matter, but for directed graphs - it's crucial.
So let's consider the Eulerian Tour for this graph to be the reverse of the above circuit:

1, 2, 3, 4, 2, 8, 5, 7, 8, 1, 6, 9, 1




Applications:
  • A postman has to visit a set of streets in order to deliver mails and packages. It is needed to find a path that starts and ends at the post-office, and that passes through each street (edge) exactly once. This way the postman will deliver mails and packages to all streets he has to, and in the same time will spend minimum efforts/time for the road.

    Note: not all graphs have an eulerian circuit. If needed - the algorithm for Chinese Postman Problem can be used.
 
Copyright 2004-2014 Dumitru Ciubatii. All rights reserved.
Protected by copyright laws and international treaties.