哈密顿路径与回路详解

画五个点围成一圈,把每个点与它的两个邻点相连,您就能绕一圈经过每个点各一次并回到原处:这就是哈密顿回路。再添几条边或去掉几条,问题就会变得出奇地难。一个图是否有这样的回路,是至今没有任何计算机能对每个图都快速回答的著名问题之一。

一个压平的十二面体,20 个角用辅音字母标注,一条经过全部角的哈密顿回路以亮色线条画出,并在搜索回退处有一条红色虚线边
一个压平的十二面体,20 个角用辅音字母标注,一条经过全部角的哈密顿回路以亮色线条画出,并在搜索回退处有一条红色虚线边

每个顶点一次

图是一组称为顶点的点,由称为边的线相连。哈密顿路径沿边行走,恰好经过每个顶点一次;哈密顿回路还会回到出发点,因此它的边数与顶点数相同。有哈密顿回路的图称为哈密顿图。验证一条给定路线很容易:数一数顶点,再看每一步。难的是找到一条,或者证明一条都没有,因为顶点可能被访问的次序数按 n! 增长,20 个顶点时已达 2.4 × 10¹⁸。

哈密顿的二十面体游戏

发现四元数的爱尔兰数学家威廉·罗万·哈密顿在 1857 年设计了二十面体游戏。棋盘上是压平到平面上的十二面体,20 个角用辅音字母标注,主要任务是把编号 1 到 20 的木钉插到各角上,使相邻编号以及 20 与 1 都由边相连。哈密顿把版权以 25 英镑卖给了伦敦玩具商 John Jaques and Son,该游戏于 1859 年上市,销量不佳。这道谜题有 30 个解,这是把回路不论起点和方向都只算一次的结果。问题本身并不新鲜:托马斯·柯克曼在 1855 年寄给皇家学会的一篇论文中就问过哪些多面体有经过全部角的回路,并给出了一个没有这种回路的例子。

马步巡游

马步巡游移动国际象棋中的马,使它恰好在每个格子上落子一次:这是在以格子为顶点、以马的走法为边的图中的一条哈密顿路径。闭合巡游的终点距起点正好是一步马的距离,也就是一条哈密顿回路。一千多年前棋手们就在出这类题目,欧拉在 1759 年的一篇论文中研究过它们。1823 年 H. C. 冯·Warnsdorff 提出总是走向后续走法最少的格子;这条简单规则通常能走完 8 × 8 棋盘而不回头。马总是换格色,所以闭合巡游需要浅色格与深色格一样多,这就排除了格数为奇数的棋盘。艾伦·施文克在 1991 年精确给出了哪些矩形棋盘有闭合巡游;在正方形棋盘中,边长为 6 及以上偶数的都有。标准棋盘有 13,267,364,410,532 条闭合巡游,由布兰登·麦凯在 1997 年数出。

没有哈密顿回路的图

证明不存在回路最快的办法是计数论证。如果顶点能用两种颜色着色,使每条边都连接不同颜色,那么回路必须交替着色,两色顶点数要一样多;5 × 5 网格一色 13 个、另一色 12 个,所以没有哈密顿回路。割点一旦去掉就会把图分开,回路必须两次经过它;度数为 1 的顶点则根本无法被穿过。有些图躲开了所有这类论证。尤利乌斯·彼得森在 1898 年发表的彼得森图有 10 个度数为 3 的顶点且没有哈密顿回路,然而删去任何一个顶点,剩下的图就有了;它是最小的这类亚哈密顿图。赫歇尔图以 1862 年撰文讨论二十面体游戏的亚历山大·斯图尔特·赫歇尔命名,有 11 个顶点和 18 条边,是一个有九个四边形面的多面体的图。角数更少的多面体都不缺哈密顿回路。1884 年彼得·格思里·泰特猜想,每个角上有三条棱的多面体都有哈密顿回路;W. T. 塔特在 1946 年找到了一个 46 个顶点的反例。

能保证存在的条件

