第六百五十八章 林格爾猜想（圖論）

　　樹圖是只有分支沒有閉合的圖，完全圖是每個節(jié)點(diǎn)都兩兩相連的滿圖。

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

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

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

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

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

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

　　最簡單的樹圖之一是星形：有一個中心點(diǎn)，其他邊從中心輻射出來。但它不同于典型的星形圖，因?yàn)檫叢槐卦邳c(diǎn)周圍均勻排列，只需從同一位置向外延伸，除了在中央點(diǎn)之外，不能在其他任何地方相交。

　　確實(shí)，數(shù)學(xué)家很快觀察到，具有n+1個點(diǎn)的星形樹始終可以完美地復(fù)制到具有2n+1個點(diǎn)的完整圖形。單單這個事實(shí)就很有趣，但是如何證明卻讓數(shù)學(xué)家們犯了難。

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

　　幸運(yùn)的是，數(shù)學(xué)家們最終找到了一個直觀的色彩方法。

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

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

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

　　假設(shè)如果兩個點(diǎn)彼此相鄰，則它們之間的距離為1，如果兩個點(diǎn)中間相隔一個點(diǎn)，則它們之間的距離為2。

　　現(xiàn)在根據(jù)距離為完整圖的邊上色。距離為1的所有點(diǎn)的邊都涂成相同的顏色，例如藍(lán)色。距離為2的點(diǎn)的所有邊也都標(biāo)記相同的顏色，例如黃色。繼續(xù)這樣操作，以使連接點(diǎn)的邊距相等的距離都標(biāo)記相同的顏色。

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

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

　　這個想法是將樹定位，使其覆蓋每種顏色的一個邊，且不覆蓋任何顏色兩次，數(shù)學(xué)家們將此位置稱為樹的彩虹副本。對于一個具有2n+1個點(diǎn)的完整圖來說，由于著色需要n種顏色，并且其彩虹副本總是具有n+1個點(diǎn)的樹圖，因此我們知道彩虹副本是存在的。

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

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

　　隨著工作不斷進(jìn)行，放置下一個樹的工作越來越難，因此你可能需要提前做好計(jì)劃。三個數(shù)學(xué)家從一開始就知道，找到彩虹副本或許不難，難得是如何放置。就好像打包過行李箱，眾所周知，我們應(yīng)該從最困難、最復(fù)雜的物體開始，比如手提箱、自行車等，因?yàn)闊o論如何，你最后總能找到縫隙塞進(jìn)一些小東西，數(shù)學(xué)家們也采納了這一哲學(xué)。

　　想象一棵有11條邊的樹，其中6條邊的點(diǎn)集中在一起。剩下的大部分是單一的形狀，像卷須一樣。

　　最難放置的部分是具有6條邊的點(diǎn)。因此，數(shù)學(xué)家將它與樹的其余部分分開，然后將其首先放置。這就像你要把一張床移到樓上必須得先拆卸再進(jìn)行組裝一樣。

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

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

　　除此之外，三位數(shù)學(xué)家的研究結(jié)果給類似未解決的問題提供了新思路?；蛟S適當(dāng)調(diào)整一下還可以解決更多未知猜想。