第六百五十八章 林格爾猜想（圖論）(第1/2頁)

樹圖是隻有分支沒有閉合的圖，完全圖是每個節點都兩兩相連的滿圖。

格哈德·林格爾（Gerhard Ringel）想用多個相同樹圖去填充完全圖。如何讓多個簡單的小圖副本完美地重構（覆蓋）一張大圖？

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

解釋一下，就是首先，想象一個包含2n+1個點的完整圖形。然後思考使用n+1個點可以製作多少棵樹，事實上可以做出很多種完全不同的樹。現在，選擇其中一棵樹並將其放置，以使樹的每個邊與完整圖形中的邊重合。然後，將同一棵樹的另一個副本放在整個圖形的不同部分上。林格爾預測，假設你從正確的地方開始放置並持續這個動作，那麼你將能夠完美地複製出上面的完整圖形。這意味著完整圖形中的每個邊都被樹的每條邊覆蓋，且樹的任何副本都不會相互重疊。

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

科齊格則推測，平鋪總是可以旋轉的方式完成。

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

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

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

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

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

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

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

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

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

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

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

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

這個想法是將樹定位，使其覆蓋每種顏色的一個邊