中国邮递员问题

中国邮递员问题（Chinese postman problem）要求在带权网络中找到一条总长度最小的闭合行走，使每条要求服务的边至少被经过一次。本文讨论所有边都要服务、边权非负的有限连通无向图；允许重复经过边和顶点，终点必须回到起点。

它与访问每个顶点的旅行商问题不同。巡检道路、清扫街道等任务往往要求覆盖整条边，而非只到达路口。最基本的困难在于：各边各走一次以后，未必能把所有经过拼成一条闭合巡回；重复的部分必须花在能修复这种困难的地方。

欧拉回路与奇数度顶点

若一条闭合行走恰好经过每条边一次，称为欧拉回路。沿这样的回路，每次进入一个顶点，都要沿另一条边离开，所以每个顶点的度数必须为偶数。

反过来，若有边的图连通且所有度数为偶数，从任一点沿尚未使用的边行进，不会在起点以外被迫终止：在非起点，已进入的次数比已离开的次数多一，剩余度数不可能为零。于是先形成一个闭合回路。若还有未用边，连通性保证当前回路上某点可通向未用部分；从那里再走一个未用边回路，把它拼入原回路。每次至少用掉一条新边，有限次后便使用全部边。这证明了无向连通图具有欧拉回路当且仅当所有度数为偶数。

图中奇数度顶点总有偶数个，因为总度数等于边数的两倍。若记奇点集合为 $O$ ，重复走一条从 $u$ 到 $v$ 的路径，会使两个端点的度数各增加一，内部顶点各增加二。因此补路的目标是把奇点成对修复。^[1]

最短路匹配公式及证明

记原边权总和为 $W = \sum_{e \in E} w_{e}$ ， $d (u, v)$ 为原图中两点间的最短路径长度。在奇点集合 $O$ 上，考虑把所有奇点两两配对的完美匹配 $M$ 。最优闭合巡回长度为 $W + min_{M} \sum_{{u, v} \in M} d (u, v) .$ 若没有奇点，空匹配的费用为零，原图已经达到下界 $W$ 。

可达性。 对某个最小费用匹配，把每一对端点间的一条最短路径复制一次。每个奇点作为端点恰出现一次，变为偶数度；其余顶点的新增度数为偶数。复制边后仍连通，于是可用刚证明的拼接办法得到欧拉回路，其总长正是公式中的值。

下界。 任取一条覆盖全部原边的闭合行走，把每条边第一次需要的那一份留给原图，其余经过构成补充多重边图。最终经过次数图所有度数为偶数，所以补充图的奇点集合恰为 $O$ 。从一个奇点出发沿补充边取路，直到另一个奇点，将该路删去；两个端点的奇偶性被修复，内部点奇偶性不变。重复后，补充边分成配对奇点的路径以及剩余闭合部分。每条配对路径长度至少为原图相应端点的最短距离，剩余闭合部分费用非负。因此补充总费用至少为某个奇点匹配的距离和，进而至少为最小匹配费用。上下界相同，公式得证。

非负权重在此保证删去额外闭合部分不会增加费用。若有可反复经过的负费用无向边，来回走可能令费用无下界，不能沿用这一定理。

五条单位边的完整例子

四个顶点 $A, B, C, D$ 构成正方形的四条边，再加对角边 $A C$ ，每条权重都为一。图的画法只显示连接关系，边权不按纸面几何长度量取。度数为 $\deg A = \deg C = 3, \deg B = \deg D = 2.$ 因此 $O = {A, C}$ ，只有一种配对；最短距离为一。原边总费用五，最优费用为六。复制 $A C$ 后，可以走 $A \to B \to C \to D \to A \to C \to A .$ 四条边各一次，对角边两次，总计六，且回到起点。

四边形加对角边AC使A和C为奇点，旁边用偏移虚线标示重复AC — 全部边权为一，金色偏移虚线表示对角边 AC 的第二次经过，不是新增的一条可任选捷径。

变式。 再从 $B$ 连接叶顶点 $E$ ，边 $B E$ 的权为二。原边总费用七，奇点变成 $A, B, C, E$ 。三种匹配的补路费用是 $d (A, C) + d (B, E) = 1 + 2 = 3,$ $d (A, B) + d (C, E) = 1 + 3 = 4, d (A, E) + d (B, C) = 3 + 1 = 4.$ 所以最优费用为十，应补 $A C$ 和 $B E$ 。叶边必须出去后再返回，这次额外费用二不是任选路径算法的失误，而是闭合覆盖的必需成本。

增加权二叶边BE后，四个奇点的三种配对费用分别三四四 — 先计算原图中的最短距离，再比较完整配对。配对的费用是路径长度，端点之间不必原来就有直接边。

