第169章 這就很離譜！

請關閉瀏覽器的閱讀/暢讀/小說模式並且關閉廣告遮蔽過濾功能，避免出現內容無法顯示或者段落錯亂。

有數學家觀察到，如果三度圖中任意由邊圍成的區域，邊的個數都是3的倍數，那麼圖可以被4-染色。他進一步現，只要存在一種給圖的頂點賦值+1或-1的方法，使得每個區域的頂點數字之和都被3整除，那麼圖可以被4-染色。可以證明，4-染色和存在賦值方法是等價的。

在美國，數學家對四色定理的研究從未停止過。

除了約翰·霍普金斯大學的皮爾斯以及斯多利等人外，另一個研究者是保羅·溫尼克。從當時的學術聖地哥廷根大學畢業的溫尼克來到美國後在肯塔基大學任教。他19o4年表的論文中已經出現了可約性的雛形。然而美國數學界在四色問題上次實質性的進展出現在1912年後。普林斯頓大學的奧斯瓦爾德·維布倫（經濟學家托爾斯坦·範伯倫的侄子）是這波浪潮的先鋒。他的工作重心是拓撲學，19o5年證明了若爾當曲線定理。對龐加萊展出的新代數工具有深入瞭解的他，很自然地開始對四色定理的研究。他使用有限幾何學的觀念和有限域上的關聯矩陣作為工具，將四色問題轉化成有限域係數空間上的方程問題。這個方向被後來的密碼學家、數學家威廉·托馬斯·塔特稱為“量化方法”（thequantitativemethod）。同年，他的普林斯頓同僚喬治·戴維·伯克霍夫也開始探索這個方向，但一年之後他開始轉向肯普的方法，也即是塔特所稱的“定性方法”（thequa1itativemethod），並提出可約環（redunetg）的概念。1913年，伯克霍夫表名為《地圖的可約性》（TheReducibi1ityofmaps）的論文，利用可約環證明了由不過12個國家構成的地圖都能用四色染色。1922年，伯克霍夫的學生菲利普·富蘭克林運用同樣的方法，將結論加強到不過25個國家構成的地圖都能用四色染色。由於別克霍夫次證明四色定理對不過12個國家的地圖成立，歷史上證明的可染色地圖的國家數上限記錄被稱為別克霍夫數。

伯克霍夫等人的證明是肯普的方法的延續和系統化，歸納為尋找一個不可避免的可約構形集（anunavoidab1esetofredunets）。

這個理念已經體現在肯普的證明中。

他先說明任一地圖中必然存在以下四種構形2鄰國國家、3鄰國國家、4鄰國國家和5鄰國國家；然後證明每種構形都是可約構形。後來希爾將這種分類方式稱為“不可避免集”。

伯克霍夫的構想是使用反證法反設存在至少需要五種顏色染色的地圖，那麼其中必然存在國家數最小的“極小五色地圖”（five-chromaticmap）。這個地圖必然是“不可約的”（irreducib1e）。而只要找到一組構形，使極小五色地圖中不可避免地會出現其中一種構形，並且每個構形都是可約的，那麼就能夠透過約化，將地圖的國家數減少，從而導致矛盾。

肯普找的不可避免集由四種構形組成，但他無法證明最後一種（5鄰國國家）的可約性，因此伯克霍夫開始尋找刻畫不可避免集的新方法。

他提出以相鄰國家連成的環來將整個地圖m分為三個部分環內部分a、環外部分B以及環本身R。若環上的國家數為n就稱其為n-環。如果R的任意染色都不妨礙a進行染色，那麼就可以“忽略”a而將m的染色問題約化為B+R的染色問題。這時便稱a+R是可約構形，R稱為可約環。伯克霍夫證明了當R是4-環，或者R是5-環且a中國家不止一個，或者a+R是“伯克霍夫菱形”時，a+R都是可約的構形。因此極小五色地圖不可能包含這些構形。

富蘭克林進一步證明極小五色地圖中必定包含三個鄰接的五邊國（5鄰國的國家），或者鄰接的兩個五邊國與一個六邊國，或者鄰接的一個五邊國和兩個六邊國。他從而得出一系列的可約構形，形成了25國以下地圖的不可避免的可約構形集。因此推出，極小五色地圖必定至少包含26個國家。

富蘭克林現，極小五色地圖必定包括以上6種情形之一。

這種方法的終極目標是找到所有地圖的不可避免的可約構形集。然而隨著國家數增多，要找到不可避免集並證明其可約化性就越難。這主要是因為隨著環的增大，染色的方法數目會迅增大。6-環的4-染色方法有31種，而12-環則有種。因此對大環圍成的構形驗證可約性是十分繁雜的工作。

1926年，neto1ds將別克霍夫數從25提高到27。1938年，富蘭克林將其推進到31。1941年，net將之提高到35。而直到1968年，別克霍夫數才更新為4o。

四色問題研究的下一個突破並不是在美國，而是由哥廷頓大學出身的德國數學家亨利·希爾帶來的。

他在1948年提出不可避免集的存在性，但他提出的不可避免集可能包含個構形，其中還有18-環的龐大構形。希爾的另一個成果是在1969年提出“放電法”（disnetgmethod），為尋找不可避免集給出了系統的方法。

