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

鄧 碩 王獻(xiàn)芬

（1.河北地質(zhì)大學(xué)數(shù)理學(xué)院，河北 石家莊050031；2.河北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，河北 石家莊050024）

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

鄧 碩1王獻(xiàn)芬2

（1.河北地質(zhì)大學(xué)數(shù)理學(xué)院，河北 石家莊050031；2.河北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，河北 石家莊050024）

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

圖論；四色定理；證明；圖著色；拓?fù)鋱D論

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

1 早期歷史

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

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

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

2 1976年的突破

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

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

3 1976年以后

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

3.1 再次機(jī)器證明（1994年）

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

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

3.2 形式證明（2005年）

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

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

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

然而，對數(shù)學(xué)家來講，更為令人信服的方法，當(dāng)然是純粹數(shù)學(xué)的證明，而且越簡單越好。

4 推動圖論的發(fā)展

4.1 圖著色理論的誕生

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

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

4.2 拓?fù)鋱D論的開始

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

5 結(jié)語

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

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

［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］王獻(xiàn)芬，胡作玄.四色定理的三代證明[J].自然辯證法通訊.2010(4).

［4］王獻(xiàn)芬.惠特尼對圖論的貢獻(xiàn)[J].自然科學(xué)史研究.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.

［責(zé)任編輯：張濤］

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

鄧碩（1987—），女，河北地質(zhì)大學(xué)數(shù)理學(xué)院，助教，研究方向為代數(shù)編碼理論。