哈密顿圈: 环游世界的路线存在吗？
作者 | 陈旭瑾
1859 年爱尔兰数学家威廉·哈密顿(William Hamilton) 提出一个“环游世界” 游戏: 把一个正十二面体的二十个顶点看作世界上著名的二十个城市 (图1), 要求游戏者找出一条路线, 沿着正十二面体的棱边访问每个城市恰好一次后回到出发点, 即环游世界. 这个游戏在欧洲风靡一时,哈密顿还以 25 个金币的高价把这个游戏的版权卖给了一个玩具商.
图1 环游世界
环游世界游戏相当于要求寻找图2所示平面图中一个经过所有顶点的圈. 这样的圈被称为哈密顿圈 (Hamilton cycle). 图2是否有哈密顿圈呢？你不妨也和 19 世纪的人们一起来尝试回答一下这个问题.
图2 正十二面体的平面表示
哈密顿给出的答案如图3所示, 蓝色的粗线条给出了图2的一个哈密顿圈, 展示了如何在哈密顿所设计的游戏中环游世界.
图 3 哈密顿圈
像图2这样具有哈密顿圈的图被称为哈密顿图. 显然不是所有的图都有哈密顿圈. 树不含圈, 所以它显然不是哈密顿图. 但对于有的图,就不是那么明显地能够看出它一定没有哈密顿图了. 比如, 彼得森图(图4), 你能证明它不是哈密顿图吗？
图4 有两个洞的曲面, 欧拉示性数为 −2
从正十二面体图和彼得森图我们可以看到,无论是要找到哈密顿图的哈密顿圈, 还是要证明非哈密顿图一定没有哈密顿圈, 都得费一些周章. 这引发了下述的哈密顿问题.
哈密顿问题 (Hamilton problem) 判断给定图是不是哈密顿图.
运筹学、计算机科学和编码理论中的很多问题都可化归为哈密顿问题, 因而它引起国际上广泛的关注和研究.
哈密顿问题属于一个被记作 NP 的问题类. 在 20 世纪 70 年代,哈密顿问题被证明是 NP 完全的; 也就是说: 如果能找到判定哈密顿圈是否存在的快速算法, 那么就证明了 NP 这一问题类等同于它的一个被称为 P 的子类, 从而解决了 “NP 是否等于 P” 这一千禧年大奖难题(Millennium Prize Problems, 指的是由美国的克雷数学研究所于 2000年公布的当今最具挑战性的七个数学难题, 每解破一题可获奖金 100 万美元. 迄今为止, 在七个问题中, 庞加莱猜想是唯一被解决的).
然而, 目前绝大多数科学家相信 NP 不等于 P, 只是还没有找到办法证明. 实际上对于顶点数不到 100 的图,即使利用当今最快的算法和最先进的计算机也可能需要几百年才能确定这个图里是否存在哈密顿圈. 除非 NP = P, 否则对于一般图, 不可能会有判定哈密顿圈是否存在的简洁通用的充分必要条件. 于是数学家们寻求保证哈密顿圈存在的充分条件.
针对简单图 (没有环边, 并且任何两个顶点之间至多有一条边的图),挪威数学家奥斯丁 • 欧尔 (Øystein Ore) 提出了著名的欧尔条件.
欧尔定理 (1960 年) 任给简单图, 如果它满足欧尔条件——每一对非相邻顶点的度和都大于等于图的顶点数, 那么该图是哈密顿图.图5满足欧尔条件, 所以它有哈密顿圈 (蓝边显示). 欧尔不仅证明了上面的定理, 而且它的证明告诉我们如何在满足欧尔条件的图中找到一个哈密顿圈.
图5 满足欧尔条件的哈密顿图
但是仍有很多哈密顿图不满足欧尔条件, 比如图6, 它有 9 个顶点,但是在最外层有不相邻的 3 度顶点. 实际上, 这个图的哈密顿圈 (蓝色粗边显示) 并不那么容易找. 但它离运用欧尔条件也仅一步之遥.
欧尔证明的关键步骤说明, 如果在度和至少是顶点数的非相邻顶点间加一条边使得新图有哈密顿圈的话, 那么原图也有哈密顿圈. 于是, 著名图论学家约翰·邦迪 (John Bondy) 和瓦茨拉夫·奇瓦塔尔 (VáclavChvátal) 提出闭包这一有力工具, 对欧尔定理进行了推广. 设 G 是具有n 个顶点的简单图. 图 G 的哈密顿闭包(Hamilton closure) 是从 G 开始, 迭代地加入边连接其中度和至少为 n 的非相邻顶点对 (直到不存在这样的对为止) 而获得的图.
图6 不满足欧尔条件的哈密顿图
邦迪–奇瓦塔尔定理 (1976) 一个简单图是哈密顿图当且仅当它的哈密顿闭包是哈密顿图.对于图6, 当依次加边连接它的非相邻点对 (1, 2), (1, 3), (1, 4),(1, 5), (1,6), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6), (5, 7), (6, 7) 时, 它们的度和在当时至少是顶点数 9. 所以这个加边过程产生的是图 32 的哈密顿闭包, 如图7所示. 这是完全图 K 9 , 显然它有哈密顿圈. 所以根据邦迪–奇瓦塔尔定理, 图6是哈密顿图.
图7 哈密顿闭包
本文摘编自《认识数学.1》第5章“图论就在我们身边”5.7 节“哈密顿圈: 环游世界的路线存在吗？”作者：陈旭瑾。
《认识数学.1》
主编：席南华
责任编辑：李欣
本书是《认识数学》系列数学科普书的第一卷，由10篇文章组成，作者均是中国科学院数学院系统科学研究院的科研人员。在本卷中，您可以找到这些问题的答案：数学里面最有名的问题黎曼猜想是什么，它的由来是怎样的？什么是克莱因瓶，卡拉比-丘流形?凭声音能听出鼓的形状吗？三体问题是什么？哥尼斯堡七桥问题，环游世界的路线存在吗？地图染色用四色够了么？孤立波、孤立子、可积系统是什么？女士品茶问题——她能够品尝出奶茶的调制过程是先加奶还是先加茶？星座能预测诺贝尔文学奖么？
☟左右滑动查看更多
Slide for more photos