什么是“周游世界游戏”

1859年，英国的大数学家哈密顿（1805—1865）提出了一个著名的数学游戏——“周游世界”。他把正十二面体（图1）上的20个顶点，看成是当时世界上最出名的20个大城市，要求游戏者从某一个城市出发，沿着各条棱前进，把所有的城市（也就是20个顶点）无遗漏地全部通过，并且不允许重复。问：是否能够找到这样一条路线？

图1

正十二面体中有12个面，20个顶点，30条棱，又是一个空间图形，情况比较复杂，所以不容易求解。

但是，经过仔细观察与思考，你会发现，在这个游戏中，每条棱的长短是无关紧要的，即使将棱弄弯曲了，对问题的解决也没有什么妨碍。关键在于两个顶点之间是否有条棱将它们连接起来，这是最重要的事情。为此我们可以把背后那个面剪破、摊平，而不改变任意两个顶点之间的是否连接的关系。设想每个面都是用橡皮薄膜做的，摊平以后可以得到如图2所示的图形，这样问题解决起来就比较容易了。

由于每个顶点在正十二面体中的地位是相同的，所以可将图2中任何一个顶点作为初始顶点。现在不妨将图2中编号为1的那个顶点作为初始顶点。在图2中直观上看起来，20个顶点被分成3层。里层与外层中各有5个顶点，夹层中有10个顶点。从顶点1到顶点7，挨着顺序前进，就用尽了里层所有顶点以及夹层中的2个顶点。从顶点7到顶点8，就由里层转到了夹层，再挨着顺序到顶点15，这样就用尽了夹层中其余的顶点。从顶点15到顶点16，就由夹层转到外层。从顶点16挨着顺序到顶点20，就用尽了所有外层顶点。最后从顶点20到顶点1，就得到一条所要求的一条路线，完成了“周游世界”游戏，这个趣味数学问题得到了圆满解决。

图2

值得注意的是，虽然在这个数学游戏中我们与图形打了交道，但着眼点与欧氏几何是有很大区别的。这里我们最关心的是图形中有哪些顶点，这些顶点之间是否有“棱”或“边”将它们连接起来，其他的因素如“形状”、“面积”、“体积”，甚至连接顶点的边的长短、弯曲等等都是无关紧要的。这样的图形在数学中干脆就叫做“图”。

图论是专门研究图及其应用的一个现代数学分支。“周游世界”游戏在图论中具有重要的意义。在这个游戏中，要求在图上找到这样一条路线，它沿着边经过图上每个顶点一次且仅仅一次，最后起点与终点重合。为了纪念哈密顿，图论中将具有这种性质的图称为哈密顿图。一个图是哈密顿图的充分必要条件是什么？这个问题称为哈密顿问题，是当代图论中尚未完全解决的重要问题之一。这方面的研究在运筹学、计算机科学以及编码理论中有许多应用。

图3

很多少年朋友喜爱足球运动。最后，我们利用足球图，请你自己动手试一试，做一个类似的“周游世界”游戏。在下面3个足球图（图3）上，各找出一条路线：从某个顶点出发，沿着那些路线（直的、曲的都可以），经过每个顶点一次，且仅仅一次，最后回到初始顶点。这3个足球图都是哈密顿图，你是应该能够找到符合要求的路线的。