四色定理獲證歷程及對圖論的影響

鄧 碩 王獻芬

（1.河北地質大學數理學院，河北 石家莊050031；2.河北師范大學數學與信息科學學院，河北 石家莊050024）

四色定理獲證歷程及對圖論的影響

鄧 碩1王獻芬2

（1.河北地質大學數理學院，河北 石家莊050031；2.河北師范大學數學與信息科學學院，河北 石家莊050024）

通過回溯四色問題從猜想到定理的歷史過程，揭示了簡化思想在數學方法中的主導作用，最后簡述四色問題對圖論發展的影響，以對相關研究有所助益。

圖論；四色定理；證明；圖著色；拓撲圖論

圖論是組合數學的一個分支，是離散數學的重要組成部分。近些年來，隨著計算機科學的發展，圖的理論及其在其他科學領域的廣泛應用，越來越受到數學界乃至科學界的重視。同其他數學學科相比，圖論的歷史雖不太久遠，但是其內容的豐富、問題的難度、技巧的精湛及其理論的交叉融合，卻是難以想象的。一個表述簡單的問題，證明起來卻有著意想不到的艱難。限于篇幅，本文簡要論述四色問題從猜想到證明的歷程，從中獲得有益啟示。

1 早期歷史

所謂四色問題，簡單說就是，若給平面（或球面）上任意地圖著色，使得相鄰兩區域不能用相同顏色，問是否四種顏色足夠？此問題是剛從倫敦大學畢業不久的英國青年葛斯瑞（F.Guthrie,1831-1899）在1852年的一個猜測。迄今為止，人們發現的第一個正式的文字記錄是德·摩根在1860年4月14日寫的一篇書評[6]。由于英國大數學家凱萊（A.Cayley，1821-1895）在1878年6月13日召開的倫敦數學會上當場發問，四色問題是否已被證明，從而引起了數學界極大的反響[1]。各國數學中心和主要數學雜志此后源源不斷地收到四色問題的各種證明。

1879年，劍橋大學三一學院數學畢業生肯普（A.B.Kempe,1849-1922）首先給出了一個 “證明”。11年后，即1890年，希伍德（P.J. Heawood，1861-1955）首先給出一個反例圖（即希伍德圖），指出了肯普證明的疏漏。四色問題又成了未解之謎！

盡管肯普和希伍德均未能破解四色問題，但是，他們二人均為四色問題的最終獲證乃至圖論的發展做出了早期貢獻。進入20世紀，數學家研究四色問題正是沿著肯普和希伍德開辟的道路前行的：一方面是定性方法，主要圍繞肯普提出的“肯普鏈”展開；另一個則是定量方法，即希伍德構造極小反例的方法。利用這兩種方法，數學界開始的做法是對區域數目很少的地圖驗證四色定理成立，由少及多，然而半個多世紀過去了，能被驗證四色足夠的地圖，其區域數目才增至40個！實際上，區域數越多，可能的構形數目也就越大，就越困難。到20世紀60年代，這種依靠擴充區域數目的推廣盡管已推至100多個，但四色問題距離解決還差得很遠。

2 1976年的突破

要想完整地證明四色定理，還需要引入新的概念，特別是可約化的構形，亦即把區域數多的問題簡化為區域少的情形。20世紀70年代，德國數學家希什（H.Heesch，1906-1995）推測這種構形應該有個上限，并估計不超過10000個，這相當于說，要把情況細分到可以證明的地步，要大約10000種情況才行！這是一個大膽預測。這使他成為繼肯普之后第一位公開宣稱四色問題能夠通過可約構形思想來證明的數學家。顯然，構造如此龐大的一個集合并證明其中每一個元素都可約用手算太不現實，即使使用計算機，在當時也辦不到！盡管如此，但這種試圖用有限駕馭無窮的想法，卻成為四色定理獲證的一個關鍵思想。為了尋找不可避免集，希什引入了一種類似在電網絡中移動電荷的“放電”思想，這一創新思想成為四色定理最終獲證的又一關鍵。

正是在這個時候，阿佩爾（K.Appel,1932-2013）和哈肯（W. Haken,1928—）勇敢地接過來希什手中的“接力棒”。他們把研究重點放在調整放電法則而不是一味地擴充不可避免集中可約構形的數目。他們運用希什的思想，重點著眼于不可避免集中那些看上去不可能可約的構形，然后重新設計放電算法以排除這些特殊構形。1976年，他們由于找到了一種新的放電程序，利用“窮舉檢驗”法分情況檢查，篩選出1482種可約的構形，即分了1482種情況，借助IBM360計算機，運行達1200多個小時后，終于攻克了這個難題?！睹绹鴶祵W會通報》刊出四色定理獲得計算機輔助證明的消息，轟動了當時整個數學界[2]。

