?

　　Jacob Holm和Eva Rotenberg是兩位計算機科學家，去年10月，他們在arXiv上提交了一篇論文，論文的主題與數(shù)學中的“可平面圖”（planar graph）概念有關。在論文提交后不久，他們突然意識到，這篇論文中所涵蓋的內容，包含了一個很了不起的洞見，可以為改進一個算法問題解決主要障礙。

計算機科學家Eva Rotenberg（左）和Jacob Holm（右）在2019年提交的一篇論文，成為了他們破解一個數(shù)學謎題的文章的指引。| 圖片來源：University of Copenhagen

　　近幾十年來，數(shù)學家和計算機科學家就一直在努力尋找一個可以用最快速度解決一個圖論問題的算法，我們可以用一個腦筋急轉彎問題來解釋這個圖論問題討論的是什么。

　　1913年，《斯特蘭德雜志》（The Strand Magazine）上刊登了一個叫做“三個公用設施問題（three-utilities problem）”的腦筋急轉彎，問題中有三間房子，以及三種公用設施——水、氣、電。它問的是：如果每一間房子都要與三種公用設施相連，是否可以讓所有的這些連線互相之間不交叉。

三個房子與三種公用設施相連的問題。

　　用不了多久你就會發(fā)現(xiàn)，這個問題中的要求是不可能做到的。

　　如果用簡單的數(shù)學語言來加以說明，可以說這個問題的本質就與圖論中的可平面圖概念有關。在圖論中，圖形是由連線和節(jié)點構成的集合，它們可以用來表示許多事物，從社交網(wǎng)絡到道路系統(tǒng)，再到電路板上的電子連接等等。

由連線與節(jié)點組成的圖形的例子。

　　因此，“三個公用設施問題”在實質上討論的是，對一個圖形來說，如何在連線不交叉的情況下將節(jié)點連接；以及如何利用算法，來確保當對一個圖形被更改后，仍然能保持可平面性。

　　這種可平面性具有很強的應用意義，無論是建造巨大的道路網(wǎng)絡，還是設計電子設備中的微小電路板，都需要考慮到線路的交叉問題。以電路板為例，如果圖形不是可平面的，就意味著兩根線交叉，電路板出現(xiàn)了短路。那么，當一個可平面圖被隨機的添加了額外的連線時，是否有算法可以快速判斷新形成的圖形是否仍然維持了可平面性呢？

左：連線不會交叉的可平面圖。右：連線會交叉的非可平面圖。

　　這正是許多計算機科學家希望能找到的算法，能幫助他們快速地確定當一個圖形在進行了所需的修改之后，是否仍然保持了可平面性；且這種算法可以在當圖形只有部分被改變時，并不需要對圖形的每個部分都進行檢查。

　　終于在1996年，4名計算機科學家發(fā)表了一種測試圖形的可平面性的算法。可惜的是，這個算法所涉及到的計算步驟非常多，其步驟數(shù)量基本上與圖形中的節(jié)點數(shù)的平方根成正比。作為一個算法，這并不算很高效。而自這一算法被發(fā)表以來，一直沒能得到改進。直到現(xiàn)在。

　　Holm和Rotenberg在翻閱他們去年發(fā)表的論文時，驚喜地發(fā)現(xiàn)論文中含有一個可得出更好算法的重要見解，解決了改進這個算法時會遇到的一個主要障礙。今年6月，他們提交了一份新的論文，文中詳細描述了一種方法，能指數(shù)級地改進檢驗圖形的可平面性的算法。

　　在檢查圖形的平面性方面，新算法的步驟數(shù)量正比于圖形中的節(jié)點數(shù)的對數(shù)的立方，這比1996年的算法要快得多。他們利用了可平面圖的這樣一個特點，即一個相同的可平面圖有著多種不同的繪制方式，在不同的繪制方式中，點與點之間的連接仍是相同的，但連線之間的相對位置卻有可能不同。

　　以下圖為例，圖A、B、C都是相同的可平面圖，圖A和B可以通過翻轉由節(jié)點1、2、3構成的三角形而獲得；圖C可以通過繞節(jié)點4、5的連接翻轉圖B的上半部分而生成。

素材來源：Quanta Magazine

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

素材來源：Quanta Magazine

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

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

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

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



關注【深圳科普】微信公眾號，在對話框：
回復【最新活動】，了解近期科普活動
回復【科普行】，了解最新深圳科普行活動
回復【研學營】，了解最新科普研學營
回復【科普課堂】，了解最新科普課堂
回復【科普書籍】，了解最新科普書籍
回復【團體定制】，了解最新團體定制活動
回復【科普基地】，了解深圳科普基地詳情
回復【觀鳥知識】，學習觀鳥相關科普知識