什么是哈密顿周游世界问题

英国数学家哈密顿

英国数学家哈密顿以其发明了四元数著称于世。我们已经知道，四元数的乘法不满足交换律。但很少有人了解，哈密顿还发明了另一种乘法不满足交换律的代数运算，他称为“二十点演算”。这个演算的三个主要符号是$ι，κ，λ$，它们满足方程：$ι^2=1，κ^3=1，λ^5=ικ$。

其中$ικ≠κι$，否则就会有$λ^6=1$，从而得到$λ=1$。哈密顿为什么要给这种演算起这么个名字呢?

原来，哈密顿发现，一连串这种符号的推导，可以解释成在十二面体的顶点之间作移动。而十二面体的顶点个数是20，所以他就以“二十点演算”来命名这种新的代数运算。他还以此为基础，设计了一个同名游戏。这个“二十点游戏”的目标，相当于在一幅平面上的十二面体图中，找出一条通过每个顶点仅一次并且回到出发点的路线，如图所示。

哈密顿回路

1857年，哈密顿将他的这个游戏公布出来，并以25英镑的价格卖给了一个玩具商。1859年，该玩具商又将十二面体的顶点标上20个重要的城市名： 布鲁塞尔、广州、德里$\cdots\cdots$桑给巴尔，冠以“周游世界”的名字推向市场。可想而知，这个游戏并没有获得商业上的成功。然而它却留下了“哈密顿周游世界问题”这个名称，所寻找的这样一条路线则被称为“哈密顿回路”。

后来人们才知道，其实早于哈密顿一年，另一位英国数学家柯克曼已经讨论了更为一般的问题:哪些多面体上可以找到通过每个顶点仅一次的回路？他证明了如果一个多面体有奇数个顶点，而每个面有偶数条边，那么就不存在这样的回路。

你可能已经注意到了，在一笔画问题和哈密顿周游世界问题之间，似乎有着某种共性。一笔画问题是要求不重复地走遍图中所有的线；周游世界问题则是要求不重复地走遍图中所有的点。但这两个问题却是极其不同的。对于任意给出的一个图，利用欧拉的结论可以很容易判断能否一笔画出，但现在还没有找到判断是否存在哈密顿回路的有效方法，事实上这是一个极其困难的问题。