數(shù)學(xué)家證明，某種常見類型的圖必定包含一條恰好訪問每個點(diǎn)一次的路線。

圖源：Nico Roper / Quanta Magazine

作者：Leila Sloman 量子雜志特約記者 2024-6-7

譯者：zzllrr小樂（數(shù)學(xué)科普公眾號）2024-6-9

隨著數(shù)學(xué)抽象的發(fā)展，圖是其中最簡單的抽象物。在平面上散布一堆點(diǎn)。用直線連接其中一些點(diǎn)。這就是圖的全部內(nèi)容。然而，它們非常強(qiáng)大。它們可用于解決各種各樣的問題，從模擬大腦中的神經(jīng)元到安排路上跑的送貨卡車的路線。在數(shù)學(xué)中，它們可被用來對于稱為群的重要代數(shù)對象進(jìn)行分類，描述紐結(jié)以及用于無數(shù)的其它地方。

圖論的核心問題之一是找到在返回起點(diǎn)之前恰好訪問圖中每個點(diǎn)一次的路線。這些路線被稱為哈密頓環(huán)路、哈密頓回路（Hamiltonian cycle），以19世紀(jì)數(shù)學(xué)家威廉·羅文·哈密頓（又譯哈密爾頓，漢密爾頓，William Rowan Hamilton，1805 - 1865）的名字命名。

許多圖都有這樣的環(huán)路。但在其他情況下，無論你多么努力地尋找哈密頓環(huán)路，你最終都會陷入困境：也許你會被困在圖的一個孤立的氣泡中，無法訪問所有的點(diǎn)，或者你可能會被迫回溯你的步驟。

圖源：Merrill Sherman / Quanta Magazine

對于像上面這樣的小圖，通過反復(fù)試驗來確定哈密頓環(huán)路是否存在相對容易。在這個例子中，不存在這種環(huán)路。

但是，如果你開始考慮包含數(shù)百個、數(shù)千個或數(shù)百萬個點(diǎn)和線的圖，那么這項任務(wù)就會變得非常困難。沒有已知的有效算法來確定給定的大圖是否包含環(huán)路。如果有人找到這樣的算法，它將為數(shù)學(xué)和計算機(jī)科學(xué)中的大量問題提供解決方案 https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9 。（這樣的算法還可以解決剩下的六個千禧年獎問題 https://www.claymath.org/millennium/p-vs-np/ 之一，從克萊數(shù)學(xué)研究所獲得一百萬美元的凈收入。）

前兩個圖描繪了兩個哈密頓環(huán)路，而在第三個圖上，不可能找到這樣的環(huán)路。

因此，一些數(shù)學(xué)家沒有試圖產(chǎn)生一種尋找哈密頓環(huán)路的通用算法，而是專注于證明特定類型的圖包含此類環(huán)路的更簡單的問題。2002年，特拉維夫大學(xué)的邁克爾·克里夫列維奇（Michael Krivelevich）和現(xiàn)供職于瑞士蘇黎世聯(lián)邦理工學(xué)院的本尼·蘇達(dá)科夫（Benny Sudakov）猜測 https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.10065 ，一類重要的圖稱為擴(kuò)展圖（expander graph），都包含哈密頓環(huán)路。今年2月，蘇達(dá)科夫與其他四位數(shù)學(xué)家一起，成功地證明了他在二十多年前首次提出的猜想 https://arxiv.org/abs/2402.06603 。

尋找環(huán)路

克里夫列維奇和蘇達(dá)科夫的猜想打斷了一連串的嘗試，試圖解開保證有哈密頓環(huán)路的條件。早在1952年，丹麥數(shù)學(xué)家加布里埃爾·狄拉克（Gabriel Dirac，1925 - 1984，是著名物理學(xué)家保羅·狄拉克Paul Dirac的繼子）就證明了每個具有n個點(diǎn)或節(jié)點(diǎn)的圖，其中每個節(jié)點(diǎn)至少連接到n/2個其他的點(diǎn)，都包含一個哈密頓環(huán)路。但這種情形下含有很多直線（通常稱為邊）。多年來，數(shù)學(xué)家們一直在努力減少哈密頓圖必須具有的邊數(shù)。1976年，匈牙利數(shù)學(xué)家拉喬斯·波薩（Lajos Pósa，1947 -）證明了通過隨機(jī)繪制邊構(gòu)建的某些圖幾乎可以保證包含哈密頓環(huán)路 https://www.ceid.upatras.gr/webpages/courses/pithmeth/hamilton-cycles.pdf 。到2001年，克里夫列維奇和蘇達(dá)科夫，和另外兩位同事 https://people.math.ethz.ch/~sudakovb/reghigh.pdf ，以及另一個競爭小組 https://www.math.cmu.edu/~af1p/Texfiles/conham.pdf ，已經(jīng)證明了關(guān)于另一類圖的類似結(jié)果。

