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

英国数学家哈密顿

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

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

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

哈密顿回路

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

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

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

【微博士】柯克曼女生问题

英国人柯克曼在1850年提出了这样的问题：一位女教师每天会带领着15名女生散步。这位老师按照3人一行的排列方式，将女学生们排列成5行。在同一行中的3个女生，称呼彼此为同伴。问：能否制订出一个连续7天的散步计划，使每一位女生和其他的同学只同伴一次？

【微问题】你去公园游览的时候能不能试着自己设计一个最佳参观路线？

【关键词】图论　回路　一笔画