人工尋找不可避免構形集和驗證構形可約性過於緩慢，數學家開始考慮使用當時新出現的計算機作為輔助，以提高驗證的效率。構造出放電法的同時，藉助於計算機來驗證構形可約性的工作也飛進展。

希爾在kar1dürre的幫助下在1965年設計了第一個演算法來驗證構形的可約性。他們使用的是a1go16o語言，在德國漢諾威技術學院計算機中心的一臺cdc15o4a電腦上次執行。1967年前，由於記憶體不足，只能驗證12-環以下的構形。而希爾找出的不可避免集含有的大構形可以達到14-環甚至更多，計算機的能力並不足以快完成可約性的驗證。

當時美國的計算機技術領先於歐洲，因此希爾希望能夠藉助美國的大型計算機來證明四色定理。1967年，美國紐約布魯克海文國家實驗室（BnL）應用數學院院長邀請希爾來美國訪問，並允許他使用當時世界上最快的計算機cdc66oo。其後幾年，希爾兩度到美國尋求大型計算機的使用機會。這段時間中，dürre將程式用FoRTRan進行重寫。抱著在德國最終解決四色問題的希望，希爾回到德國，但令他失望的是，德國學術界對他的計劃持否定態度，並不願為他的程式撥出計算時間。

在數次訪美時，希爾開始與沃夫岡·哈肯合作。

哈肯在1948年曾經旁聽過希爾提出不可避免集的課程，之後對四色定理產生了持續的興趣。兩人透過信件交流合力作出很多進展，為最終解決四色問題鋪平道路。1971年，阿佩爾也開始在哈肯的介紹下研究四色問題。然而當時哈肯對解決四色問題的前途感到悲觀，因為尋找並驗證合適的不可避免可約構形集實在過於複雜，即便藉助計算機也需要過多的時間。塔特當時也認為，即便最樂觀的估計中，不可避免集也要包含至少8ooo個構形。然而塔特等人也將希爾的工作介紹到美國（當時希爾的工作只在德國表過），並引了很多人的熱情。包括弗蘭科·阿萊爾、愛德華·雷尼爾·斯瓦特、弗蘭科·R·伯恩哈特等人都開始尋找不可避免集以及檢驗可約性。哈肯和阿佩爾依賴於計算機的工作能力，因此不斷改良放電過程。他們將透過放電過程尋找不可避免集的演算法和驗證可約性結合起來，當某個不可避免集的構形不是c-可約（可約性的一種）或難以被驗證為c-可約的時候，就放棄這個不可避免集，以提高效率。兩人設定了很多經驗性的修正規則，比如設定三個經驗性的“障礙”（三種特定的構形），當某個構形中含有這種障礙就直接認為是不可約的；又比如構形的大小不能過14-環，等等。

1975年，哈肯找到一種很好的放電過程，但難以化為演算法程式。於是兩人暫時開始迴歸紙筆計算。這時候他們得到當時還是博士學生的約翰·科赫的支援，後者對他們提供了可約性驗證演算法工作上的幫助。1976年3月，他們終於得到一個由1936個構形組成的不可避免集，對應的放電過程由487條規則構成。同時伊利諾伊大學的主電腦也更換成運算度更高的IBm36o，為計算節省大量時間。經過電腦12oo小時的驗證，他們終於在6月得出1936個構形都是可約構形。這代表著四色定理最終的解決[2]:35。這時候他們的幾個競爭對手如阿萊爾、斯瓦特等的工作也將近尾聲。

1976年6月22日，哈肯和阿佩爾次在美國數學協會（m.a.a.）於多倫多大學召開的美國數學學會（a.m.s.）夏季會議公佈他們的結果。不久，伊利諾伊大學數學系的郵戳上加上了“四種顏色就夠了”（FouRcoLoRssuFFIce）的一句話，以慶祝四色猜想得到解決。9月，美國數學學會的公告專欄上刊登了兩人證明四色定理的訊息。

1977年，哈肯和阿佩爾將結果寫成名為《任何平面地圖都能用四種顏色染色》（everyp1anarmapisfourco1orab1e）的論文，分成上下兩部分，表在《伊利諾伊數學雜誌》。

至此，困擾人們長達長久的四色問題終於被解決了。

可以看得出來長久人們圍繞著四色猜想主要進行的工作都是圍繞著可約性驗證進行的。

在這一過程中，諸如計算機這樣的新工具對簡化運算帶來了很大幫助~

良好的工具對科研會提供良好的助力~

然鵝工具太先進也不是什麼好事情！

章杉從系統圖書館內總共看到了9種全新的證明方法。

然而有六種都沒辦法使用！

利用量子計算機證明是什麼鬼？

現有根本沒有合適的量子計算機，難道為了這次證明明點新工具。

還有利用特子計算機證明是什麼鬼！這就出章杉的想象力了。

再幾種更是沒眼看~

這就很離譜！

不過好在還是有三種能用的方法的~

只是利用現有的工具即可，證明思路也很巧妙。

這就很nice了~

喜歡讀書成神豪請大家收藏讀書成神豪本站更新度全網最快。