 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 1005 | 回復(fù): 4 | |||
[交流]
介紹四色問題的肯普證明（節(jié)選自《數(shù)學(xué)證明》、大連理工大學(xué)出版社 著 蕭文強(qiáng)）
|
|
為方便朋友們的學(xué)習(xí),下面將《數(shù)學(xué)證明》（大連理工大學(xué)出版社，著 蕭文強(qiáng)）一書中有關(guān)肯普的錯誤證明介紹給大家. 要明白肯普的證明錯在哪里與后來希五德怎樣修正,較清晰地敘述是采用普通的圖論語言.一個圖由某些點(diǎn)和相連其中一些點(diǎn)的邊組成,每個點(diǎn)的次數(shù)是以該點(diǎn)為一個端點(diǎn)的邊的數(shù)目.如果每兩點(diǎn)頂多只有一條邊相連,又沒有一點(diǎn)自己與自己有邊相連,這個圖叫做單圖.如果任意兩點(diǎn)必有一條點(diǎn)接點(diǎn)由若干條邊合起來的路線連著,這個圖叫做連通圖.如果全部點(diǎn)和邊都在一平面上,而且任意兩條邊沒有相交點(diǎn)[端點(diǎn)不計],這個圖叫做平面圖.平面圖的邊,把平面分為若干份,每份叫一個面.設(shè)有v個點(diǎn),e條邊和f個面,著名的毆拉公式v+f-e=2把這三個數(shù)字聯(lián)系了起來.設(shè)平面圖是單圖且為連通圖,則可證明必有一點(diǎn)的次數(shù)不大于5.利用反證法:設(shè)若不然,則每點(diǎn)的次數(shù)均不小于6,即:6v<=2e.同時又由于每個面至少有三條邊,即:3f<=2e.將兩式代入毆拉公式得:2<=e/3 + 2e/3 - e = 0 ,產(chǎn)生矛盾!所以一個單且連通的平面圖必有一個點(diǎn)的次數(shù)不大于5.作:deg<=5. 給定一個地圖在每個國家里取一點(diǎn),若兩個國家有共同a/b/c/d(圖1).觀察所有以v'為起點(diǎn),點(diǎn)接點(diǎn)由若干條邊組成的路線,上面的點(diǎn)隔個涂上a和 c.如果沒有一條這樣的線路以v'"為終點(diǎn)的話,我們只用把這些路線上的a和c兩色互調(diào),便可以把v'的色改為c,仍維持四種顏色著色，把 v 涂上a色補(bǔ)回去,便知道原來的圖只需要四種顏色,與圖的選取產(chǎn)生矛 盾(圖1). 如果從v'至v'"有一條這樣的路線,便不可能從v"為起點(diǎn),有一條點(diǎn)接點(diǎn)由若干條邊組成的路線,上面的點(diǎn)隔個涂上b和d,終點(diǎn)是v"".于是用類似的推斷,亦產(chǎn)生矛盾(見圖2)! 情況2:v的次數(shù)是5,與v相連的五點(diǎn)v'/v"/v'"/v""/v'""各涂上色a/b/a/c/d(見圖3).像剛才的考慮一般,可以假定有一條點(diǎn)接點(diǎn)由若干條邊組成的路線,從v"走到v'"",上面的點(diǎn)隔個涂上b和d,也有一條點(diǎn)接點(diǎn)由若干條邊組成的路線,從v"走到v"",上面的點(diǎn)隔個涂上b和c.于是從v'至v""不會有這樣的路線,上面的點(diǎn)隔個涂上a和c;從v'"至v'""也不會有這樣的路線,上面的點(diǎn)隔個涂上a和d.把這些從v'出發(fā)的路線上的a和c二色互調(diào),把這些從v'"出發(fā)的路線上的a和d二色互調(diào),便可以把v'與v'"的色分別改為c和d,于是把v涂上a色補(bǔ)回去,便知道原來的圖只需用四種顏色,與圖的選取產(chǎn)生矛盾! 肯普以為他排除了全部可能情況,所以沒有找到反例.即是說,四色猜想給證實(shí)了.希五德指出的漏洞出現(xiàn)于最后一種情況,當(dāng)我們把那些從v'出發(fā)的路線上的a和c二色互調(diào)時,可能制造了一條從v'"至v'""的路線,上面的點(diǎn)隔個涂上a和d!(v'"-d-c-v'""  因此,當(dāng)我們再把a(bǔ)和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和它的相鄰點(diǎn)組成,他以為已經(jīng)證明了每一個都是"可約"的,但希五德指出了最后一個并不是"可約",故證明不完全.后來從事這方面研究的人還是循著這條路走,把那些并不"可約"的"無可避免"構(gòu)形再分解,試圖證明分解了的構(gòu)形變成"可約"的.這樣做可能導(dǎo)致一組個數(shù)很多的"無可避免"的構(gòu)形,曾經(jīng)一度大家以為約有一萬多個,其中有些還包含很多點(diǎn)的,即使運(yùn)用電子計算機(jī)去驗證一個這樣的構(gòu)形是否"可約",亦得花上100個小時.撇下儲存問題不理,單是計算也得花上100年左右!后來美國數(shù)學(xué)家哈肯與阿佩爾成功地把"無可避免"構(gòu)形數(shù)縮減至1478個,把驗算時間縮短至1200小時.在1976年,他們宣稱四色猜想是對的.文章在1977年發(fā)表,長達(dá)139頁,還附上電子計算機(jī)程序的微形膠片400頁!過了10年后,還有人對他們的證明提出質(zhì)疑,認(rèn)為存在著漏洞.哈肯與阿佩爾亦有回應(yīng).據(jù)他們說,那些漏洞都給補(bǔ)足了.對于四色猜想是否解答了,數(shù)學(xué)家的意見還是莫衷一是. 四色問題由肯普的證明至今已一百多年,究竟有多少人研究過他的方法,又有多少人親自動手去操作實(shí)踐一下他的方法的過程,不得而知.請有意為學(xué)之精神者認(rèn)真讀書.這是我親自從蕭教授的書上節(jié)選的,保證無誤.并希廣泛發(fā)表意見,以鼓勵本人繼續(xù)學(xué)習(xí). *這里的圖指原書希五德舉出的反例圖,該圖是塊地形圖,在電腦中很難畫.故本人經(jīng)認(rèn)真分析研究后選取用圖3表示.根據(jù)最少著色原則,他所舉的圖例可用四種顏色著色. 有關(guān)的圖另發(fā)。 |
回復(fù)此樓» 猜你喜歡
材料與化工求調(diào)劑
已經(jīng)有7人回復(fù)
-
304求調(diào)劑
已經(jīng)有3人回復(fù)
-
0817 化學(xué)工程 299分求調(diào)劑 有科研經(jīng)歷 有二區(qū)文章
已經(jīng)有12人回復(fù)
-
085600材料與化工調(diào)劑 324分
已經(jīng)有12人回復(fù)
-
286求調(diào)劑
已經(jīng)有10人回復(fù)
-
324分 085600材料化工求調(diào)劑
已經(jīng)有3人回復(fù)
-
317求調(diào)劑
已經(jīng)有6人回復(fù)
-
307求調(diào)劑
已經(jīng)有5人回復(fù)
-
求調(diào)劑
已經(jīng)有3人回復(fù)
-
求調(diào)劑，一志愿:南京航空航天大學(xué)大學(xué) ，080500材料科學(xué)與工程學(xué)碩，總分289分
已經(jīng)有3人回復(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ù)
|
先謝謝版主的夸獎。至于是否為資源帖，無所謂；不過，我得真誠地告訴網(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
|
看來第一個圖，還可用；缺點(diǎn)是大小寫字母有些混淆。畫第二圖： ......C--------A---------C----A ......|................................| ......|.........B(V" ...............|......|.........|......................| ....A(V')----V-----------------C(V"" ................|.......................... ...............D(V"" ................................圖 2.......................... 順便留給大家一個問題：在肯普的證明中，不論是情形1或2，為什么總存在某兩點(diǎn)沒有聯(lián)通對角鏈？您能否找出其理論根據(jù)？ [ Last edited by liufu on 2011-4-20 at 10:45 ] |
3樓2011-04-20 10:42:51
★
math105(金幣+1): 歡迎討論有價值的話題。 2011-04-20 23:03:33
math105(金幣+1): 歡迎討論有價值的話題。 2011-04-20 23:03:33
|
前兩個好用，第三個圖是有關(guān)希伍德的反例；不過我這里是9個點(diǎn)的反例圖。 |----------------------------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
5樓2011-04-29 12:03:18
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 liufu 的主題更新
| 5 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 321求調(diào)劑 +7 | 何潤采123 2026-03-18 | 7/350 |
|
|---|---|---|---|---|
|
|
[考研] 288求調(diào)劑 +6 | 于海海海海 2026-03-19 | 6/300 |
|
|
[教師之家] 焦慮 +9 | 水冰月月野兔 2026-03-13 | 13/650 |
|
|
|
[考研]
 271材料工程求調(diào)劑
+5
|
.6lL 2026-03-18 | 5/250 |
|
|
|
[考研] 一志愿武理材料305分求調(diào)劑 +5 | 想上岸的鯉魚 2026-03-18 | 6/300 |
|
|
|
[考研] 一志愿西南交大，求調(diào)劑 +4 | 材化逐夢人 2026-03-18 | 4/200 |
|
|
|
[考研] 280求調(diào)劑 +6 | 咕嚕曉曉 2026-03-18 | 7/350 |
|
|
|
[考研] 303求調(diào)劑 +4 | 睿08 2026-03-17 | 6/300 |
|
|
|
[考研] 301求調(diào)劑 +9 | yy要上岸呀 2026-03-17 | 9/450 |
|
|
|
[考研] 334求調(diào)劑 +3 | 志存高遠(yuǎn)意在機(jī)?/a> 2026-03-16 | 3/150 |
|
|
|
[考博] 26博士申請 +3 | 1042136743 2026-03-17 | 3/150 |
|
|
|
[考研] 277調(diào)劑 +5 | 自由煎餅果子 2026-03-16 | 6/300 |
|
|
|
[碩博家園] 湖北工業(yè)大學(xué) 生命科學(xué)與健康學(xué)院-課題組招收2026級食品/生物方向碩士 +3 | 1喜春8 2026-03-17 | 5/250 |
|
|
|
[考研] 本人考085602 化學(xué)工程 專碩 +16 | 不知道叫什么！ 2026-03-15 | 18/900 |
|
|
|
[考研] 26考研求調(diào)劑 +6 | 丶宏Sir 2026-03-13 | 6/300 |
|
|
|
[考博] 26申博 +4 | 八6八68 2026-03-16 | 4/200 |
|
|
|
[考研] 085600調(diào)劑 +5 | 漾漾123sun 2026-03-12 | 6/300 |
|
|
|
[考研] 330求調(diào)劑 +3 | ?醬給調(diào)劑跪了 2026-03-13 | 3/150 |
|
|
|
[考研] 工科材料085601 279求調(diào)劑 +8 | 困于星晨 2026-03-12 | 10/500 |
|
|
|
[考研] 289求調(diào)劑 +3 | 李政瑩 2026-03-12 | 3/150 |
|