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

jacobholm和evarotenberg是两位计算机科学家，2019年10月，他们在arxiv上提交了一篇论文，论文的主题与数学中的“可平面图”（planargraph）概念有关。在论文提交后不久，他们突然意识到，这篇论文中所涵盖的内容，包含了一个很了不起的洞见，可以为改进一个算法问题解决主要障碍。

计算机科学家evarotenberg和jacobholm在2019年提交的一篇论文，成为了他们破解一个数学谜题的文章的指引。

近几十年来，数学家和计算机科学家就一直在努力寻找一个可以用最快速度解决一个图论问题的算法，我们可以用一个脑筋急转弯问题来解释这个图论问题讨论的是什么。

1913年，《斯特兰德杂志》（thestrandmagazine）上刊登了一个叫做“三个公用设施问题（three-utilitiesproblem）”的脑筋急转弯，问题中有三间房子，以及三种公用设施——水、气、电。它问的是：如果每一间房子都要与三种公用设施相连，是否可以让所有的这些连线互相之间不交叉。

三个房子与三种公用设施相连的问题。

用不了多久你就会发现，这个问题中的要求是不可能做到的。

如果用简单的数学语言来加以说明，可以说这个问题的本质就与图论中的可平面图概念有关。在图论中，图形是由连线和节点构成的集合，它们可以用来表示许多事物，从社交网络到道路系统，再到电路板上的电子连接等等。

由连线与节点组成的图形的例子。

因此，“三个公用设施问题”在实质上讨论的是，对一个图形来说，如何在连线不交叉的情况下将节点连接；以及如何利用算法，来确保当对一个图形被更改后，仍然能保持可平面性。

这种可平面性具有很强的应用意义，无论是建造巨大的道路网络，还是设计电子设备中的微小电路板，都需要考虑到线路的交叉问题。以电路板为例，如果图形不是可平面的，就意味着两根线交叉，电路板出现了短路。那么，当一个可平面图被随机的添加了额外的连线时，是否有算法可以快速判断新形成的图形是否仍然维持了可平面性呢？