Eulerian Circuits and Paths

Problem:
Given an undirected graph G = (V,E) we need to find a path which uses every edge exactly once - we are allowed to visit vertices multiple times to achieve our goal. If the start and ending vertex must be the same, then this is known as an Eulerian Circuit. Otherwise, this is known as an Eulerian path.

Algorithm:
There is a simple existence theorem which we can use to determine whether or not a graph has an Eulerian circuit and/or path. These are given without proofs:

- A graph has an Eulerian circuit if and only if it is both connected (i.e. from a given vertex we can reach all other vertices through some arbitrary path) and every node has an even degree (which is the number of edges a particular vertex has).

- A graph has an Eulerian path if and only if it is both connected and every node except for two has an even degree.

It follows that an Eulerian circuit is a special case of an Eulerian path in which the start and end vertices are the same. We are allowed to have two non-even degree vertices for an Eulerian path as these denote the start and end vertices.

The classic algorithm to solve this problem is called Fleury's Algorithm. Fleury's Algorithm is pretty simple and intuitive:

- Pick any starting vertex.
- Traverse in a DFS-like manner on edges that haven't been traversed yet. The special case is not to traverse a bridge unless that is the only edge remaining (this is because if we traverse through a bridge we can't come back to the other side by definition as we are only allowed to traverse an edge exactly once).
- When the edge is traversed, erase/delete the edge from the graph.
- Recurse on the new vertex and keep repeating until all edges have been traversed.

The problem with Fleury's when translating it to code is detecting bridges. We present another algorithm which is just as simple but resolves this issue implicitly through the use of backtracking. This algorithm is from the USACO training pages which can also be accessed here: http://acm.fzu.edu.cn/reference/Eulerian%20Tour.htm

Basically, we recurse like in Fleury's Algorithm without consideration of bridges. We also construct the Eulerian path/circuit in reverse order by appending book-keeping information post-processing order. For more details about this algorithm - see the above link. You may ask, how does this avoid having to keep track of bridges?

Firstly, let's make some observations. Take a look at the graph below:

Imagine we are at vertex C. We have several possible choices to traverse - either to vertex E (using edge CE), vertex F (using CF) and vertex D (using CD). Note that if we delete the edge we came from, we are essentially creating a subproblem in which we lose one edge and start "again" from the new vertex we just traversed to in the previous step. For example, if we traverse to vertex E, we are left with only two vertices E-B as a subproblem. The interesting thing to note is that the subproblems carry the same properties as our original problem. Namely, all vertices are either even or they are all even except for two.

Now we need to convince ourselves that the order of traversals of our algorithm does not matter as it produces the correct path for all cases. The first case is when our problem (or subproblem) has no bridges, in which case the order does not matter as we will not exclude any vertices/edges being visited later. The second case is when our problem (or subproblem) has bridges. Our graph above has such a bridge (edge CE). If we were to traverse through this edge before visiting the edges CD, CF and DF then we won't have a valid path as we can't go back on edge CE to visit these edges - thus by definition it won't be an Eulerian path.

However our algorithm adds vertices in a backwards manner. If we visit edge CE first, our stack for the subproblem would be: B-E. Then we visit either edge CF or CD (from backtracking to our vertex C call). The second subproblem's stack are both C-F-D (trace it yourself for edges CF and CD). Since we visited edge CE first, our problem's stack becomes B-E-C-F-D. Since we have now deleted edges CD, CE and CF. Vertex C has no neighbours and hence gets added on as well, yielding: B-E-C-F-D-C. Reversing this path we get the Eulerian path of C-D-F-C-E-B.

If we don't visit edge CE first, then we don't get more than 1 new subproblem (i.e. more than one component) as we don't "violate" the bridge (i.e. we visit all the edges on the left side before traversing it). Hence in this case, our algorithm produces the correct answer also. Intutitively this means that if we generate a disconnected component (by using a bridge too early) we actually put these towards the end of the path first and hence as a result their visiting order gets "reversed" implicitly. Therefore, we still generate a valid path and most importantly still visit all the edges, therefore we have an Eulerian path.

So what happens when there are multiple bridges? Luckily our constraint of at most two vertices having odd degrees saves us a lot of trouble. Draw it out yourself by constructing potential counterexamples!

Our particular graph only has an Eulerian path (not a circuit) because there are two edges with odd degrees (namely vertex C and B). However it is trivial to use the same algorithm for a graph with only even degree vertices - just start at any vertex! For graphs such as the one above, we must start our algorithm on one of the odd degree vertices.

Application (USACO Training Pages - Riding the Fences):

Farmer John owns a large number of fences, which he must periodically check for integrity. Farmer John keeps track of his fences by maintaining a list of their intersection points, along with the fences which end at each point. Each fence has two end points, each at an intersection point, although the intersection point may be the end point of only a single fence. Of course, more than two fences might share an endpoint.

Given the fence layout, calculate if there is a way for Farmer John to ride his horse to all of his fences without riding along a fence more than once. Farmer John can start and end anywhere, but cannot cut across his fields (the only way he can travel between intersection points is along a fence). If there is a way, find one way.

This is a simple application of the Eulerian algorithm outlined above:

using namespace std;

int adjmat[511][511];
int visited[511];
int circuit[1111];
int numEdges[511];
int circuitpos;

void euler_circuit(int pos) {
   bool change = true;
   while (change) {
      change = false;
      for (int i = 0; i < 511; i++) {
         if (adjmat[pos][i] > 0) {
            change = true;
            adjmat[pos][i]--;
            adjmat[i][pos]--;
            euler_circuit(i);
         }
      }
   }
   circuit[circuitpos++] = pos;
}

int main() {
   ifstream inFile("fence.in");
   ofstream outFile("fence.out");
   int F; inFile >> F;
   int x, y;
   int startNode = 1 << 20;
   for (int i = 0; i < F; i++) {
      inFile >> x >> y;
      adjmat[x][y]++;
      adjmat[y][x]++;
      numEdges[x]++; numEdges[y]++;
      startNode = min(startNode, min(x, y));
   }
   for (int i = 505; i >= 0; i--) if (numEdges[i] % 2 != 0) { startNode = i; }
   euler_circuit(startNode);
   for (int i = circuitpos-1; i >= 0; i--) outFile << circuit[i] << "\n";
   return 0;
}