停滯了20多年一個數學問題，終於有了新突

來源：原理

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的上半部分而生成。

現在，如果添加一條連接平面圖中的兩個節點的額外的連線，比如讓這節點1和6相連，那麼假如從A開始，它需要連續翻轉兩次才能使節點1和6的相連不與其他任何邊交叉。

Holm和Rotenberg發現，在2019年的論文中涵蓋了這樣一個信息，利用這個信息，可以爲可平面圖找到“更好的繪製方法”。這裏的更好的繪製方法，指的是當有額外的連線被添加到圖中時，“更好”的繪製方法能比其他繪製方法提供更優的起始位置，使得當額外的連線被添加之後，只需經過很少步驟的翻轉，就能維持圖形的可平面性不被破壞的狀況。

當他們很快意識到這一點，就產生了一個概念上的非常簡單的新算法。新的算法在每次執行一次翻轉時，都會生成兩種結果中的一種：要麼是算法找到了一種能維持可平面性的添加所需邊的方法；要麼是算法得出結論發現沒有可以添加所需邊的方法，於是在下一個翻轉時撤銷上一個翻轉。這對於從事該領域研究的科學家來說，是一個重大的啓發。

新的方法或許目前來看還不夠完美，對於大多數解決現實問題的應用程序來說，它所需要的步驟還是沒有最小化，但這已經是在朝着解決這類問題的最佳可能算法靠近的一個重大突破。對Holm和Rotenberg來說，能夠精進算法固然重要，但其中所涉及的新洞見更讓他們激動，他們相信基於這種理解，很快會有新的概念出現。並最終應用到實際問題中。

而這一概念的發現，也讓許多研究人員開始期待，或許許多構成了謎題答案的要素已經存在，它們正在一堆陳舊的論文中靜靜等待能發現它們的人。何時會出現更快的算法，沒有人知道，但全新的突破可能就藏在意想不到的驚喜中。