|
Jacob Holm和Eva Rotenberg是两位计较机科学家，去年10月，他们在arXiv上提交了一篇论文，论文的主题与数学中的“可平面图”观念有关。在论文提交后不久，他们溘然意识到，这篇论文中所涵盖的内容，包括了一个很了不得的洞见，可觉得改造一个算法问题办理主要障碍。
近几十年来，数学家和计较机科学家就一直在尽力寻找一个可以用最快速度办理一个图论问题的算法，我们可以用一个头脑急转弯问题来表明这个图论问题接头的是什么。 1913年，《斯特兰德杂志》上登载了一个叫做“三个公用设施问题”的头脑急转弯，问题中有三间屋子，以及三种公用设施——水、气、电。它问的是：假如每一间屋子都要与三种公用设施相连，是否可以让所有的这些连线相互之间不交错。
用不了多久你就会发明，这个问题中的要求是不行能做到的。 假如用简朴的数学语言来加以说明，可以说这个问题的本质就与图论中的可平面图观念有关。在图论中，图形是由连线和节点组成的荟萃，它们可以用来暗示很多事物，从社交网络到阶梯系统，再到电路板上的电子毗连等等。
因此，“三个公用设施问题”在实质上接头的是，对一个图形来说，如安在连线不交错的环境下将节点毗连；以及如何操作算法，来确保当对一个图形被变动后，仍然能保持可平面性。 这种可平面性具有很强的应用意义，无论是制作庞大的阶梯网络，照旧设计电子设备中的微小电路板，都需要思量到线路的交错问题。以电路板为例，假如图形不是可平面的，就意味着两根线交错，电路板呈现了短路。那么，当一个可平面图被随机的添加了特另外连线时，是否有算法可以快速判定新形成的图形是否仍然维持了可平面性呢？
这正是很多计较机科学家但愿能找到的算法，能辅佐他们快速地确定当一个图形在举办了所需的修改之后，是否仍然保持了可平面性；且这种算法可以在当图形只有部门被改变时，并不需要对图形的每个部门都举办查抄。 终于在1996年，4名计较机科学家颁发了一种测试图形的可平面性的算法。惋惜的是，这个算法所涉及到的计较步调很是多，其步调数量根基上与图形中的节点数的平方根成正比。作为一个算法，这并不算很高效。而自这一算法被颁发以来，一直没能获得改造。直到此刻。 Holm和Rotenberg在翻阅他们去年颁发的论文时，惊喜地发明论文中含有一个可得出更好算法的重要看法，办理了改造这个算法时会碰着的一个主要障碍。本年6月，他们提交了一份新的论文，文中具体描写了一种要领，能指数级地改造检讨图形的可平面性的算法。 在查抄图形的平面性方面，新算法的步调数量正比于图形中的节点数的对数的立方，这比1996年的算法要快得多。他们操作了可平面图的这样一个特点，即一个沟通的可平面图有着多种差异的绘制方法，在差异的绘制方法中，点与点之间的毗连仍是沟通的，但连线之间的相对位置却有大概差异。 以下图为例，图A、B、C都是沟通的可平面图，图A和B可以通过翻转由节点1、2、3组成的三角形而得到；图C可以通过绕节点4、5的毗连翻转图B的上半部门而生成。
此刻，假如添加一条毗连平面图中的两个节点的特另外连线，好比让这节点1和6相连，那么如果从A开始，它需要持续翻转两次才气使节点1和6的相连不与其他任何边交错。
|
