国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2016-11-25 09:21:07鄧碩王獻(xiàn)芬
科技視界 2016年25期
關(guān)鍵詞:圖論證明

鄧碩 王獻(xiàn)芬

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

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

圖論是組合數(shù)學(xué)的一個分支,是離散數(shù)學(xué)的重要組成部分。近些年來,隨著計(jì)算機(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ù)目很少的地圖驗(yàn)證四色定理成立,由少及多,然而半個多世紀(jì)過去了,能被驗(yàn)證四色足夠的地圖,其區(qū)域數(shù)目才增至40個!實(shí)際上,區(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)該有個上限,并估計(jì)不超過10000個,這相當(dāng)于說,要把情況細(xì)分到可以證明的地步,要大約10000種情況才行!這是一個大膽預(yù)測。這使他成為繼肯普之后第一位公開宣稱四色問題能夠通過可約構(gòu)形思想來證明的數(shù)學(xué)家。顯然,構(gòu)造如此龐大的一個集合并證明其中每一個元素都可約用手算太不現(xiàn)實(shí),即使使用計(jì)算機(jī),在當(dāng)時也辦不到!盡管如此,但這種試圖用有限駕馭無窮的想法,卻成為四色定理獲證的一個關(guān)鍵思想。為了尋找不可避免集,希什引入了一種類似在電網(wǎng)絡(luò)中移動電荷的“放電”思想,這一創(chuàng)新思想成為四色定理最終獲證的又一關(guān)鍵。

正是在這個時候,阿佩爾(K. Appel, 1932-2013)和哈肯(W. Haken, 1928—)勇敢地接過來希什手中的“接力棒”。他們把研究重點(diǎn)放在調(diào)整放電法則而不是一味地擴(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多個小時后,終于攻克了這個難題?!睹绹鴶?shù)學(xué)會通報》刊出四色定理獲得計(jì)算機(jī)輔助證明的消息,轟動了當(dāng)時整個數(shù)學(xué)界[2]。

3 1976年以后

在數(shù)學(xué)定理證明中,阿佩爾和哈肯史無前例地使用了計(jì)算機(jī)。人們?yōu)橹痼@與歡呼之后,便是懷疑與非議。顯然,四色定理的機(jī)器證明并未得到普遍認(rèn)可。事實(shí),其中主要原因有二:一是,使用計(jì)算機(jī)的部分無法用手算核實(shí);二是,應(yīng)該用手算核實(shí)的部分因過于繁瑣,無人能夠獨(dú)立完成。這些不太令人滿意的地方導(dǎo)致人們對定理的真實(shí)性持懷疑態(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)隊(duì),宣稱得到了一種更加簡化的證明方法。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ì)算機(jī)驗(yàn)證,5分鐘就能驗(yàn)證完畢!最后,也是更重要的是,第二代證明澄清了長期以來對定理真實(shí)性的種種置疑,再次肯定了四色定理的正確性[3]。第二代證明盡管也要用計(jì)算機(jī),但這種證明對人來講是更透明的,因?yàn)槊恳徊蕉伎梢赞D(zhuǎn)換成人可理解的證明,盡管它還不完全是一個標(biāo)準(zhǔn)的數(shù)學(xué)證明。時至今日,我們還沒有一個通常意義下的四色問題的數(shù)學(xué)證明??上驳氖牵M(jìn)入21世紀(jì),四色定理又有了新進(jìn)展。

3.2 形式證明(2005年)

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

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

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

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

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

4.1 圖著色理論的誕生

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

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

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

無論是頂點(diǎn)著色還是邊著色,研究對象均是簡單曲面(所謂簡單曲面就是不含有洞的曲面)上的圖。對于復(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ā)展(的理論)將具有永恒的價值。”的確,由它提出的大量形式化了的其他問題還有待解決,例如圖的頂點(diǎn)著色、邊著色、拓?fù)鋱D論中的著色問題,以及這三種量的任何組合的著色問題。無怪乎現(xiàn)代圖論之父塔特(W.T.Tutte, 1917-2002)感慨道,“四色問題是冰山一角、楔之尖端、孟春一啼”。當(dāng)然,本文只是略論了四色問題對圖論發(fā)展的影響,但愿可以起拋磚引玉的作用,而由四色問題的研究引導(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)芬.惠特尼對圖論的貢獻(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é)任編輯:張濤]

猜你喜歡
圖論證明
獲獎證明
判斷或證明等差數(shù)列、等比數(shù)列
判斷和證明等差數(shù)列、等比數(shù)列
基于FSM和圖論的繼電電路仿真算法研究
一道IMO題的推廣與證明
構(gòu)造圖論模型解競賽題
代數(shù)圖論與矩陣幾何的問題分析
知識文庫(2018年12期)2018-09-06 04:10:40
點(diǎn)亮兵書——《籌海圖編》《海防圖論》
孫子研究(2016年4期)2016-10-20 02:38:06
證明我們的存在
圖論在變電站風(fēng)險評估中的應(yīng)用
電測與儀表(2015年3期)2015-04-09 11:37:54
日土县| 车致| 古丈县| 清丰县| 蒙阴县| 民权县| 客服| 盐边县| 顺昌县| 奈曼旗| 嘉义县| 建湖县| 新巴尔虎右旗| 临漳县| 湘乡市| 长阳| 饶阳县| 黑龙江省| 安溪县| 印江| 吴忠市| 舟曲县| 浪卡子县| 弥渡县| 宁陵县| 灵石县| 鲁甸县| 绍兴县| 贵德县| 建湖县| 饶平县| 左权县| 济宁市| 乌兰察布市| 花莲县| 句容市| 安吉县| 柘荣县| 明溪县| 克山县| 武川县|