这个停滞了20多年的数学问题，终于有了新突破

本文来自微信公众号：原理（ID：principia1687），作者：佐佑，题图来自：视觉中国

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的相连不与其他任何边交叉。

素材来源：Quanta Magazine

Holm和Rotenberg发现，在2019年的论文中涵盖了这样一个信息，利用这个信息，可以为可平面图找到“更好的绘制方法”。这里的更好的绘制方法，指的是当有额外的连线被添加到图中时，“更好”的绘制方法能比其他绘制方法提供更优的起始位置，使得当额外的连线被添加之后，只需经过很少步骤的翻转，就能维持图形的可平面性不被破坏的状况。

当他们很快意识到这一点，就产生了一个概念上的非常简单的新算法。新的算法在每次执行一次翻转时，都会生成两种结果中的一种：要么是算法找到了一种能维持可平面性的添加所需边的方法；要么是算法得出结论发现没有可以添加所需边的方法，于是在下一个翻转时撤销上一个翻转。这对于从事该领域研究的科学家来说，是一个重大的启发。

三

新的方法或许目前来看还不够完美，对于大多数解决现实问题的应用程序来说，它所需要的步骤还是没有最小化，但这已经是在朝着解决这类问题的最佳可能算法靠近的一个重大突破。对Holm和Rotenberg来说，能够精进算法固然重要，但其中所涉及的新洞见更让他们激动，他们相信基于这种理解，很快会有新的概念出现。并最终应用到实际问题中。

而这一概念的发现，也让许多研究人员开始期待，或许许多构成了谜题答案的要素已经存在，它们正在一堆陈旧的论文中静静等待能发现它们的人。何时会出现更快的算法，没有人知道，但全新的突破可能就藏在意想不到的惊喜中。

参考来源：

https://arxiv.org/abs/1910.09005

https://www.quantamagazine.org/a-new-algorithm-for-graph-crossings-hiding-in-plain-sight-20200915/

https://www.science.ku.dk/english/press/news/2020/researchers-got-busy-after-nearly-allowing-the-solution-to-a-math-conundrum-from-the-1980s-slip-away/

https://dl.acm.org/doi/10.1145/3357713.3384249

本文来自微信公众号：原理（ID：principia1687），作者：佐佑