哈密顿路径与哈密顿回路

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. 每个顶点，恰好一次

所谓哈密顿路径，是指恰好经过图中每个顶点一次的路径。而哈密顿回路在此基础上还要沿着再一条边回到起始顶点。具有哈密顿回路的图称为哈密顿图，而具有哈密顿路径的图有时称为可迹图。每个哈密顿图都是可迹的，因为删去哈密顿回路的一条边就得到一条哈密顿路径，但反过来不成立，下面的例子说明了这一点。

这个问题听起来像是 Euler 在 1736 年所解答问题的近亲，关于欧拉路径的指南讲述了那段故事。欧拉迹使用每条边一次；哈密顿路径经过每个顶点一次。两者的难度差异巨大。Euler 的问题只需数一数奇度顶点即可解决，用时是线性的。对于 Hamilton 的问题，目前还不知道有类似的检验方法，而且人们也预计不存在这样的方法。

在上面的房屋形图中，顶点 A 的度为 2， B 和 C 的度为 4， D 和 E 的度为 3。恰好有两个度是奇数，所以存在一条从 D 到 E的欧拉迹，仅凭这些度就能证明这一点。哈密顿回路 A, B, D, E, C 同样存在，但一般而言，要知道它存在的唯一办法就是把它找出来。

2. 从周游世界游戏到 Petersen 图

这个名字来自 William Rowan Hamilton，他在 1857 年推出了周游世界游戏（Icosian game）：游戏盘画成一个正十二面体，即有 12 个五边形面和 20 个顶角的立体，玩家必须沿着边经过全部 20 个顶角并回到起点。Hamilton 以 25 英镑的价格把版权卖给了伦敦的 John Jaques and Son 公司，该公司于 1859 年将这款游戏推向市场。这个问题本身更古老：Thomas Kirkman 在 1856 年发表的一篇论文中就问过，哪些多面体存在经过其所有顶角的回路。

正十二面体恰好有 30 条哈密顿回路，这里每条回路只计一次，不论其方向和起始顶角。 Petersen 图是经典的对照，Julius Petersen 于 1898 年描述了它。它有 10 个顶点和 15 条边，每个顶点的度都是 3，它是连通的且没有割点，然而它没有哈密顿回路。它确实有哈密顿路径。更奇特的是，删去它的任意一个顶点后，剩下的图都有哈密顿回路，这一性质称为亚哈密顿。凡是暗示一个图应当是哈密顿图的简单检验，Petersen 图全都满足，这正是它作为反例出现在图论各处的原因。

3. 证明回路不存在

贯穿全文的示例是一座有 9 个展厅的博物馆，展厅编号为 A 到 I，展厅之间有 14 扇门。一位参观者想恰好参观每个展厅一次，最好还能在出发的地方结束：

doors = {AB, AC, BC, FG, FH, GH, AD, BD, DF, DI, CE, EH, EI, EG}      9 个展厅，14 扇门

deg:   A 3   B 3   C 3   D 4   E 4   F 3   G 3   H 3   I 2

存在一条哈密顿路径： A, B, C, E, G, H, F, D, I 经过每个展厅一次。哈密顿回路则不存在，原因从图上就能看出来。关闭展厅 D 和 E，博物馆的其余部分就分成三个互不相连的部分： {A, B, C}、 {F, G, H} 以及单独的展厅 I。

这个论证适用于任何图。从一个回路中删去 k 个顶点，它至多断成 k 段弧，所以如果一个图有哈密顿回路，那么删去它的任意 k 个顶点后，至多剩下 k 个连通部分。一条路径至多断成 k + 1 段，所以可迹图至多剩下 k + 1个部分。博物馆中有一个由 2 个展厅组成的集合，移除后剩下 3 个部分，这对回路来说太多了，但对路径来说是允许的。Chvátal 于 1973 年研究了这一度量，并称之为坚韧度。

