第662章 「可平面圖」論問題

JacobHolm和EvaRotenberg是兩位計算機科學家，2019年10月，他們在arXiv上提交了一篇論文，論文的主題與數學中的「可平面圖」（planargraph）概念有關。

JacobHolm對EvaRotenberg說：「我們現在要被迫研究圖論的問題了。」

EvaRotenberg說：「為什麼要研究圖論？」

Jacob說：「有三間房子，以及三種公用設施，有水、氣、電。它問的是：如果每一間房子都要與三種公用設施相連，是否可以讓所有的這些連線互相之間不交叉。」

Eva說：「讓我畫畫。」Eva畫了很久，不管這裡的線如何去繞，到無法讓線之間交叉。

Jacob說：「說明有些圖，是不能在平面內無交叉表達出來的。」

Eva說：「這是個有意思的問題，我們應該研究這個東西，這是個了不起的發現。我們需要尋找一個問題圖，是否會無交叉相連，或者相連了快速畫出路線來。」

Jacob說：「或者是改變了節點后，是否能夠可平面無交叉，能的話如何快速畫出來。」

Eva突然想到了，電子設備中的微小電路板，都需要考慮到線路的交叉問題。以電路板為例，如果圖形不是可平面的，就意味著兩根線交叉，電路板出現了短路。他說：「當一個可平面圖被隨機的添加了額外的連線時，是否有演算法可以快速判斷新形成的圖形是否仍然維持了可平面性呢？」

Jacob說：「沒錯，這就是問題的精髓。」

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

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

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

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

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

當他們很快意識到這一點，就產生了一個概念上的非常簡單的新演算法。

新的演算法在每次執行一次翻轉時，都會生成兩種結果中的一種：要麼是演算法找到了一種能維持可平面性的添加所需邊的方法；要麼是演算法得出結論發現沒有可以添加所需邊的方法，於是在下一個翻轉時撤銷上一個翻轉。

新的方法或許目前來看還不夠完美，對於大多數解決現實問題的應用程序來說，它所需要的步驟還是沒有最小化，但這已經是在朝著解決這類問題的最佳可能演算法靠近的一個重大突破。

。