3 1976年以后

在數學定理證明中，阿佩爾和哈肯史無前例地使用了計算機。人們為之震驚與歡呼之后，便是懷疑與非議。顯然，四色定理的機器證明并未得到普遍認可。事實，其中主要原因有二：一是，使用計算機的部分無法用手算核實；二是，應該用手算核實的部分因過于繁瑣，無人能夠獨立完成。這些不太令人滿意的地方導致人們對定理的真實性持懷疑態度，甚至上升到了對數學證明含義的哲學探討。然而，想必很多人還以為就只有這么一代證明吧。

3.1 再次機器證明（1994年）

第一代證明以后，數學家們并沒有放棄尋求嚴格的數學證明，也因此推動了圖論學科的發展，這也是為什么圖論的大多數問題都與四色問題有關的原因。到20世紀90年代，曾一直致力于研究四色問題的西繆爾（P.Seymour，1950-）團隊，宣稱得到了一種更加簡化的證明方法。1994年，西繆爾應邀參加第22屆國際數學家大會，并做1小時大會報告。

西繆爾等人的證明盡管基本思路與阿佩爾、哈肯的大致相同，但這個簡化后的證明不乏創新思想。首先，證明篇幅從原來的741頁，精簡到43頁。其中，放電法則從486個減至20個；不可避免構形從1482個減少到633個；圖著色算法由4次時間算法優化為2次時間算法；證明所需機時由1200小時縮至24小時。其次，第二代證明達到了人工復核的要求。如果用計算機驗證，5分鐘就能驗證完畢！最后，也是更重要的是，第二代證明澄清了長期以來對定理真實性的種種置疑，再次肯定了四色定理的正確性[3]。第二代證明盡管也要用計算機，但這種證明對人來講是更透明的，因為每一步都可以轉換成人可理解的證明，盡管它還不完全是一個標準的數學證明。時至今日，我們還沒有一個通常意義下的四色問題的數學證明?？上驳氖?，進入21世紀，四色定理又有了新進展。

3.2 形式證明（2005年）

在某種程度上，盡管西繆爾等人的漂亮修正，平息了對于四色定理證明的置疑與非議，但無論如何，總有某些地方似乎“不大受歡迎”。至少英國劍橋微軟研究院的高級研究員貢蒂爾（Georges Gonthier）這么認為。

30多年來，隨著計算機科學的發展，一種所謂的形式證明進入了數學界。這種證明法的思想是編寫一種既能描述機器應該做什么，也能刻畫它為什么必須這么執行的編碼。證明的有效性是由不同程序進行復核的客觀數學事實，而程序本身的正確性可以通過運行多種輸入程序憑實驗確定。盡管困難重重，四色定理還是迎來了它的第三代證明。2005年，貢蒂爾公布了他關于四色定理的形式證明，這個證明可以由Coq輔助證明系統完全復核[3]。

從某種意義上講，我們認為，形式證明的提法對數學和計算機科學有著十分重要的意義：首先，再次強烈肯定四色定理確實是一個定理；其次，對于大量已有數學證明的數學定理，如何找出一個形式證明，這給數學家與計算機科學家提供了一個新的研究領域。

然而，對數學家來講，更為令人信服的方法，當然是純粹數學的證明，而且越簡單越好。

4 推動圖論的發展

4.1 圖著色理論的誕生

四色問題可以做這樣的化簡：把一個區域看成一個點，任何兩個區域相鄰（或者不相鄰），就把代表兩區域的點連上線，否則就不連線。這樣的結構就稱為圖。四色問題也就變成圖的頂點著色問題。從歷史上看，20世紀30年代以前，圖著色理論主要研究地圖的著色，盡管肯普早在1879年就意識到了圖的頂點著色與地圖的面著色之間的對偶關系，但是除肯普外，其他數學家在當時還沒有這種意識，更沒有上升到研究一般圖的著色問題的高度。直到惠特尼（H.Whitney,1907-1089）和布魯克斯（R.L.Brooks,1916-1993）[1]的文章發表以后，圖著色理論才逐漸由地圖著色轉向一般圖的著色。值得一提的是，惠特尼正是由于對四色問題的研究而對圖論做出了大量原創性的貢獻[4]。