图的边一多,哈密顿回路就必然存在。加布里埃尔·狄拉克在 1952 年证明:若图有 n ≥ 3 个顶点且每个顶点的度数至少为 n/2,则它有哈密顿回路;厄于斯坦·奥尔在 1960 年把条件放宽:只要任意两个不相邻顶点的度数之和至少为 n 即可。两个条件都只在一个方向上成立。由 100 个顶点组成的简单环处处度数为 2,远低于 50,却本身就是一条哈密顿回路。这就是总体图景:既有充分条件,也有失败的理由,两者之间是一大片只有搜索才能判定的图。

为什么没有已知的快速判定方法

判断一个图是否有哈密顿回路是 NP 完全问题,它是理查德·卡普 1972 年所列 21 个问题之一。能对每个图快速求解它的方法,也会快速解决成千上万的其他问题,并解决 P 与 NP 之争。与把每条边走一次的欧拉路径相比,反差十分鲜明:欧拉在 1736 年证明,数一数奇数度顶点就能立刻判定那个问题。目前针对哈密顿回路的最好精确算法仍需指数时间。对顶点全部子集做动态规划的方法由理查德·贝尔曼以及迈克尔·赫尔德与理查德·卡普在 1962 年提出,约需 n² × 2ⁿ 步;安德烈亚斯·比约克隆德 2010 年的随机算法约需 1.657ⁿ 步。实际中,剪枝良好的回溯可以处理几十个顶点的图,而寻找最短哈密顿回路的旅行商问题,正是同一问题的带权版本。

格雷码与超立方体

把 0 到 7 写成 3 位编码,当两个编码恰好相差一位时就把它们相连:结果就是立方体的图。其中的一条哈密顿回路,例如 000、001、011、010、110、111、101、100,把八个编码排成一列,使每个编码与前一个只差一位。这样的序列就是格雷码,得名于贝尔实验室的弗兰克·格雷,他在 1947 年提交的一项专利中描述了它。每个超立方体都有一条:把少一位的编码写出来,再把同一列表倒着写一遍,然后在前半部分前面加 0、后半部分前面加 1。旋转编码器使用格雷码,使得在两个位置之间读取的数值误差永远不超过一步。立方体有 6 条哈密顿回路,4 位超立方体有 1,344 条。

动手探索

打开哈密顿路径探索器,亲自试试哈密顿的谜题,虚线圆环会显示接下来可以走到哪里;也可以切换到「搜索」,看回溯如何工作:路径不断生长,红色虚线标出它回退的地方,柱状图按路径长度统计节点数。开关死路检查、连通性检查和 Warnsdorff 顺序,比较各自需要多少节点,数出小图的全部回路,或者画出自己的图,看看哪些快速判定适用。

常见问题

有欧拉回路的图也一定是哈密顿图吗,反过来呢?

两者互不蕴含。蝴蝶结是共用一个顶点的两个三角形,因为每个度数都是偶数,所以有欧拉回路,但没有哈密顿回路,因为共用的顶点必须被经过两次。完全图 K₄ 有哈密顿回路,但四个顶点的度数都是 3,所以它没有欧拉回路。

计算机不能干脆把所有次序都试一遍吗?

只有小图可以。n 个顶点有 n! 种次序,20 个顶点约为 2.4 × 10¹⁸ 种。回溯要好得多,因为它只沿边行走,一旦走不通就放弃当前的部分路径:它约用 1,400 步就能找出 20 个顶点的十二面体的全部 30 条回路。但对某些图来说,部分路径的数量仍呈指数增长,而且没有已知方法能对每个图都避免这一点。

哈密顿路径问题比回路问题更容易吗?

不,两者都是 NP 完全的。彼此可以相互转化:添加一个与所有原顶点相连的新顶点,那么原图有哈密顿路径,当且仅当新图有哈密顿回路。反过来,把某个顶点复制一份(邻点相同),再给原顶点接上一个新的端点、给副本接上另一个,回路问题就变成了路径问题。

为什么 5 × 5 棋盘上的马步巡游必须从角的颜色出发?

25 个格子中有 13 个是角的颜色,12 个是另一种颜色,而马每走一步都换色。走遍 25 个格子的巡游颜色交替,因此起点和终点都在格子较多的那种颜色上。本应用能找出 5 × 5 棋盘全部 1,728 条开放巡游,若把一条巡游与它的逆序算作一条则是 864 条,而且每一条都在角色的格子上起止。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

打开哈密顿路径探索器