Jacob Holm和Eva Rotenberg是两位计算机科学家,去年10月,他们在arXiv上提交了一篇论文,论文的主题与数学中的“可平面图”(planar graph)概念有关。在论文提交后不久,他们突然意识到,这篇论文中所涵盖的内容,包含了一个很了不起的洞见,可以为改进一个算法问题解决主要障碍。
计算机科学家Eva Rotenberg(左)和Jacob Holm(右)在2019年提交的一篇论文,成为了他们破解一个数学谜题的文章的指引。| 图片来源:University of Copenhagen
近几十年来,数学家和计算机科学家就一直在努力寻找一个可以用最快速度解决一个图论问题的算法,我们可以用一个脑筋急转弯问题来解释这个图论问题讨论的是什么。
1913年,《斯特兰德杂志》(The Strand Magazine)上刊登了一个叫做“三个公用设施问题(three-utilities problem)”的脑筋急转弯,问题中有三间房子,以及三种公用设施——水、气、电。它问的是:如果每一间房子都要与三种公用设施相连,是否可以让所有的这些连线互相之间不交叉。
三个房子与三种公用设施相连的问题。
用不了多久你就会发现,这个问题中的要求是不可能做到的。
如果用简单的数学语言来加以说明,可以说这个问题的本质就与图论中的可平面图概念有关。在图论中,图形是由连线和节点构成的集合,它们可以用来表示许多事物,从社交网络到道路系统,再到电路板上的电子连接等等。
由连线与节点组成的图形的例子。
因此,“三个公用设施问题”在实质上讨论的是,对一个图形来说,如何在连线不交叉的情况下将节点连接;以及如何利用算法,来确保当对一个图形被更改后,仍然能保持可平面性。
这种可平面性具有很强的应用意义,无论是建造巨大的道路网络,还是设计电子设备中的微小电路板,都需要考虑到线路的交叉问题。以电路板为例,如果图形不是可平面的,就意味着两根线交叉,电路板出现了短路。那么,当一个可平面图被随机的添加了额外的连线时,是否有算法可以快速判断新形成的图形是否仍然维持了可平面性呢?
左:连线不会交叉的可平面图。右:连线会交叉的非可平面图。
这正是许多计算机科学家希望能找到的算法,能帮助他们快速地确定当一个图形在进行了所需的修改之后,是否仍然保持了可平面性;且这种算法可以在当图形只有部分被改变时,并不需要对图形的每个部分都进行检查。
终于在1996年,4名计算机科学家发表了一种测试图形的可平面性的算法。可惜的是,这个算法所涉及到的计算步骤非常多,其步骤数量基本上与图形中的节点数的平方根成正比。作为一个算法,这并不算很高效。而自这一算法被发表以来,一直没能得到改进。直到现在。
Holm和Rotenberg在翻阅他们去年发表的论文时,惊喜地发现论文中含有一个可得出更好算法的重要见解,解决了改进这个算法时会遇到的一个主要障碍。今年6月,他们提交了一份新的论文,文中详细描述了一种方法,能指数级地改进检验图形的可平面性的算法。
在检查图形的平面性方面,新算法的步骤数量正比于图形中的节点数的对数的立方,这比1996年的算法要快得多。他们利用了可平面图的这样一个特点,即一个相同的可平面图有着多种不同的绘制方式,在不同的绘制方式中,点与点之间的连接仍是相同的,但连线之间的相对位置却有可能不同。
以下图为例,图A、B、C都是相同的可平面图,图A和B可以通过翻转由节点1、2、3构成的三角形而获得;图C可以通过绕节点4、5的连接翻转图B的上半部分而生成。
素材来源:Quanta Magazine
现在,如果添加一条连接平面图中的两个节点的额外的连线,比如让这节点1和6相连,那么假如从A开始,它需要连续翻转两次才能使节点1和6的相连不与其他任何边交叉。