第601章 “可平面图”论问题
Jacob Holm和Eva Rotenberg是两位计算机科学家，2019年10月，他们在arXiv上提交了一篇论文，论文的主题与数学中的“可平面图”（planar graph）概念有关。
Jacob Holm对Eva Rotenberg说：“我们现在要被迫研究图论的问题了。”
Eva Rotenberg说：“为什么要研究图论？”
Jacob说：“有三间房子，以及三种公用设施，有水、气、电。它问的是：如果每一间房子都要与三种公用设施相连，是否可以让所有的这些连线互相之间不交叉。”
Eva说：“让我画画。”Eva画了很久，不管这里的线如何去绕，到无法让线之间交叉。
Jacob说：“说明有些图，是不能在平面内无交叉表达出来的。”
Eva说：“这是个有意思的问题，我们应该研究这个东西，这是个了不起的发现。我们需要寻找一个问题图，是否会无交叉相连，或者相连了快速画出路线来。”
Jacob说：“或者是改变了节点后，是否能够可平面无交叉，能的话如何快速画出来。”
Eva突然想到了，电子设备中的微小电路板，都需要考虑到线路的交叉问题。以电路板为例，如果图形不是可平面的，就意味着两根线交叉，电路板出现了短路。他说：“当一个可平面图被随机的添加了额外的连线时，是否有算法可以快速判断新形成的图形是否仍然维持了可平面性呢？”
Jacob说：“没错，这就是问题的精髓。”
终于在1996年，4名计算机科学家发表了一种测试图形的可平面性的算法。可惜的是，这个算法所涉及到的计算步骤非常多，其步骤数量基本上与图形中的节点数的平方根成正比。作为一个算法，这并不算很高效。而自这一算法被发表以来，一直没能得到改进。直到现在。
Holm和Rotenberg在翻阅他们去年发表的论文时，惊喜地发现论文中含有一个可得出更好算法的重要见解，解决了改进这个算法时会遇到的一个主要障碍。今年6月，他们提交了一份新的论文，文中详细描述了一种方法，能指数级地改进检验图形的可平面性的算法。
在检查图形的平面性方面，新算法的步骤数量正比于图形中的节点数的对数的立方，这比1996年的算法要快得多。他们利用了可平面图的这样一个特点，即一个相同的可平面图有着多种不同的绘制方式，在不同的绘制方式中，点与点之间的连接仍是相同的，但连线之间的相对位置却有可能不同。
现在，如果添加一条连接平面图中的两个节点的额外的连线，比如让这节点1和6相连，那么假如从A开始，它需要连续翻转两次才能使节点1和6的相连不与其他任何边交叉。
Holm和Rotenberg发现，在2019年的论文中涵盖了这样一个信息，利用这个信息，可以为可平面图找到“更好的绘制方法”。这里的更好的绘制方法，指的是当有额外的连线被添加到图中时，“更好”的绘制方法能比其他绘制方法提供更优的起始位置，使得当额外的连线被添加之后，只需经过很少步骤的翻转，就能维持图形的可平面性不被破坏的状况。
当他们很快意识到这一点，就产生了一个概念上的非常简单的新算法。
新的算法在每次执行一次翻转时，都会生成两种结果中的一种：要么是算法找到了一种能维持可平面性的添加所需边的方法；要么是算法得出结论发现没有可以添加所需边的方法，于是在下一个翻转时撤销上一个翻转。
新的方法或许目前来看还不够完美，对于大多数解决现实问题的应用程序来说，它所需要的步骤还是没有最小化，但这已经是在朝着解决这类问题的最佳可能算法靠近的一个重大突破。
喜欢数学心请大家收藏：(m.dzzzw.com)数学心读者中文更新速度全网最快。