Eulerian paths and the Chinese postman problem

Graph theory was born, by tradition, with a puzzle. In the city of Königsberg seven bridges connected the two banks of the river Pregel and two islands. The inhabitants wondered whether it was possible to take a walk crossing each bridge exactly once. In 1736 Leonhard Euler proved that it was impossible, and his reasoning is still the heart of a whole family of algorithms.

The problem is not merely historical. Anyone planning the rounds of snowploughs, refuse collection, meter reading or pipeline inspection must travel along every street, not visit every point. This is exactly the Königsberg question.

Eulerian paths and circuits

In a graph, an Eulerian path traverses every edge exactly once. If it ends at its starting point it is called an Eulerian circuit.

Euler observed that every time you enter a vertex you must also leave it, using two different edges. So, in a circuit, every vertex must have even degree. The full theorem, for undirected connected graphs (ignoring isolated vertices), says:

• an Eulerian circuit exists if and only if all vertices have even degree;
• an open Eulerian path exists if and only if exactly two vertices have odd degree; the path starts at one and ends at the other;
• in all other cases there is none.

In Königsberg the four land areas all had odd degree: no walk.

For directed graphs the condition becomes: at every vertex the in-degree equals the out-degree, and the graph is connected when edge directions are ignored. For an open path, one vertex may have one extra outgoing edge and one may have one extra incoming edge.

Building the circuit: Hierholzer's algorithm

Knowing that the circuit exists is not enough; it has to be built. Hierholzer's algorithm does this in time proportional to the number of edges.

1. Start from a vertex and walk using edges not yet travelled, until you get stuck. In a graph where all degrees are even, you only get stuck where you started.
2. If unused edges remain, take a vertex of the circuit found that still has some, build a new sub-circuit from there and splice it into the main one.
3. Repeat until all edges have been used.

With a stack the implementation is compact:

def hierholzer(adj, start):
    # adj: dictionary vertex -> list of neighbours (directed graph)
    adj = {u: list(vs) for u, vs in adj.items()}
    stack, circuit = [start], []
    while stack:
        u = stack[-1]
        if adj.get(u):
            stack.append(adj[u].pop())
        else:
            circuit.append(stack.pop())
    return circuit[::-1]

For an undirected graph each edge must also be marked as used in both directions, usually with an identifier per edge.

An alternative method, Fleury's algorithm, avoids crossing bridges as long as there is an alternative. It is more intuitive to carry out by hand, but much slower, because every step requires a connectivity check.

The Chinese postman problem

In reality almost no road network has all vertices of even degree. The postman must still travel along every street at least once and return to the post office, and accepts going over some streets again. Which streets should be repeated to minimise the total length? This is the Chinese postman problem, so called because it was studied by the Chinese mathematician Kwan Mei-Ko in the 1960s.

For an undirected graph the solution is elegant:

1. find the vertices of odd degree, which are always even in number;
2. compute the shortest distances between all pairs of these vertices;
3. pair them up so as to minimise the sum of distances (a minimum-cost perfect matching);
4. duplicate the edges along the chosen shortest paths: now all degrees are even;
5. build the Eulerian circuit on the resulting graph.

The optimal length is the sum of all streets plus the sum of the matching distances.

An example

A neighbourhood has four junctions with odd degree: A, B, C, D. The shortest distances are A–B 2, C–D 3, A–C 4, B–D 5, A–D 6, B–C 4. There are three possible pairings:

The best choice is to repeat the streets along paths A–B and C–D: the round costs 5 units more than the total length of the network.

Real-world variants

• Mixed graph: some streets are one-way, others are not. This version is much harder and is tackled with heuristics or integer programming.
• Rural postman: only some streets need servicing, the others can be used to move around. Here too the problem becomes hard in general.
• Several vehicles and capacities: a refuse truck fills up and has to unload. These are capacitated arc routing problems, solved in practice with metaheuristics.

In short

• An Eulerian path uses every edge once; the criterion depends only on the parity of degrees.
• Hierholzer's algorithm builds the circuit in time linear in the number of edges.
• The Chinese postman repeats the minimum set of streets needed to make every degree even.
• The solution combines shortest paths, minimum-cost matching and an Eulerian circuit.
• One-way streets, partial service and capacities make the real problem much harder.