Euler's Eyes
2026-10-27
周游世界游戏与哈密顿回路
1856 年，仍在研究非交换代数的哈密顿发明了二十面体演算：三个符号 $\iota$、$\kappa$ 和 $\lambda$，服从规则
$$\iota^2 = 1, \qquad \kappa^3 = 1, \qquad \lambda^5 = 1, \qquad \lambda = \iota\kappa.$$今天我们会说，它们生成了正二十面体（有二十个三角形面的立体）的旋转群。1857 年，哈密顿在英国科学促进会于都柏林举行的会议上介绍了这种演算，并注意到它描述的是沿正十二面体（有十二个五边形面和二十个顶点的立体）的棱行走的路径。
谜题
为了让这个想法流行起来，哈密顿把十二面体压平画在一块板上，在二十个顶点处开了孔，每个孔标上一个城市的名字，另配二十个编了号的木钉。挑战是：从一个城市出发，只沿着棱走，把其他每个城市恰好访问一次，再回到出发点。1859 年，他以 25 英镑把版权卖给了伦敦的游戏制造商约翰·贾克斯父子公司。这个游戏以“周游世界游戏”（The Icosian Game）的名字出售，还有一个叫“旅行者的十二面体”的袖珍版，但在商业上失败了：只要有点耐心，基本的挑战几分钟就能解决。
试一试。字母是哈密顿用来给城市命名的辅音字母：
欧拉解决了，哈密顿没有
每个顶点恰好经过一次再回到起点的路线，今天称为哈密顿回路。这个问题看起来像是柯尼斯堡七桥问题的表亲，在那个问题里欧拉想把每条边恰好走一次。但两者非常不同。对于边，欧拉在 1736 年给出了一个简单的判据：只要看每个顶点连出多少条边。对于顶点，没有人知道简单的判据。1972 年，理查德·卡普把哈密顿回路问题列入他的 NP 完全问题清单：谁能为它找到一个快速方法，谁就有了解决成千上万其他难题的快速方法，还能从克莱研究所赢得一百万美元。
它最著名的亲戚是旅行商问题：在一张地图的所有哈密顿回路中，哪一条最短？它出现在送货路线、电路板钻孔和 DNA 测序中。
练习：数一数棱
在正十二面体中，20 个顶点中的每一个都连着 3 条棱。共有多少条棱？一条哈密顿回路用了其中多少条？
按顶点数，共有 $20 \times 3 = 60$ 个棱端，每条棱有两个端点：$60 / 2 = 30$ 条棱。一条哈密顿回路经过 20 个顶点再回来，用了 20 条棱；其余 10 条没有用到。
练习：立方体上的回路
立方体的顶点可以写成从 $000$ 到 $111$ 的三位二进制序列，只差一位的两个顶点相连。找出一条哈密顿回路。
一个解：$000 \to 001 \to 011 \to 010 \to 110 \to 111 \to 101 \to 100 \to 000$。每一步只改变一位。这个序列就是三位格雷码，正因为每一步只改变一个数字，它被用在位置传感器和纠错中。
来源： William Rowan Hamilton, “Memorandum respecting a new System of Roots of Unity”, Philosophical Magazine（1856）· Norman L. Biggs、E. Keith Lloyd 与 Robin J. Wilson, Graph Theory 1736–1936（1976）· Richard M. Karp, “Reducibility among combinatorial problems”（1972）· 圣保罗大学 Matemateca 的周游世界游戏。
威廉·罗恩·哈密顿的全部主题 · ← 凯莱–哈密顿定理 · 威廉·罗恩·哈密顿的遗产 →
图片来源.