克里夫列維奇和蘇達(dá)科夫認(rèn)為他們知道為什么隨機(jī)繪制的圖可能包含哈密頓環(huán)路。隨機(jī)圖有兩個關(guān)鍵性質(zhì)。第一個性質(zhì)涉及檢查圖中兩個大型、不重疊的節(jié)點(diǎn)組時會發(fā)生什么。在隨機(jī)圖中，很可能至少有一條邊連接組。

第二個性質(zhì)涉及一小組節(jié)點(diǎn)。取一小組節(jié)點(diǎn)，并將其稱為 A。現(xiàn)在通過添加連接到 A 中某一點(diǎn)的每個節(jié)點(diǎn)來擴(kuò)大它，數(shù)學(xué)家稱這個更大的組為 A 的“鄰域”。在隨機(jī)圖中，A 的鄰域可能遠(yuǎn)大于 A 本身。所以數(shù)學(xué)家說A“擴(kuò)展”到一個大鄰域。

具有這兩個性質(zhì)的圖（其中大型節(jié)點(diǎn)組可能共享一條邊，以及小型節(jié)點(diǎn)組擴(kuò)展為更大的組）稱為擴(kuò)展圖（expander graph）。如果 A 的鄰域是 A的c倍，則該圖稱為一種c-擴(kuò)展圖。

盡管許多隨機(jī)圖最終成為擴(kuò)圖，但擴(kuò)展圖不一定是隨機(jī)的。相反，擴(kuò)展圖“具有隨機(jī)圖的性質(zhì)，而不需要隨機(jī)性，”劍橋大學(xué)的湯姆·古爾（Tom Gur）說。

由于它們必須滿足的條件，擴(kuò)展圖是高度互連的，這意味著即使邊不多，你也可以通過相對較少的步驟從圖的一部分到達(dá)另一部分。古爾說，擴(kuò)展圖體現(xiàn)了連通性和稀疏性之間的緊張關(guān)系。

擴(kuò)展圖的早期工作受到神經(jīng)元網(wǎng)絡(luò)的啟發(fā)，這些圖也出現(xiàn)在其他領(lǐng)域。一些大型在線社交網(wǎng)絡(luò)是擴(kuò)展圖，擴(kuò)展圖可用于構(gòu)建高效的糾錯碼 https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf ，提高隨機(jī)算法的準(zhǔn)確性。

在他們2002年的論文中，克里夫列維奇和蘇達(dá)科夫證明了某些類型的擴(kuò)展圖具有哈密頓環(huán)路 https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=90605361a8c0a33901c2742eb749952e44361455 。他們認(rèn)為擴(kuò)展圖更普遍地也有這樣的環(huán)路，但他們無法證明這一點(diǎn)。“我們堅信這個猜想應(yīng)該是真的，我們也非常堅信（證明）這個猜想將非常非常困難，”克里夫列維奇說。

在接下來的二十年里，蘇達(dá)科夫偶爾會回到這個問題上，但沒有取得太大進(jìn)展。這種情況在 2023年3月發(fā)生了變化，當(dāng)時蘇達(dá)科夫、他的學(xué)生戴維·蒙哈·科雷亞（David Munhá Correia）和帕紹大學(xué)的史蒂芬·格洛克（Stefan Glock）對2002年的結(jié)果進(jìn)行了改進(jìn) https://arxiv.org/abs/2303.05356 ，證明一類稍大的擴(kuò)展圖必定具有哈密頓環(huán)路。“我們產(chǎn)生了許多想法，并在某個時候意識到它們可以以正確的方式組合，”蘇達(dá)科夫說。“David和Stefan一直對這個問題非常熱情，不愿意放棄。

接下來的一個月，華威大學(xué)的理查德·蒙哥馬利（Richard Montgomery）和倫敦大學(xué)學(xué)院的阿列克謝·波克羅夫斯基（Alexey Pokrovskiy）來到蘇黎世拜訪蘇達(dá)科夫。蒙哥馬利在2010年代初在劍橋大學(xué)攻讀博士學(xué)位時曾試圖證明蘇達(dá)科夫和克里夫列維奇的猜想，但他放棄了，因為他認(rèn)為自己沒有合適的工具來解決這個問題。隨著蘇達(dá)科夫、蒙哈·科雷亞和格洛克最近取得的進(jìn)展，蒙哥馬利認(rèn)為值得再試一次。蒙哥馬利說：“我建議繼續(xù)努力，但不一定有任何強(qiáng)烈的感覺，我們會取得任何重大進(jìn)展。”

在接下來的幾周里，蒙哥馬利、蘇達(dá)科夫和波克羅夫斯基提出了一個策略。他們使用一種稱為波薩Pósa旋轉(zhuǎn)的技術(shù)來收集長路徑的集合，希望最終將這些路徑連接成哈密頓環(huán)路。蒙哥馬利回到沃里克的家中時并沒有帶回證明，但帶著新發(fā)現(xiàn)的樂觀情緒。“我們有一種感覺，最終，不管怎樣，我們應(yīng)該有正確的想法來獲得結(jié)果，”蘇達(dá)科夫說。

