书城教材教辅必玩的数学闯关
10611300000055

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

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

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

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

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

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