你知道什么是“周游世界”游戏吗

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

正十二面体中有12个面，20个顶点，30条棱，又是一个空间图形，所以求解比较困难。在七桥问题中我们已经知道，顶点的位置及边的长短、曲直对问题的解决没有影响。所以我们可以把背后那个面剪破摊平，可以得到如图2所示的图形，这样问题就比较容易了。

由于每个顶点在正十二面体中的地位是相同的，所以可将图2中任何一点作为初始顶点。不妨选1号点，按照图中所示的点的顺序，从1号到20号从里层到外层，就能完成“周游世界”的游戏。

“周游世界”游戏在图论中具有重要的意义，具有这种性质的图被称为哈密顿图。一个图成为哈密顿图的充分必要条件是什么呢?这个问题称为哈密顿问题，是当代图论中尚未解决的重要问题之一。这方面的研究在运筹学、计算机科学以及编码理论中有许多应用。

有兴趣的话，大家可以自己动手试一试，利用足球上的顶点和棱，做一个类似的“周游世界”游戏。

关键词：哈密顿图 哈密顿问题