哈密顿圈：从“环游世界”到最难的数学谜题

一场19世纪的“环球旅行”

想象你生活在1857年的伦敦。著名数学家、物理学家威廉·罗文·哈密顿（William Rowan Hamilton）刚刚推出了一款新奇的智力游戏，名为“周游世界游戏” (Icosian Game)。

这个游戏由一个正十二面体的木质模型组成。十二面体的20个顶点被标记为当时著名的城市（如伦敦、巴黎、东京等），而棱边则代表连接城市的航线。你的任务非常明确：从某个城市出发，沿着棱边行进，必须恰好经过每一个城市各一次，最后回到起点。

你不妨在脑海中构建这样一个物理图像：你手里拎着一个装满20个图钉的袋子，每到一个城市就钉下一个。如果你能在不拔掉任何图钉、也不经过任何已有图钉城市的情况下，用一根长线把所有城市连成一个闭环回到出发地，你就赢了。

什么是哈密顿圈

在图论中，这种“不重复地遍历所有顶点”的闭合路径被赋予了哈密顿的名字。

为了理解其直观意义，你可以把自己想象成一名快递员。你需要去全市所有的客户家送快递，但你希望设计的路线能精准地在每家门口停一次，既不走冤枉路（不重复），也不漏掉任何人（全覆盖），最后还能回到快递站。这条完美的闭环路线就是哈密顿圈。

为了让你更直观地感受这种挑战，尝试在下方的正十二面体模型（投影图）中，看看你能否不重复地走遍所有点并回到原点。

实际上，在这个高度对称的结构中，一种可行的路径序列如下（按字母顺序连接）：

.

为什么它比欧拉路径更难

很多学生在学习图论时，容易把哈密顿圈与“柯尼斯堡七桥问题”中的欧拉路径 (Eulerian Path) 搞混。既然“走遍每一条边”（欧拉路径）只需要数一数每个顶点的度数就能判定，这不可避免地导致了一个疑问：为什么仅仅把目标从“边”换成“顶点”，难度就会发生天壤之别？

• 欧拉路径（遍历边）：只要图是连通的，且奇数度的顶点不超过2个，就一定存在。这是一种“局部判定”法，只需要看一眼每个节点的情况。
• 哈密顿圈（遍历顶点）：它要求的是“全局协调”。到目前为止，数学家们还没能找到任何一个像欧拉路径那样简单、普适的度数判定准则。

这种“不可知性”使哈密顿圈成为了计算机科学中著名的“NP完全问题”。

这意味着，随着节点数量的增加，寻找这条路径的计算量会呈指数级爆炸。如果一个 20 个城市的网络能在 1 秒内算完，一个 100 个城市的网络可能需要运行几万年。这正是克雷数学研究所悬赏百万美元的“P vs NP”问题的核心战场之一。

寻找圈子的“保底协议”

虽然我们无法快速判定任意图是否存在哈密顿圈，但数学家们找到了一些“保底协议”——即满足某些条件时，图一定存在哈密顿圈。

在 1952 年，数学家加布里埃尔·狄拉克（Gabriel Dirac）提出了一个著名的充分条件：

这给了我们一个直观的启发：只要城市之间的交通足够发达（每个城市连接了至少一半的其他城市），那么“环球旅行”就总能实现。

值得注意的是，正十二面体并不满足狄拉克定理的条件（它有 20 个顶点，但每个顶点只有 3 条边，），但它依然拥有哈密顿圈。这再次证明了哈密顿圈问题的诡谲：有些路虽然没有“保底协议”撑腰，但奇迹依然存在。

参考文献

[1] Patrick Honner. "How a 19th-Century Game Helped Spawn Modern Graph Theory", Quanta Magazine, 2020.

[2] Bondy, J. A., & Murty, U. S. R. "Graph Theory with Applications", 1976.