from itertools import combinations

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def pieces(adj, removed):
    """删去 removed 中的顶点后剩下的连通部分数。"""
    seen, count = set(removed), 0
    for s in adj:
        if s in seen:
            continue
        count += 1
        stack = [s]
        seen.add(s)
        while stack:
            for w in adj[stack.pop()] - seen:
                seen.add(w)
                stack.append(w)
    return count

def cycle_obstruction(adj):
    """删去后剩下多于 |S| 个部分的集合 S：证明不存在哈密顿回路。"""
    for k in range(1, len(adj)):
        for S in combinations(sorted(adj), k):
            if pieces(adj, S) > k:
                return list(S), pieces(adj, S)
    return None

museum = graph(['AB', 'AC', 'BC', 'FG', 'FH', 'GH', 'AD', 'BD', 'DF', 'DI', 'CE', 'EH', 'EI', 'EG'])
print(cycle_obstruction(museum))
# (['D', 'E'], 3)
outer = [(i, (i + 1) % 5) for i in range(5)]
spokes = [(i, i + 5) for i in range(5)]
star = [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
petersen = graph(outer + spokes + star)
print(cycle_obstruction(petersen))            # 没有找到证书，但同样没有哈密顿回路
# None

该函数从小到大尝试每一个顶点集合，返回第一个留下过多部分的集合。在博物馆图上，它找到了 {D, E}，这是唯一一个这样的集合。在 Petersen 图上它什么也没找到，尽管 Petersen 图没有哈密顿回路。这正是这一类条件的局限：它能证明回路不可能存在，但它的沉默什么也证明不了。

同一思想有几种特殊情形，值得记住它们的名字：

• 割点。有割点（即删去后会使图不连通的顶点）的图没有哈密顿回路。这就是 k = 1的情形。
• 度为 1 或 2 的顶点。度为 1 的顶点只能是哈密顿路径的端点，绝不可能位于回路上。度为 2 的顶点迫使它的两条边都出现在任何哈密顿回路中：在博物馆中，展厅 I的两扇门都必须用到。
• 不平衡的二分图。在二分图中，回路在两侧之间交替，所以哈密顿回路要求两侧大小相等，而哈密顿路径要求两侧大小之差至多为一。完全二分图 K2,3 正是因此有哈密顿路径而没有哈密顿回路。

4. 保证回路存在的度条件

反方向的问题是：什么能迫使哈密顿回路存在？最著名的答案都用到度，关于顶点的度的指南详细讨论了其中第一个。

• Dirac 定理（1952）。一个具有 n ≥ 3 个顶点、且每个顶点的度都至少为 n / 2 的简单图有哈密顿回路。
• Ore 定理（1960）。只要 deg(u) + deg(v) ≥ n 对每一对不相邻的顶点 u 和 v 都成立即可。Dirac 的条件是其中每个度都至少为 n / 2的特殊情形。
• Bondy–Chvátal 闭包（1976）。反复连接任意两个度之和至少为 n的不相邻顶点。原图是哈密顿图，当且仅当最终得到的图（即它的闭包）是哈密顿图；如果闭包是完全图，答案就是肯定的。
• Chvátal–Erdős 定理（1972）。如果一个图的连通度（即删去后使图不连通所需的最少顶点数）至少等于它的独立数（即最大独立集的大小），那么该图是哈密顿图。关于团与独立集的指南解释了后一个量。

所有这些都是充分条件，而不是必要条件。100 个顶点上的回路是哈密顿图，但每个顶点的度都是 2，远低于 50。博物馆则展示了另一面：它的最大度是 4，低于 9 / 2，所以没有任何度条件适用，这与它没有回路是一致的。在 G 和 I之间再开一扇门后，博物馆就成为哈密顿图，而度条件仍然什么也说不出来。它们描述的是稠密到足以因简单原因而成为哈密顿图的图；稀疏图需要别的工具。

5. 平面图：Tait 猜想与 Tutte 的回答

哈密顿回路一度看起来像是通往四色定理的一条途径。1884 年，Peter Guthrie Tait 猜想每个 3-连通、3-正则的平面图都有哈密顿回路，这将为“每个顶角都与三个区域相接的地图只需四种颜色”给出一个简单的证明。这个猜想是错误的。William Tutte 于 1946 年发表了一个有 46 个顶点的反例，而 Holton 和 McKay 在 1988 年证明了最小的反例有 38 个顶点。

再多一度连通性就足够了。Whitney 在 1931 年证明了每个 4-连通的平面三角剖分都是哈密顿图，Tutte 在 1956 年将这一结论推广到每个 4-连通平面图。这些结果属于少数几个能在稀疏图中保证哈密顿回路存在的结论，而在稀疏图中，第 4 节的度条件无法适用。

6. 用搜索寻找哈密顿路径

最直接的方法是每次把路径延长一个顶点。每一步，它依次尝试最后一个顶点的未访问邻居；当路径无法再延长而仍有顶点未被访问时，它就回退并尝试下一个选择。如果路径最终覆盖了所有顶点，它就是一条哈密顿路径；如果它的两个端点相邻，它还能闭合成一个回路。

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def hamiltonian(adj, cycle=False):
    """回溯：每次把路径延长一个顶点，遇到死胡同就撤销。"""
    n = len(adj)
    def extend(path, seen):
        if len(path) == n:
            return path if not cycle or path[0] in adj[path[-1]] else None
        for w in sorted(adj[path[-1]] - seen):
            found = extend(path + [w], seen | {w})
            if found:
                return found
        return None                           # 所有延续都失败了：回退
    starts = [min(adj)] if cycle else sorted(adj)   # 回路可以从任意顶点开始
    for s in starts:
        found = extend([s], {s})
        if found:
            return found
    return None

museum = graph(['AB', 'AC', 'BC', 'FG', 'FH', 'GH', 'AD', 'BD', 'DF', 'DI', 'CE', 'EH', 'EI', 'EG'])
print(hamiltonian(museum))                    # 每个展厅参观一次
# ['A', 'B', 'C', 'E', 'G', 'H', 'F', 'D', 'I']
print(hamiltonian(museum, cycle=True))        # ……并回到起点
# None
museum['G'].add('I'); museum['I'].add('G')    # 再开一扇门
print(hamiltonian(museum, cycle=True))
# ['A', 'B', 'C', 'E', 'H', 'F', 'G', 'I', 'D']

第一行是第 3 节中的那条路线。第二行确认没有任何路线能回到起点，正如前面的障碍所证明的。第三行表明，在 G 和 I之间再开一扇门，就使哈密顿回路成为可能。在寻找回路时，函数只从一个顶点出发，因为回路经过每个顶点，从其中任何一个开始读都可以。该函数在 1,136 个最多 8 个顶点的随机图上与暴力搜索进行了对照检验。

朴素的回溯是指数级的：在最坏情况下，它要探索顶点的 n! 种排列中的很大一部分，而 20! 约为 2.4 × 1018。实用的求解器会加入剪枝。一旦未访问的顶点不再连通，或者某个顶点剩下的未访问邻居太少、无法再被穿过，或者某个度为 2 的顶点的强制边被堵住，它们就立即放弃这个分支。它们还会优先尝试约束最强的邻居，这与第 9 节中骑士巡游的 Warnsdorff 规则是同一个思想。

7. 子集上的动态规划

更好的最坏情况界来自一个动态规划，它由 Bellman 以及 Held 和 Karp 于 1962 年各自独立发现，最初用于旅行商问题。固定一个起始顶点。对每个包含它的顶点子集 S 以及每个顶点 v （在 S中），记录有多少条路径从固定顶点出发、恰好经过 S中的顶点，并在 v处结束。每个表项都由更小的子集构建而来，完整集合给出哈密顿路径；当路径的最后一个顶点与起点相邻时，它们就闭合成回路。

from itertools import combinations

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def count_hamiltonian_cycles(adj):
    """子集上的动态规划（Bellman；Held 和 Karp），O(2^n * n^2) 时间。"""
    V = sorted(adj)
    n, index = len(V), {v: i for i, v in enumerate(V)}
    ways = [[0] * n for _ in range(1 << n)]   # ways[S][v]：从 V[0] 出发、恰好经过 S、终止于 v 的路径数
    ways[1][0] = 1
    for S in range(1 << n):
        for v in range(n):
            if ways[S][v]:
                for w in adj[V[v]]:
                    j = index[w]
                    if not S >> j & 1:
                        ways[S | 1 << j][j] += ways[S][v]
    full = (1 << n) - 1
    closing = sum(ways[full][index[w]] for w in adj[V[0]])
    return closing // 2                       # 每个回路在两个方向上各被找到一次

museum = graph(['AB', 'AC', 'BC', 'FG', 'FH', 'GH', 'AD', 'BD', 'DF', 'DI', 'CE', 'EH', 'EI', 'EG'])
print(count_hamiltonian_cycles(museum))
# 0
museum['G'].add('I'); museum['I'].add('G')    # 前面那扇额外的门
print(count_hamiltonian_cycles(museum))
# 4
print(count_hamiltonian_cycles(graph(combinations(range(6), 2))))   # K6: (6 - 1)! / 2
# 60

博物馆图没有哈密顿回路，多开一扇门的博物馆图恰好有 4 条，而完全图 K6 有 (6 − 1)! / 2 = 60条，与完全图的公式相符。该程序要检查 2n 个子集，每个子集有 n 个可能的终点，并对每个表项尝试至多 n 个邻居，所以它的运行时间为 O(2n n2)。对于 20 个顶点，这意味着 20,971,520 个表项，规模虽大但完全可行；而逐一列出 K20 的哈密顿回路则意味着要列出 60,822,550,204,416,000 条。已知对无向图最快的算法是 Björklund 于 2014 年发表的一种随机化方法，运行时间为 O*(1.657n)，其中星号隐藏了多项式因子。

8. 这个问题有多难？

判定一个图是否有哈密顿回路是 NP 完全的，无向图和有向图都是如此；这两个版本都在 Karp 1972 年列出的 21 个 NP 完全问题之中。哈密顿路径问题同样是 NP 完全的。这种困难性在很强的限制下依然存在：Garey、Johnson 和 Tarjan 在 1976 年证明，该问题对于 3-连通且 3-正则的平面图仍然是 NP 完全的，这恰好是 Tait 猜想所涉及的图类；Itai、Papadimitriou 和 Szwarcfiter 在 1982 年证明，网格图中的哈密顿路径问题也是 NP 完全的，尽管完整的矩形网格很容易。

与 Euler 问题的对比，是图论中两个问题看似相像、却分处 P 与 NP 分界两侧的最清晰的例子。哈密顿回路问题也是旅行商问题的核心：给图中的边赋予长度 1，给每条缺失的边赋予长度 2，那么这个图有哈密顿回路，当且仅当经过所有顶点的最短路线长度为 n。因此，旅行商问题的任何快速算法也都能判定哈密顿性。

9. 必有哈密顿路径或回路的图族

有些图族由于结构上的原因而是哈密顿的，其中有几个本身就很有名。

• 完全图。对于 Kn，其顶点的每一种排列都是一条哈密顿路径；当 n ≥ 3 时，共有 (n − 1)! / 2 条哈密顿回路。
• 竞赛图。竞赛图是任意两个顶点之间恰好有一条箭头的有向图，就像循环赛的比赛结果一样。Rédei 在 1934 年证明了每个竞赛图都有哈密顿路径，因此总能把选手排成一列，使每位选手都战胜了排在其后的那一位；Camion 在 1959 年证明，只要每位选手都能通过一串胜场到达其他每位选手，竞赛图就有哈密顿回路。
• 超立方体与格雷码。以长度为 n的二进制串为顶点、两个串仅相差一位时相连的立方体图，在 n ≥ 2时是哈密顿图。它的一条哈密顿回路就是一个格雷码：全部 2n 个串的一个列表，其中相邻的串只相差一位。Frank Gray 于 1953 年为用于信号传输的反射二进制码获得了专利。
• 骑士巡游。一个经过棋盘每个格子一次的骑士，在骑士走法图中描出一条哈密顿路径。Euler 在 1759 年研究了这类巡游，Warnsdorff 在 1823 年提出了总是走到后续走法最少的格子这一规则，Schwenk 在 1991 年确定了到底哪些矩形棋盘存在闭合巡游。

10. 随机图：哈密顿回路何时出现？

第 3 节中的障碍大多是局部的：一个只有一条边的顶点，或几个能把图的一部分切下来的顶点。在随机图中，事实证明局部障碍是唯一重要的障碍。Pósa 在 1976 年证明，在 n 个顶点上、约有 C n log n 条边的随机图（其中 C为适当的常数）几乎必然是哈密顿图。Komlós 和 Szemerédi 在 1983 年找到了精确的阈值：它恰好位于度小于 2 的顶点的期望数目降为零的地方。

最强的形式是关于一个每次随机增加一条边而不断生长的图的命题。Bollobás 于 1984 年，以及 Ajtai、Komlós 和 Szemerédi 于 1985 年各自独立地证明：以趋于 1 的概率，这个图恰好在最后一个度小于 2 的顶点消失的那一刻变成哈密顿图。在随机图中，一旦没有明显阻碍哈密顿回路的因素，哈密顿回路就存在。

11. 哈密顿路径的应用

• 路线规划与巡回。每一条必须访问每个地点一次的送货路线、巡检路线或钻孔顺序，都是一个附带距离的哈密顿回路问题，也就是旅行商问题。
• 基因组组装。早期的组装程序把 DNA 读段建模为顶点，按重叠关系连边，然后寻找经过它们的哈密顿路径。Idury 和 Waterman 在 1995 年提出把组装重新表述为 de Bruijn 图中的欧拉路径问题，Pevzner、Tang 和 Waterman 在 2001 年进一步发展了这一方法，这就是现代组装程序求解 Euler 的简单问题、而不是 Hamilton 的困难问题的原因。
• 编码器与格雷码。旋转式和直线式位置编码器使用格雷码，这样从一个位置移到下一个位置时只改变一位，从而避免在过渡期间出现大的读数误差。
• 测试与排序。访问系统的每个状态一次，或者给作业排序使每个作业都跟在一个兼容的前驱之后，都是在允许转换构成的图上的哈密顿路径问题。
• 谜题。周游世界游戏、骑士巡游以及许多画路径的谜题，都是改头换面地要求寻找哈密顿路径或回路。

12. 常见错误

13. 术语表

15. 参考文献

以上定义、定理和归属均出自以下文献，按时间顺序排列。

1. Euler, L. (1759). "Solution d'une question curieuse qui ne paroît soumise à aucune analyse." Mémoires de l'Académie Royale des Sciences et Belles Lettres de Berlin 15，310 至 337 页。标注年份 1759 年，1766 年印行。骑士巡游。
2. Warnsdorff, H. C. von (1823). Des Rösselsprunges einfachste und allgemeinste Lösung. 施马尔卡尔登：Varnhagen。
3. Kirkman, T. P. (1856). "On the Representation of Polyedra." Philosophical Transactions of the Royal Society of London 146，413 至 418 页。
4. Tait, P. G. (1884). "Listing's Topologie." Philosophical Magazine，第 5 辑，17，30 至 46 页。
5. Petersen, J. (1898). "Sur le théorème de Tait." L'Intermédiaire des Mathématiciens 5，225 至 227 页。
6. Whitney, H. (1931). "A Theorem on Graphs." Annals of Mathematics 32(2)，378 至 390 页。
7. Rédei, L. (1934). "Ein kombinatorischer Satz." Acta Litterarum ac Scientiarum Szeged 7，39 至 43 页。
8. Tutte, W. T. (1946). "On Hamiltonian Circuits." Journal of the London Mathematical Society 21(2)，98 至 101 页。
9. Dirac, G. A. (1952). "Some Theorems on Abstract Graphs." Proceedings of the London Mathematical Society s3-2，69 至 81 页。
10. Gray, F. (1953). "Pulse Code Communication." 美国专利 2,632,058。
11. Tutte, W. T. (1956). "A Theorem on Planar Graphs." Transactions of the American Mathematical Society 82，99 至 116 页。
12. Camion, P. (1959). "Chemins et circuits hamiltoniens des graphes complets." Comptes Rendus de l'Académie des Sciences 249，2151 至 2152 页。
13. Ore, O. (1960). "Note on Hamilton Circuits." The American Mathematical Monthly 67(1)，55 页。
14. Bellman, R. (1962). "Dynamic Programming Treatment of the Travelling Salesman Problem." Journal of the ACM 9(1)，61 至 63 页。
15. Held, M. 和 Karp, R. M. (1962). "A Dynamic Programming Approach to Sequencing Problems." Journal of the Society for Industrial and Applied Mathematics 10(1)，196 至 210 页。
16. Chvátal, V. 和 Erdős, P. (1972). "A Note on Hamiltonian Circuits." Discrete Mathematics 2(2)，111 至 113 页。
17. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." 载于 Complexity of Computer Computations，R. E. Miller 和 J. W. Thatcher 编，85 至 103 页。纽约：Plenum。
18. Chvátal, V. (1973). "Tough Graphs and Hamiltonian Circuits." Discrete Mathematics 5(3)，215 至 228 页。
19. Bondy, J. A. 和 Chvátal, V. (1976). "A Method in Graph Theory." Discrete Mathematics 15(2)，111 至 135 页。
20. Garey, M. R., Johnson, D. S. 和 Tarjan, R. E. (1976). "The Planar Hamiltonian Circuit Problem is NP-Complete." SIAM Journal on Computing 5(4)，704 至 714 页。
21. Pósa, L. (1976). "Hamiltonian Circuits in Random Graphs." Discrete Mathematics 14(4)，359 至 364 页。
22. Itai, A., Papadimitriou, C. H. 和 Szwarcfiter, J. L. (1982). "Hamilton Paths in Grid Graphs." SIAM Journal on Computing 11(4)，676 至 686 页。
23. Komlós, J. 和 Szemerédi, E. (1983). "Limit Distribution for the Existence of Hamiltonian Cycles in a Random Graph." Discrete Mathematics 43(1)，55 至 63 页。
24. Bollobás, B. (1984). "The Evolution of Sparse Graphs." 载于 Graph Theory and Combinatorics，B. Bollobás 编，35 至 57 页。伦敦：Academic Press。
25. Ajtai, M., Komlós, J. 和 Szemerédi, E. (1985). "First Occurrence of Hamilton Cycles in Random Graphs." Annals of Discrete Mathematics 27，173 至 178 页。
26. Holton, D. A. 和 McKay, B. D. (1988). "The Smallest Non-Hamiltonian 3-Connected Cubic Planar Graphs Have 38 Vertices." Journal of Combinatorial Theory, Series B 45(3)，305 至 319 页。
27. Schwenk, A. J. (1991). "Which Rectangular Chessboards Have a Knight's Tour?" Mathematics Magazine 64(5)，325 至 332 页。
28. Idury, R. M. 和 Waterman, M. S. (1995). "A New Algorithm for DNA Sequence Assembly." Journal of Computational Biology 2(2)，291 至 306 页。
29. Pevzner, P. A., Tang, H. 和 Waterman, M. S. (2001). "An Eulerian Path Approach to DNA Fragment Assembly." Proceedings of the National Academy of Sciences 98(17)，9748 至 9753 页。
30. Björklund, A. (2014). "Determinant Sums for Undirected Hamiltonicity." SIAM Journal on Computing 43(1)，280 至 299 页。
31. Diestel, R. (2017). Graph Theory，第 5 版。Graduate Texts in Mathematics 173。柏林：Springer。