6.5 Eulerization and the Chinese Postman Problem

Not every graph has an Euler path or circuit, yet our lawn inspector still needs to do her inspections. Her goal is to minimize the amount of walking she has to do. In order to do that, she will have to duplicate some edges in the graph until an Euler circuit exists.

Note that we can only duplicate edges, not create edges where there wasn’t one before. Duplicating edges would mean walking or driving down a road twice, while creating an edge where there wasn’t one before is akin to installing a new road!

In the example above, you’ll notice that the last eulerization required duplicating seven edges, while the first two only required duplicating five edges. If we were eulerizing the graph to find a walking path, we would want the eulerization with minimal duplications. If the edges had weights representing distances or costs, then we would want to select the eulerization with the minimal total added weight.

# Ch 6.5 - Eulerization: duplicate the FEWEST edges until every degree is even.
# The lawn inspector has to walk every street; duplicated edges are streets she
# has to walk twice, so we want as few of them as possible.

def hops(g, src):                      # BFS - fewest edges from src to everyone
    d, queue = {src: 0}, [src]
    while queue:
        v = queue.pop(0)
        for w in g[v]:
            if w not in d:
                d[w] = d[v] + 1
                queue.append(w)
    return d

def cheapest_pairing(odds, dist):      # try every way to pair the odd vertices
    if not odds:
        return 0, []
    first, best = odds[0], (float("inf"), [])
    for partner in odds[1:]:
        rest = [v for v in odds[1:] if v != partner]
        sub, pairs = cheapest_pairing(rest, dist)
        total = sub + dist[first][partner]
        if total < best[0]:
            best = (total, [(first, partner)] + pairs)
    return best

def eulerize(g, name=str):
    odds = sorted(v for v in g if len(g[v]) % 2)
    print(f"   {len(g)} corners, {sum(len(n) for n in g.values()) // 2} street segments")
    print(f"   odd-degree corners ({len(odds)}): {', '.join(name(v) for v in odds)}")
    if len(odds) > 12:
        print(f"   {len(odds)} odd corners means too many pairings to check - "
              "shrink the grid")
        return
    dist = {v: hops(g, v) for v in odds}
    total, pairs = cheapest_pairing(odds, dist)
    for a, b in pairs:
        print(f"      walk the {dist[a][b]}-segment path {name(a)} to {name(b)} twice")
    print(f"   fewest segments that must be duplicated: {total}")

print("The Try it Now 4 graph (the book duplicates edge BC):")
eulerize({"A": ["B", "C"], "B": ["A", "C", "D"],
          "C": ["A", "B", "D"], "D": ["B", "C"]})

ROWS, COLS = 2, 3       # TRY IT: 1,3 then 3,3 then 3,4 - does the answer double
                        # when the neighbourhood doubles?
print(f"\nA {ROWS} x {COLS} rectangular block of streets:")
grid = {(r, c): [] for r in range(ROWS + 1) for c in range(COLS + 1)}
for (r, c) in list(grid):
    for nb in ((r + 1, c), (r, c + 1)):
        if nb in grid:
            grid[(r, c)].append(nb)
            grid[nb].append((r, c))
eulerize(grid, name=lambda v: f"({v[0]},{v[1]})")

The problem of finding the optimal eulerization is called the Chinese Postman Problem, a name given by an American in honor of the Chinese mathematician Mei-Ko Kwan who first studied the problem in 1962 while trying to find optimal delivery routes for postal carriers. This problem is important in determining efficient routes for garbage trucks, school buses, parking meter checkers, street sweepers, and more.

Unfortunately, algorithms to solve this problem are fairly complex. Some simpler cases are considered in the exercises.

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.