小奇点集上的精确计算

下面实现先用 Floyd–Warshall 计算全部最短距离，再对奇点位掩码作配对动态规划。输入为编号 $0, \dots, n - 1$ 的连通无向简单图；权重接受非负整数或 Fraction，以避免把浮点误差称为精确最优证书。函数不改输入，返回最优长度及奇点配对；不返回整条巡回。实际路线还需恢复各对的最短路径、复制边，再按前述欧拉拼接法构造。

Python 3

from fractions import Fraction
from functools import lru_cache


def postman_cost(n, edges):
    if type(n) is not int or n < 1:
        raise ValueError("n must be positive")
    distance = [[None] * n for _ in range(n)]
    degree = [0] * n
    total, seen = Fraction(0), set()
    for i in range(n):
        distance[i][i] = Fraction(0)
    for u, v, weight in edges:
        if type(u) is not int or type(v) is not int:
            raise TypeError("Integer vertex labels required")
        if not (0 <= u < n and 0 <= v < n) or u == v:
            raise ValueError("Invalid edge")
        if isinstance(weight, bool) or not isinstance(weight, (int, Fraction)):
            raise TypeError("Use exact integer or Fraction weights")
        w = Fraction(weight)
        edge = (min(u, v), max(u, v))
        if w < 0 or edge in seen:
            raise ValueError("Nonnegative simple edges required")
        seen.add(edge)
        distance[u][v] = distance[v][u] = w
        degree[u] += 1
        degree[v] += 1
        total += w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if distance[i][k] is None or distance[k][j] is None:
                    continue
                candidate = distance[i][k] + distance[k][j]
                if distance[i][j] is None or candidate < distance[i][j]:
                    distance[i][j] = candidate
    if any(value is None for row in distance for value in row):
        raise ValueError("The graph must be connected")
    odd = [i for i in range(n) if degree[i] % 2]
    count = len(odd)

    @lru_cache(None)
    def match(mask):
        if mask == 0:
            return Fraction(0), ()
        i = (mask & -mask).bit_length() - 1
        rest = mask ^ (1 << i)
        candidates = []
        for j in range(i + 1, count):
            if rest & (1 << j):
                cost, pairs = match(rest ^ (1 << j))
                candidates.append((distance[odd[i]][odd[j]] + cost,
                                   ((odd[i], odd[j]),) + pairs))
        return min(candidates)

    added, pairs = match((1 << count) - 1)
    return total + added, pairs


graph = [(0, 1, 1), (1, 2, 1), (2, 3, 1), (3, 0, 1), (0, 2, 1)]
print(postman_cost(4, graph))
print(postman_cost(5, graph + [(1, 4, 2)]))
# (Fraction(6, 1), ((0, 2),))
# (Fraction(10, 1), ((0, 2), (1, 4)))

动态规划每次固定剩余奇点中编号最小的那个 $i$ ，枚举它与哪个 $j$ 配对，再求余下集合的最小费用。任一完美匹配恰有一个与 $i$ 配对的点，所以这些分支覆盖所有可能且不漏解；以空集费用零为基例，对剩余点数归纳便证明递推正确。

设奇点数为 $r$ 。最短路阶段需 $O (n^{3})$ 次加法、比较；配对阶段至多 $2^{r}$ 个状态，每个枚举 $O (r)$ 个伙伴，并复制至多 $O (r)$ 的证书元组，因此这份实现的保守时间上界为 $O (n^{3} + r^{2} 2^{r})$ ，存储为 $O (n^{2} + r 2^{r})$ ，有理数位长另计。它适用于小奇点集；一般无向中国邮递员问题可用多项式时间的最小权完美匹配算法，而不是必须指数枚举。

模型的范围

本文要求每条原边都服务，且每条边两个方向费用相同。如果只需服务指定的一部分边，连接这些必经边的费用也会参与选择；如果是有向图，则要平衡各点的入度与出度；若道路两个方向费用不同，也不能只按无向奇偶性处理。开放路线、车辆容量和时间窗都会改变问题，须先写清实际约束再选算法。

参考资料

↑ Amedeo R. Odoni：Networks: Lecture 1，MIT 1.203J，2006-11-15，PDF第13–21页，无向中国邮递员问题、欧拉条件及奇点最小费用匹配。本文使用不同的小图并补全上下界论证。

[odoni-1] Amedeo R. Odoni：Networks: Lecture 1，MIT 1.203J，2006-11-15，PDF第13–21页，无向中国邮递员问题、欧拉条件及奇点最小费用匹配。本文使用不同的小图并补全上下界论证。

[1]