 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 1034 | 回復(fù): 4 | |||
| 當(dāng)前只顯示滿足指定條件的回帖，點擊這里查看本話題的所有回帖 | |||
[交流]
介紹四色問題的肯普證明（節(jié)選自《數(shù)學(xué)證明》、大連理工大學(xué)出版社 著 蕭文強）
|
|||
|
為方便朋友們的學(xué)習(xí),下面將《數(shù)學(xué)證明》（大連理工大學(xué)出版社，著 蕭文強）一書中有關(guān)肯普的錯誤證明介紹給大家. 要明白肯普的證明錯在哪里與后來希五德怎樣修正,較清晰地敘述是采用普通的圖論語言.一個圖由某些點和相連其中一些點的邊組成,每個點的次數(shù)是以該點為一個端點的邊的數(shù)目.如果每兩點頂多只有一條邊相連,又沒有一點自己與自己有邊相連,這個圖叫做單圖.如果任意兩點必有一條點接點由若干條邊合起來的路線連著,這個圖叫做連通圖.如果全部點和邊都在一平面上,而且任意兩條邊沒有相交點[端點不計],這個圖叫做平面圖.平面圖的邊,把平面分為若干份,每份叫一個面.設(shè)有v個點,e條邊和f個面,著名的毆拉公式v+f-e=2把這三個數(shù)字聯(lián)系了起來.設(shè)平面圖是單圖且為連通圖,則可證明必有一點的次數(shù)不大于5.利用反證法:設(shè)若不然,則每點的次數(shù)均不小于6,即:6v<=2e.同時又由于每個面至少有三條邊,即:3f<=2e.將兩式代入毆拉公式得:2<=e/3 + 2e/3 - e = 0 ,產(chǎn)生矛盾!所以一個單且連通的平面圖必有一個點的次數(shù)不大于5.作:deg<=5. 給定一個地圖在每個國家里取一點,若兩個國家有共同a/b/c/d(圖1).觀察所有以v'為起點,點接點由若干條邊組成的路線,上面的點隔個涂上a和 c.如果沒有一條這樣的線路以v'"為終點的話,我們只用把這些路線上的a和c兩色互調(diào),便可以把v'的色改為c,仍維持四種顏色著色，把 v 涂上a色補回去,便知道原來的圖只需要四種顏色,與圖的選取產(chǎn)生矛 盾(圖1). 如果從v'至v'"有一條這樣的路線,便不可能從v"為起點,有一條點接點由若干條邊組成的路線,上面的點隔個涂上b和d,終點是v"".于是用類似的推斷,亦產(chǎn)生矛盾(見圖2)! 情況2:v的次數(shù)是5,與v相連的五點v'/v"/v'"/v""/v'""各涂上色a/b/a/c/d(見圖3).像剛才的考慮一般,可以假定有一條點接點由若干條邊組成的路線,從v"走到v'"",上面的點隔個涂上b和d,也有一條點接點由若干條邊組成的路線,從v"走到v"",上面的點隔個涂上b和c.于是從v'至v""不會有這樣的路線,上面的點隔個涂上a和c;從v'"至v'""也不會有這樣的路線,上面的點隔個涂上a和d.把這些從v'出發(fā)的路線上的a和c二色互調(diào),把這些從v'"出發(fā)的路線上的a和d二色互調(diào),便可以把v'與v'"的色分別改為c和d,于是把v涂上a色補回去,便知道原來的圖只需用四種顏色,與圖的選取產(chǎn)生矛盾! 肯普以為他排除了全部可能情況,所以沒有找到反例.即是說,四色猜想給證實了.希五德指出的漏洞出現(xiàn)于最后一種情況,當(dāng)我們把那些從v'出發(fā)的路線上的a和c二色互調(diào)時,可能制造了一條從v'"至v'""的路線,上面的點隔個涂上a和d!(v'"-d-c-v'""  因此,當(dāng)我們再把a和d二色互調(diào)時,只是把v'""的d色換作d色,把v'"的a色換作d色,對v來說仍然要涂上第五色!他給了一個反例(見圖3).固然這是一個局部反例,說明了原來的證明行不通,卻不是全局反例,因為他的圖(*)是可用四種顏色著色的.希五德還指出肯普的想法,可以搬來證明五種顏色是足夠了,讀者愿意試證明嗎?肯普的想法雖然行不通,卻是一個很有意思的想法.他的戰(zhàn)術(shù)是找出一組"無可避免"的構(gòu)形,意思是說任何單且連通的平面圖肯定包含至少一個這類構(gòu)形作為里面的一部分,然后設(shè)法證明每一個這類構(gòu)形都是"可約"的,即它不能在四色猜想的最小反例里出現(xiàn).肯普的證明所選的"無可避免"的構(gòu)形,由那些次數(shù)小于5和它的相鄰點組成,他以為已經(jīng)證明了每一個都是"可約"的,但希五德指出了最后一個并不是"可約",故證明不完全.后來從事這方面研究的人還是循著這條路走,把那些并不"可約"的"無可避免"構(gòu)形再分解,試圖證明分解了的構(gòu)形變成"可約"的.這樣做可能導(dǎo)致一組個數(shù)很多的"無可避免"的構(gòu)形,曾經(jīng)一度大家以為約有一萬多個,其中有些還包含很多點的,即使運用電子計算機去驗證一個這樣的構(gòu)形是否"可約",亦得花上100個小時.撇下儲存問題不理,單是計算也得花上100年左右!后來美國數(shù)學(xué)家哈肯與阿佩爾成功地把"無可避免"構(gòu)形數(shù)縮減至1478個,把驗算時間縮短至1200小時.在1976年,他們宣稱四色猜想是對的.文章在1977年發(fā)表,長達(dá)139頁,還附上電子計算機程序的微形膠片400頁!過了10年后,還有人對他們的證明提出質(zhì)疑,認(rèn)為存在著漏洞.哈肯與阿佩爾亦有回應(yīng).據(jù)他們說,那些漏洞都給補足了.對于四色猜想是否解答了,數(shù)學(xué)家的意見還是莫衷一是. 四色問題由肯普的證明至今已一百多年,究竟有多少人研究過他的方法,又有多少人親自動手去操作實踐一下他的方法的過程,不得而知.請有意為學(xué)之精神者認(rèn)真讀書.這是我親自從蕭教授的書上節(jié)選的,保證無誤.并希廣泛發(fā)表意見,以鼓勵本人繼續(xù)學(xué)習(xí). *這里的圖指原書希五德舉出的反例圖,該圖是塊地形圖,在電腦中很難畫.故本人經(jīng)認(rèn)真分析研究后選取用圖3表示.根據(jù)最少著色原則,他所舉的圖例可用四種顏色著色. 有關(guān)的圖另發(fā)。 |
回復(fù)此樓» 猜你喜歡
一志愿大連理工大學(xué)材料求調(diào)劑
已經(jīng)有5人回復(fù)
-
材料與化工調(diào)劑一志愿大連海事085600，349
已經(jīng)有6人回復(fù)
-
一志愿中海洋320化學(xué)工程與技術(shù)學(xué)碩求調(diào)劑
已經(jīng)有4人回復(fù)
-
材料科學(xué)與工程調(diào)劑
已經(jīng)有11人回復(fù)
-
311求調(diào)劑一志愿合肥工業(yè)大學(xué)
已經(jīng)有4人回復(fù)
-
一志愿食品科學(xué)與工程083200求調(diào)劑
已經(jīng)有4人回復(fù)
-
材料科學(xué)與工程求調(diào)劑
已經(jīng)有10人回復(fù)
-
一志愿北化085600材料專碩275|有文章專利｜求調(diào)劑
已經(jīng)有11人回復(fù)
-
一志愿 南京航空航天大學(xué) ，080500材料科學(xué)與工程學(xué)碩
已經(jīng)有4人回復(fù)
-
085600材料與化工調(diào)劑
已經(jīng)有15人回復(fù)
» 本主題相關(guān)價值貼推薦，對您同樣有幫助:
- 圖論方面的一個小問題
已經(jīng)有14人回復(fù)
- 求助：怎么證明這個數(shù)學(xué)式子？？
已經(jīng)有6人回復(fù)
- 求問導(dǎo)師資助證明
已經(jīng)有11人回復(fù)
- 關(guān)于導(dǎo)師資助證明有問題請教
已經(jīng)有8人回復(fù)
- 怎樣證明0和1之間沒有整數(shù)？
已經(jīng)有6人回復(fù)
- 本人考大連理工大學(xué)，分?jǐn)?shù)已出，如何著手復(fù)試��？
已經(jīng)有4人回復(fù)
- 求助解一道數(shù)學(xué)證明題
已經(jīng)有2人回復(fù)
- 有關(guān)數(shù)學(xué)期望的證明題
已經(jīng)有4人回復(fù)
- 一道關(guān)于商空間的證明題
已經(jīng)有13人回復(fù)
- “優(yōu)先出版”的問題？
已經(jīng)有7人回復(fù)
- 國家行政學(xué)院出版社-《公共基礎(chǔ)快速過關(guān)》
已經(jīng)有336人回復(fù)
- 代爾夫特理工大學(xué) 面試主要問什么？
已經(jīng)有7人回復(fù)
★
math105(金幣+1): 歡迎討論有價值的話題。 2011-04-20 23:03:33
math105(金幣+1): 歡迎討論有價值的話題。 2011-04-20 23:03:33
|
前兩個好用，第三個圖是有關(guān)希伍德的反例；不過我這里是9個點的反例圖。 |----------------------------c----------------------------| |................................../.|.\................................| |......|--------------------/...|...\---------------....|......| |......|...........................a(v').......................|.......| |......|............................|............................|.......| |......|............................|............................|.......| |......|..........|-------------v------------------|....|.......| |......|......./....\.................................../....\..|.......| |.....d(v""').....c(v"" ....................a(v"')......b(v".||......|..............|............................|.............|........| |......\............./..............................\............/........| |........\........../.................................\........../.........| \..........\....../.....................................\....../.........../ ...\........\.../.........................................\.../........../ ....\---------B--------------------------------D---------/ ...................圖 3................................... [ Last edited by liufu on 2011-4-20 at 21:53 ] |
4樓2011-04-20 21:43:52
|
先謝謝版主的夸獎。至于是否為資源帖，無所謂；不過，我得真誠地告訴網(wǎng)友，隨便在百度搜搜，是不會搜到的；不信您試試！現(xiàn)在我畫第一個圖： ........a............................ ........|............................ .......c............................. .......|...........b(v'')........... .......|...........|.................. .......a(v')------V------c(v"') .......|...........|.................. .......C..........D(V"" ........圖1. [ Last edited by liufu on 2011-4-20 at 09:44 ] |
2樓2011-04-20 09:41:20
|
看來第一個圖，還可用；缺點是大小寫字母有些混淆。畫第二圖： ......C--------A---------C----A ......|................................| ......|.........B(V" ...............|......|.........|......................| ....A(V')----V-----------------C(V"" ................|.......................... ...............D(V"" ................................圖 2.......................... 順便留給大家一個問題：在肯普的證明中，不論是情形1或2，為什么總存在某兩點沒有聯(lián)通對角鏈？您能否找出其理論根據(jù)？ [ Last edited by liufu on 2011-4-20 at 10:45 ] |
3樓2011-04-20 10:42:51
5樓2011-04-29 12:03:18
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考博] 材料專業(yè)申博 +3 | 杜雨婷dyt 2026-03-29 | 3/150 |
|
|---|---|---|---|---|
|
[考研] 285求調(diào)劑 +5 | AZMK 2026-03-30 | 8/400 |
|
|
|
[考研] 一志愿中海洋材料357 +3 | 麥恩莉. 2026-03-30 | 3/150 |
|
|
|
[考研] 生物學(xué) 296 求調(diào)劑 +5 | 朵朵- 2026-03-26 | 7/350 |
|
|
|
[考研] 085600 材料與化工 329分求調(diào)劑 +18 | Mr. Z 2026-03-25 | 19/950 |
|
|
|
[考研] 317分 一志愿南理工材料工程 本科湖工大 求調(diào)劑 +12 | 芋泥小鈴鐺 2026-03-28 | 12/600 |
|
|
|
[考研] 071010 323 分求調(diào)劑 +3 | Baekzhy 2026-03-27 | 3/150 |
|
|
|
[考研] 085701求調(diào)劑初試286分 +5 | secret0328 2026-03-28 | 5/250 |
|
|
|
[考研] 317求調(diào)劑 +10 | 蛋黃咸肉粽 2026-03-26 | 10/500 |
|
|
|
[考研] 343求調(diào)劑085601 +3 | 要努力學(xué)習(xí)x 2026-03-29 | 3/150 |
|
|
|
[考研] 本科雙非材料，跨考一志愿華電085801電氣，283求調(diào)劑，任何專業(yè)都可以 +6 | 芝士雪baoo 2026-03-28 | 8/400 |
|
|
|
[考研] 求調(diào)劑 +7 | 爭取九點睡 2026-03-28 | 8/400 |
|
|
|
[考研] 一志愿南師大0703化學(xué) 275求調(diào)劑 +4 | Ripcord上岸 2026-03-27 | 4/200 |
|
|
|
[考研]
 一志愿 西北大學(xué) 總分282 英語一62 求調(diào)劑
+7
|
18419759900 2026-03-25 | 8/400 |
|
|
|
[考博] 26申博 +3 | 加油沖啊！ 2026-03-26 | 3/150 |
|
|
|
[考研] 348求調(diào)劑 +4 | 小懶蟲不懶了 2026-03-27 | 5/250 |
|
|
|
[考研] 求調(diào)劑 +3 | 劉柯@ 2026-03-24 | 4/200 |
|
|
|
[考研] 321求調(diào)劑 +6 | wasdssaa 2026-03-26 | 6/300 |
|
|
|
[考研]
 085602 289分求調(diào)劑
+8
|
WWW西西弗斯 2026-03-24 | 8/400 |
|
|
|
[考研] 277分求調(diào)劑，跨調(diào)材料 +3 | 考研調(diào)劑lxh 2026-03-24 | 3/150 |
|