第五百三十九章 “可平面图”论问题（2/2）

这正是许多计算机科学家希望能找到的算法，能帮助他们快速地确定当一个图形在进行了所需的修改之后，是否仍然保持了可平面性；且这种算法可以在当图形只有部分被改变时，并不需要对图形的每个部分都进行检查。

终于在1996年，4名计算机科学家发表了一种测试图形的可平面性的算法。可惜的是，这个算法所涉及到的计算步骤非常多，其步骤数量基本上与图形中的节点数的平方根成正比。作为一个算法，这并不算很高效。而自这一算法被发表以来，一直没能得到改进。直到现在。

holm和rotenberg在翻阅他们去年发表的论文时，惊喜地发现论文中含有一个可得出更好算法的重要见解，解决了改进这个算法时会遇到的一个主要障碍。今年6月，他们提交了一份新的论文，文中详细描述了一种方法，能指数级地改进检验图形的可平面性的算法。

在检查图形的平面性方面，新算法的步骤数量正比于图形中的节点数的对数的立方，这比1996年的算法要快得多。他们利用了可平面图的这样一个特点，即一个相同的可平面图有着多种不同的绘制方式，在不同的绘制方式中，点与点之间的连接仍是相同的，但连线之间的相对位置却有可能不同。

现在，如果添加一条连接平面图中的两个节点的额外的连线，比如让这节点1和6相连，那么假如从a开始，它需要连续翻转两次才能使节点1和6的相连不与其他任何边交叉。

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

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

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

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