鄧碩　王獻(xiàn)芬

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

【關(guān)鍵詞】圖論；四色定理；證明；圖著色；拓?fù)鋱D論

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

1 早期歷史

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

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

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

2 1976年的突破

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

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

3 1976年以后

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

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

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

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

3.2 形式證明（2005年）

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

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

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

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

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

4.1 圖著色理論的誕生

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

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

4.2 拓?fù)鋱D論的開(kāi)始

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

5 結(jié)語(yǔ)

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

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

【參考文獻(xiàn)】

[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)芬.惠特尼對(duì)圖論的貢獻(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é)任編輯：張濤]