除了給圖的頂點著色外，對圖的邊進行著色的研究也非常有趣。1880年，泰特給出了四色猜想的一個等價猜想：對任意三次正則地圖著色，使相鄰兩條邊界顏色不同，至多需要三種顏色。這自然地就產生一個一般的問題：給一個圖的邊著色，使其相鄰兩條邊顏色不同，至少需要幾種顏色？與頂點著色類似，這個最小的顏色數目叫做邊色數。在圖的著色理論中，邊染色問題主要研究邊色數的確定和上下界。頂點度顯然是與邊染色最直接的相關因素：任意圖的邊色數不能小于它的最大頂點度。數學家從這個基本的結論出發，研究了邊色數與最大頂點度之間進一步的關系。1964年，衛津（V.G.Vizing,1937—）從邊著色的研究中提出了圖的分類問題。另外，由于實際的需要，很多問題并不能很容易地化歸為頂點著色或邊著色，這屬于經典著色的范疇。于是就有必要引入更廣泛的著色模型，并添加各種各樣的約束條件。例如，允許一次使用多個顏色，即把幾個顏色捆綁起來等。如此一來，圖著色的模型甚至多達幾十個。例如，清單著色、調和著色、區間著色、循環著色、強著色等推廣的圖著色問題。正如狄拉克（G.A.Dirac,1925-1984）所言，“抽象的圖的著色推廣了地圖的著色，對抽象的圖的著色的研究…打開了組合數學的一個新篇章?！盵5]

4.2 拓撲圖論的開始

無論是頂點著色還是邊著色，研究對象均是簡單曲面（所謂簡單曲面就是不含有洞的曲面）上的圖。對于復雜曲面上圖的著色，還要追溯到1890年希伍德的工作[1]。他把地圖四色問題推廣到任意曲面，從而辟建了拓撲圖論并推動了其發展。例如，一個平面或球面上的地圖，四色是足夠的，那么在環面（輪胎面）上，四色就不夠了，至少需要七色才行。關于希伍德成就的綜述可以參見G.A.狄拉克[6]。

5 結語

數學問題是數學發展的源泉。這不僅體現在對問題本身的解決上，還體現在隨之而來的理論的進展上。對于數學問題，數學家感興趣的主要是方法方面的問題，這是他們的專業。但是，從知識創新的高度來看，數學家更要關注問題的來龍去脈、數學方法的精髓以及數學問題在解決過程所帶來的“副產品”。像四色問題這類敘述簡單又極易明白，卻讓許多數學家畢生求索的“世界難題”，對于數學證明的理解也是十分重要的，本文在四色定理獲證的歷史中表明，簡化永遠是數學方法的靈魂。

今天，四色猜想已然成為四色定理。但對于數學家來說，圖論研究的事業方興未艾。四色問題不僅產生了大量新的概念、新的方法乃至新的問題，如已于2006年獲證的強完美圖定理，而且開辟了許多新的分支。這些似乎正好印證了圖論專家鮑耐特（David Barnette）的話：“雖然四色定理已被證明了，但是數學家在大量未成功的嘗試中所發展（的理論）將具有永恒的價值?！钡拇_，由它提出的大量形式化了的其他問題還有待解決，例如圖的頂點著色、邊著色、拓撲圖論中的著色問題，以及這三種量的任何組合的著色問題。無怪乎現代圖論之父塔特（W.T.Tutte,1917-2002）感慨道，“四色問題是冰山一角、楔之尖端、孟春一啼”。當然，本文只是略論了四色問題對圖論發展的影響，但愿可以起拋磚引玉的作用，而由四色問題的研究引導的其他圖理論，將另文再續。

［1］Biggs N L,Lloyd E.K,Wilson R J.Graph Theory 1736-1936[M].Oxford: Clarendon Press,1986.

［2］Appel K,Haken W.Every planar map is four colorable,PartⅠ:Discharging, PartⅡ:Reducibility Illinois Journal of Mathematics.1977,21:429-490.

［3］王獻芬，胡作玄.四色定理的三代證明[J].自然辯證法通訊.2010(4).

［4］王獻芬.惠特尼對圖論的貢獻[J].自然科學史研究.2010,29(1):101-117.

［5］Chartrand G,Ping Zhang.Chromatic Graph Theory[M].Boca Raton,London, New York:CRC Press,2009.

［6］Dirac G A.Percy John Heawood[J].J.London Math.Soc.1963,38:263-277.

［責任編輯：張濤］

※基金來源：國家自然科學基金（11201113）和教育部博士點新教師類基金（20121303120001）。

鄧碩（1987—），女，河北地質大學數理學院，助教，研究方向為代數編碼理論。