困擾大家60年的“圖形填充遊戲”，這三個數學家的答案會是最終謎底嗎？_風聞

點面結合構成了一個個圖形，關於這些圖我們可以想出各種問題，比如：如何讓多個簡單的小圖副本完美地重構（覆蓋）一張大圖？

**這就像你面對家裏廚房的地板發問：我可以用商店中任意一種同尺寸的瓷磚完全覆蓋整個地板嗎？**在現實生活中，不可能每一款瓷磚都適用於你家的廚房，一般來説必須組合不同形狀的瓷磚（或者切割）才能覆蓋整個地板。但是在特定的圖形世界中，這個想法或許可以達成。

1963年，一位名叫格哈德·林格爾（Gerhard Ringel）**的德國數學家提出了一個大膽的猜想：一些特定的圖形總是可以被n個小圖副本完美覆蓋。**對此，他指出：任給一棵具有 n 條邊的樹 T，都能在2n+1階完全圖K2n+1中找到不重合且同構於T的2n+1個子圖（即2n+1個T副本可以被完美地填充到K2n+1中）

一個擁有n(大於3且為奇數)個頂點的完整圖，總能被（n-1）/2個同構不重合的子圖完美覆蓋

為了證明林格爾的猜想，人們發展與利用了多種數學工具，比如：概率方法、正則引理等，但似乎總有漏洞。

近日，蘇黎世瑞士聯邦技術學院的本尼·蘇達科夫（Benny Sudakov）、伯明翰大學的理查德·蒙哥馬利（Richard Montgomery）和倫敦伯克貝克大學的亞歷克斯·波克洛夫斯基（Alexey Pokrovskiy）三名數學家發表的相關論文或許給證明這個困惑了人們將近60年的數學猜想帶來了希望。

01****林格爾猜想是什麼？完整圖形和樹圖

發佈這個猜想，林格爾提出了一些基本概念：首先，從大於3的任何奇數個點開始（這個數字必須是奇數才能使推測合理），在它們之間繪製邊，以便每個點都與其他所有點相連，這樣創建的圖形稱為完整圖形。

一個擁有5個點的完整圖形

接下來，我們看一下另一種類型的圖。它可以是一條簡單的路徑；也可以有其他分支，當然我們還可以在分支上繼續添加分支，只要它不包含任何閉環，就可以根據需要使圖更復雜，我們把這種類型的圖稱為樹。

簡單或複雜的樹圖

林格爾猜想是關於完整圖和樹之間的關係。

他説：首先，想象一個包含2n+1個點的完整圖形。然後思考使用n+1個點可以製作多少棵樹，事實上可以做出很多種完全不同的樹。

現在，選擇其中一棵樹並將其放置，以使樹的每個邊與完整圖形中的邊重合。然後，將同一棵樹的另一個副本放在整個圖形的不同部分上。

**林格爾預測，假設你從正確的地方開始放置並持續這個動作，那麼你將能夠完美地複製出上面的完整圖形。**這意味着完整圖形中的每個邊都被樹的每條邊覆蓋，且樹的任何副本都不會相互重疊（如下圖）。

完美複製

如何理解這個猜想呢？

當已知一個完整圖，如果它的點數為n（大於3且為奇數），那麼該圖肯定可以被n個子圖完美覆蓋，且子圖的形狀為具有(n-1)/2條邊的樹圖；反之，如果已知一個具有m條邊的樹圖，那麼用2m+1個該樹圖可以構成一個具有2m+1個點的完整圖。

林格爾的猜想似乎適用於11、21、31個點的完整圖形，但是隨着點越來越多，完整圖形逐漸複雜起來，這個猜想還成立嗎？

**這個範圍雖然很廣泛，但數學界有理由相信林格爾的猜想可能是正確的。**最直接的理由是：具有2n+1個點的完整圖形中的邊數總是可以被具有n+1個點的樹中的邊數等分。

事實上，數學家們很快找到了另一條證據，表明該猜想至少是可行的。

02****旋轉方法帶來新問題：如何放置第一顆樹

林格爾發佈猜想後不久，加拿大一位名叫安東·科齊格（Anton Kotzig）的斯洛伐克裔數學家使用此示例做出了比林格爾更大膽的預測。林格爾表示，每個具有2n+1個點的完整圖都可以由具有n條邊的任何樹圖平鋪；科齊格則推測，平鋪總是可以旋轉的方式完成。

如果想探究他們的猜想，簡單的星形樹圖是或許是一個不錯的起點。

最簡單的樹圖之一是星形：有一箇中心點，其他邊從中心輻射出來。但它不同於典型的星形圖，因為邊不必在點周圍均勻排列，只需從同一位置向外延伸，除了在中央點之外，不能在其他任何地方相交。