在2023年底，穆哈·科雷亞和蘇達(dá)科夫最近畢業(yè)的學(xué)生內(nèi)馬尼亞·德拉加尼奇（Nemanja Dragani?）告訴蘇達(dá)科夫，他們也一直在研究這個猜想。穆哈·科雷亞和德拉加尼奇有一個想法，即使用一種稱為排序網(wǎng)絡(luò)的裝置將路徑連接到哈密頓環(huán)路中，他們在 2023年11月的一篇論文中 https://arxiv.org/abs/2311.03185 撞見了這個想法。“我們坐在一起，意識到所有這些想法都可以放在一起，也許可以解決問題，”穆哈·科雷亞說。

排序網(wǎng)絡(luò)（sorting network）是包含兩個匹配集 A 和 B 的圖。排序網(wǎng)絡(luò)的結(jié)構(gòu)使得無論你如何將 A 中的點(diǎn)與 B 中的點(diǎn)配對，都可以找到將 A 中的每個點(diǎn)與其在 B 中的相應(yīng)點(diǎn)連接起來的不相交路徑。“你告訴我你如何進(jìn)入，你告訴我你想如何退出，”蘇達(dá)科夫解釋道。“排序網(wǎng)絡(luò)有一個性質(zhì)，即從每個頂點(diǎn)到目的地都有一條路徑。”

11月的論文包含了一個證明，即特定類型的擴(kuò)展圖必須包含排序網(wǎng)絡(luò)。德拉加尼奇、蒙哥馬利、穆哈·科雷亞、波克羅夫斯基和蘇達(dá)科夫意識到，如果他們能夠?qū)⑴判蚓W(wǎng)絡(luò)與Pósa旋轉(zhuǎn)結(jié)合起來，他們將能夠證明這個猜想。他們使用2023年11月論文的技術(shù)來證明擴(kuò)展圖也必須包含排序網(wǎng)絡(luò)。然后，通過將集合 A 和 B 作為他們使用Pósa 旋轉(zhuǎn)創(chuàng)建的路徑的端點(diǎn)，他們發(fā)現(xiàn)可以將他們的長路徑集合連接到哈密頓環(huán)路中。“我們明確了證明所需的所有關(guān)鍵概念，”蘇達(dá)科夫說。

到二月份，該小組已經(jīng)寫完了他們的論文。它不僅證明了2002年克里夫列維奇和蘇達(dá)科夫的最初猜想，該猜想對擴(kuò)展圖使用了更狹義的定義，而且證明了更強(qiáng)大的東西：任何c-擴(kuò)展圖，只要c足夠大，都有一個哈密頓環(huán)路。他們的方法還產(chǎn)生了一個實際的哈密頓環(huán)路，而不是抽象地證明一個哈密頓環(huán)路的存在。蘇達(dá)科夫?qū)⒉莅皋D(zhuǎn)發(fā)給克里夫列維奇。“我相當(dāng)懷疑我們能否在有生之年看到它得到解決，”克里夫列維奇回應(yīng)道。

新的證明解決了關(guān)于哈密頓環(huán)路的幾個問題。例如，它證明了某些類型的圖與群有關(guān)，稱為凱萊圖（Cayley graph），必定具有哈密頓環(huán)路。但這不是最終結(jié)論。數(shù)學(xué)家仍然可以嘗試找到c的最低邊界，即擴(kuò)展因子（expansion factor），并可能證明更廣泛的一類圖，稱為堅韌圖（tough graph），必定包含環(huán)路。（蘇達(dá)科夫說，盡管這是一個愿望，但對它的證明“還遠(yuǎn)未達(dá)到”，他警告說，“甚至沒有充分的證據(jù)顯示這個猜想是正確的。）

沒有參與這項工作的古爾說，它建立了“兩個對計算機(jī)科學(xué)至關(guān)重要的對象之間的基本聯(lián)系”。他說，這種聯(lián)系將導(dǎo)致重要的應(yīng)用。“我不知道它會采取什么形式。看來這注定是有用的。”

參考資料

https://www.quantamagazine.org/in-highly-connected-networks-theres-always-a-loop-20240607/

https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9

https://www.claymath.org/millennium/p-vs-np/

https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.10065

https://arxiv.org/abs/2402.06603

https://www.ceid.upatras.gr/webpages/courses/pithmeth/hamilton-cycles.pdf

https://people.math.ethz.ch/~sudakovb/reghigh.pdf

https://www.math.cmu.edu/~af1p/Texfiles/conham.pdf

https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf

https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=90605361a8c0a33901c2742eb749952e44361455

https://arxiv.org/abs/2303.05356

https://arxiv.org/abs/2311.03185

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數(shù)學(xué)

更加

易學(xué)易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點(diǎn)贊、在看、在聽

收藏、分享、轉(zhuǎn)載、投稿

查看原始文章出處

點(diǎn)擊zzllrr小樂

公眾號主頁

右上角

數(shù)學(xué)科普不迷路！