簡單的星形樹圖

確實，數學家很快觀察到，具有n+1個點的星形樹始終可以完美地複製到具有2n+1個點的完整圖形。單單這個事實就很有趣，但是如何證明卻讓數學家們犯了難。

舉一個簡單的案例。從11個點開始，將這些點排列成一個圓形，然後將每個點與其他每個點相連以形成一個完整圖（如下圖）。

相連之後的完整圖

然後再設想一個星形樹:1箇中心點，5條邊從該點延伸出去（如下圖）。

星形樹

接下來，放置星形以使中心點與完整圖中的一個點對齊，然後開始旋轉，這時你將擁有一個新的星形樹副本，該副本與完整圖形上的另外一部分重合。

持續旋轉星形樹，一次旋轉一個點的位置。當回到起點時，就像林格爾預測的那樣，你將得到一個與之前完整圖形一模一樣且沒有任何部分重疊的圖（如下圖）。

旋轉後完全重合

但是這個實驗依然有漏洞：星形圖是規則的，因此無論如何放置都無關緊要。但是大多數樹並不是，假如樹上有許多不同長度的不同分支，那麼只有正確放置它們才能使旋轉方法起作用，且此時如何放置第一步將至關重要。

幸運的是，數學家們最終找到了一個直觀的色彩方法。

03****通過顏色編碼找到樹的彩虹副本

顏色編碼在生活中有很多應用，比如它可以幫助區分日常工作的緊急程度、完成情況等。事實證明，這也是找出如何放置第一顆樹的有效方法。

如何進行顏色編碼呢？首先，想象圍繞一個圓排列的11個點的完整圖，編碼規則是根據距離（通過一條邊連接的兩個點之間的距離）進行上色。

假設如果兩個點彼此相鄰，則它們之間的距離為1，如果兩個點中間相隔一個點，則它們之間的距離為2（如下圖）。

如何計算距離

現在根據距離為完整圖的邊上色。距離為1的所有點的邊都塗成相同的顏色，例如藍色。距離為2的點的所有邊也都標記相同的顏色，例如黃色。繼續這樣操作，以使連接點的邊距相等的距離都標記相同的顏色。

結果證明，在具有2n+1個點的完整圖形上，你需要n種不同的顏色來執行該方案（如下圖）。

上色後的完整圖形

給完整圖形按顏色編碼後，如何找到放置第一顆樹的方法呢？

這個想法是**將樹定位，使其覆蓋每種顏色的一個邊，且不覆蓋任何顏色兩次（如下圖），數學家們將此位置稱為樹的彩虹副本。**對於一個具有2n+1個點的完整圖來説，由於着色需要n種顏色，並且其彩虹副本總是具有n+1個點的樹圖，因此我們知道彩虹副本是存在的。

上色後出現樹的彩虹副本

至此，數學家們就可以通過證明每個具有2n+1個點的完整圖包含具有n條邊的樹的彩虹副本，來證明林格爾的猜想。如果彩虹副本始終存在，則完全覆蓋完整圖始終有效。

花費了40多年的時間，三位數學家證明了這個事實。

04****如何完美放置是證明猜想的最後一步

如果有一個包含11（2n+1=11,則n=5）個點，且已用5種不同顏色上色的完整圖形，以及一個包含6個點、5條邊的樹圖，你的任務是在完整圖中找到樹的彩虹副本。

隨着工作不斷進行，放置下一個樹的工作越來越難，因此你可能需要提前做好計劃。**三個數學家從一開始就知道，找到彩虹副本或許不難，難得是如何放置。**就好像打包過行李箱，眾所周知，我們應該從最困難、最複雜的物體開始，比如手提箱、自行車等，因為無論如何，你最後總能找到縫隙塞進一些小東西，數學家們也採納了這一哲學。

想象一棵有11條邊的樹，其中6條邊的點集中在一起。剩下的大部分是單一的形狀，像卷鬚一樣（如下圖）。

類似卷鬚一樣的複雜樹圖

最難放置的部分是具有6條邊的點。因此，數學家將它與樹的其餘部分分開，然後將其首先放置。這就像你要把一張牀移到樓上必須得先拆卸再進行組裝一樣。

通過這樣做，他們確保了整個圖形中的剩餘空間是隨機的。

這三位數學家的研究表明，一旦嵌入了樹圖最難的部分，且完整圖的剩餘空間是隨機的，那麼總有一種方法可以嵌入樹的其餘部分以獲得彩虹副本。

除此之外，三位數學家的研究結果給類似未解決的問題提供了新思路。或許適當調整一下還可以解決更多未知猜想。