 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 1003 | 回復(fù): 4 | |||
[交流]
介紹四色問題的肯普證明（節(jié)選自《數(shù)學(xué)證明》、大連理工大學(xué)出版社 著 蕭文強(qiáng)）
|
|
為方便朋友們的學(xué)習(xí),下面將《數(shù)學(xué)證明》（大連理工大學(xué)出版社，著 蕭文強(qiáng)）一書中有關(guān)肯普的錯(cuò)誤證明介紹給大家. 要明白肯普的證明錯(cuò)在哪里與后來希五德怎樣修正,較清晰地?cái)⑹鍪遣捎闷胀ǖ膱D論語言.一個(gè)圖由某些點(diǎn)和相連其中一些點(diǎn)的邊組成,每個(gè)點(diǎn)的次數(shù)是以該點(diǎn)為一個(gè)端點(diǎn)的邊的數(shù)目.如果每兩點(diǎn)頂多只有一條邊相連,又沒有一點(diǎn)自己與自己有邊相連,這個(gè)圖叫做單圖.如果任意兩點(diǎn)必有一條點(diǎn)接點(diǎn)由若干條邊合起來的路線連著,這個(gè)圖叫做連通圖.如果全部點(diǎn)和邊都在一平面上,而且任意兩條邊沒有相交點(diǎn)[端點(diǎn)不計(jì)],這個(gè)圖叫做平面圖.平面圖的邊,把平面分為若干份,每份叫一個(gè)面.設(shè)有v個(gè)點(diǎn),e條邊和f個(gè)面,著名的毆拉公式v+f-e=2把這三個(gè)數(shù)字聯(lián)系了起來.設(shè)平面圖是單圖且為連通圖,則可證明必有一點(diǎn)的次數(shù)不大于5.利用反證法:設(shè)若不然,則每點(diǎn)的次數(shù)均不小于6,即:6v<=2e.同時(shí)又由于每個(gè)面至少有三條邊,即:3f<=2e.將兩式代入毆拉公式得:2<=e/3 + 2e/3 - e = 0 ,產(chǎn)生矛盾!所以一個(gè)單且連通的平面圖必有一個(gè)點(diǎn)的次數(shù)不大于5.作:deg<=5. 給定一個(gè)地圖在每個(gè)國家里取一點(diǎn),若兩個(gè)國家有共同a/b/c/d(圖1).觀察所有以v'為起點(diǎn),點(diǎn)接點(diǎn)由若干條邊組成的路線,上面的點(diǎn)隔個(gè)涂上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)隔個(gè)涂上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)隔個(gè)涂上b和d,也有一條點(diǎn)接點(diǎn)由若干條邊組成的路線,從v"走到v"",上面的點(diǎn)隔個(gè)涂上b和c.于是從v'至v""不會(huì)有這樣的路線,上面的點(diǎn)隔個(gè)涂上a和c;從v'"至v'""也不會(huì)有這樣的路線,上面的點(diǎn)隔個(gè)涂上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)時(shí),可能制造了一條從v'"至v'""的路線,上面的點(diǎn)隔個(gè)涂上a和d!(v'"-d-c-v'""  因此,當(dāng)我們再把a(bǔ)和d二色互調(diào)時(shí),只是把v'""的d色換作d色,把v'"的a色換作d色,對(duì)v來說仍然要涂上第五色!他給了一個(gè)反例(見圖3).固然這是一個(gè)局部反例,說明了原來的證明行不通,卻不是全局反例,因?yàn)樗膱D(*)是可用四種顏色著色的.希五德還指出肯普的想法,可以搬來證明五種顏色是足夠了,讀者愿意試證明嗎?肯普的想法雖然行不通,卻是一個(gè)很有意思的想法.他的戰(zhàn)術(shù)是找出一組"無可避免"的構(gòu)形,意思是說任何單且連通的平面圖肯定包含至少一個(gè)這類構(gòu)形作為里面的一部分,然后設(shè)法證明每一個(gè)這類構(gòu)形都是"可約"的,即它不能在四色猜想的最小反例里出現(xiàn).肯普的證明所選的"無可避免"的構(gòu)形,由那些次數(shù)小于5和它的相鄰點(diǎn)組成,他以為已經(jīng)證明了每一個(gè)都是"可約"的,但希五德指出了最后一個(gè)并不是"可約",故證明不完全.后來從事這方面研究的人還是循著這條路走,把那些并不"可約"的"無可避免"構(gòu)形再分解,試圖證明分解了的構(gòu)形變成"可約"的.這樣做可能導(dǎo)致一組個(gè)數(shù)很多的"無可避免"的構(gòu)形,曾經(jīng)一度大家以為約有一萬多個(gè),其中有些還包含很多點(diǎn)的,即使運(yùn)用電子計(jì)算機(jī)去驗(yàn)證一個(gè)這樣的構(gòu)形是否"可約",亦得花上100個(gè)小時(shí).撇下儲(chǔ)存問題不理,單是計(jì)算也得花上100年左右!后來美國數(shù)學(xué)家哈肯與阿佩爾成功地把"無可避免"構(gòu)形數(shù)縮減至1478個(gè),把驗(yàn)算時(shí)間縮短至1200小時(shí).在1976年,他們宣稱四色猜想是對(duì)的.文章在1977年發(fā)表,長達(dá)139頁,還附上電子計(jì)算機(jī)程序的微形膠片400頁!過了10年后,還有人對(duì)他們的證明提出質(zhì)疑,認(rèn)為存在著漏洞.哈肯與阿佩爾亦有回應(yīng).據(jù)他們說,那些漏洞都給補(bǔ)足了.對(duì)于四色猜想是否解答了,數(shù)學(xué)家的意見還是莫衷一是. 四色問題由肯普的證明至今已一百多年,究竟有多少人研究過他的方法,又有多少人親自動(dòng)手去操作實(shí)踐一下他的方法的過程,不得而知.請有意為學(xué)之精神者認(rèn)真讀書.這是我親自從蕭教授的書上節(jié)選的,保證無誤.并希廣泛發(fā)表意見,以鼓勵(lì)本人繼續(xù)學(xué)習(xí). *這里的圖指原書希五德舉出的反例圖,該圖是塊地形圖,在電腦中很難畫.故本人經(jīng)認(rèn)真分析研究后選取用圖3表示.根據(jù)最少著色原則,他所舉的圖例可用四種顏色著色. 有關(guān)的圖另發(fā)。 |
回復(fù)此樓» 猜你喜歡
274求調(diào)劑
已經(jīng)有4人回復(fù)
-
328求調(diào)劑，英語六級(jí)551，有科研經(jīng)歷
已經(jīng)有10人回復(fù)
-
328求調(diào)劑，英語六級(jí)551，有科研經(jīng)歷
已經(jīng)有7人回復(fù)
-
材料專業(yè)求調(diào)劑
已經(jīng)有5人回復(fù)
-
一志愿天津大學(xué)化學(xué)工藝專業(yè)（081702）315分求調(diào)劑
已經(jīng)有10人回復(fù)
-
344求調(diào)劑
已經(jīng)有7人回復(fù)
-
一志愿985，本科211，0817化學(xué)工程與技術(shù)319求調(diào)劑
已經(jīng)有7人回復(fù)
-
271材料工程求調(diào)劑
已經(jīng)有4人回復(fù)
-
材料專碩英一數(shù)二306
已經(jīng)有4人回復(fù)
-
294求調(diào)劑材料與化工專碩
已經(jīng)有4人回復(fù)
» 本主題相關(guān)價(jià)值貼推薦，對(duì)您同樣有幫助:
- 圖論方面的一個(gè)小問題
已經(jīng)有14人回復(fù)
- 求助：怎么證明這個(gè)數(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ù)
|
先謝謝版主的夸獎(jiǎng)。至于是否為資源帖，無所謂；不過，我得真誠地告訴網(wǎng)友，隨便在百度搜搜，是不會(huì)搜到的；不信您試試！現(xiàn)在我畫第一個(gè)圖： ........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
|
看來第一個(gè)圖，還可用；缺點(diǎn)是大小寫字母有些混淆。畫第二圖： ......C--------A---------C----A ......|................................| ......|.........B(V" ...............|......|.........|......................| ....A(V')----V-----------------C(V"" ................|.......................... ...............D(V"" ................................圖 2.......................... 順便留給大家一個(gè)問題：在肯普的證明中，不論是情形1或2，為什么總存在某兩點(diǎn)沒有聯(lián)通對(duì)角鏈？您能否找出其理論根據(jù)？ [ Last edited by liufu on 2011-4-20 at 10:45 ] |
3樓2011-04-20 10:42:51
★
math105(金幣+1): 歡迎討論有價(jià)值的話題。 2011-04-20 23:03:33
math105(金幣+1): 歡迎討論有價(jià)值的話題。 2011-04-20 23:03:33
|
前兩個(gè)好用，第三個(gè)圖是有關(guān)希伍德的反例；不過我這里是9個(gè)點(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ā)表 | |
|---|---|---|---|---|
|
[考研] 一志愿天津大學(xué)化學(xué)工藝專業(yè)（081702）315分求調(diào)劑 +10 | yangfz 2026-03-17 | 10/500 |
|
|---|---|---|---|---|
|
[考研] 070303一志愿西北大學(xué)學(xué)碩310找調(diào)劑 +6 | d如愿上岸 2026-03-12 | 9/450 |
|
|
|
[考研] 一志愿吉林大學(xué)材料學(xué)碩321求調(diào)劑 +3 | Ymlll 2026-03-18 | 5/250 |
|
|
|
[考研] 354求調(diào)劑 +3 | Tyoumou 2026-03-18 | 5/250 |
|
|
|
[考研] 一志愿西南交大，求調(diào)劑 +4 | 材化逐夢人 2026-03-18 | 4/200 |
|
|
|
[考研] 265求調(diào)劑 +3 | 梁梁校校 2026-03-17 | 3/150 |
|
|
|
[考研] 268求調(diào)劑 +6 | 簡單點(diǎn)0 2026-03-17 | 6/300 |
|
|
|
[考博] 26博士申請 +3 | 1042136743 2026-03-17 | 3/150 |
|
|
|
[考研] 268求調(diào)劑 +7 | 好運(yùn)連綿不絕 2026-03-12 | 8/400 |
|
|
|
[考研] 085601求調(diào)劑 +4 | Du.11 2026-03-16 | 4/200 |
|
|
|
[考研] 【0856】化學(xué)工程（085602）313 分，本科學(xué)科評(píng)估A類院�；瘜W(xué)工程與工藝，誠求調(diào)劑 +7 | 小劉快快上岸 2026-03-11 | 8/400 |
|
|
|
[考研] 085600材料與化工求調(diào)劑 +5 | 緒幸與子 2026-03-17 | 5/250 |
|
|
|
[考研] 275求調(diào)劑 +4 | 太陽花天天開心 2026-03-16 | 4/200 |
|
|
|
[考研] 機(jī)械專碩325，尋找調(diào)劑院校 +3 | y9999 2026-03-15 | 5/250 |
|
|
|
[考研] 304求調(diào)劑 +3 | 曼殊2266 2026-03-14 | 3/150 |
|
|
|
[考研] 321求調(diào)劑 +5 | 大米飯！ 2026-03-15 | 5/250 |
|
|
|
[考研] 一志愿哈工大材料324分求調(diào)劑 +5 | 閆旭東 2026-03-14 | 5/250 |
|
|
|
[考研] 304求調(diào)劑 +7 | 7712b 2026-03-13 | 7/350 |
|
|
|
[考研] 考研調(diào)劑 +4 | 芬達(dá)46 2026-03-12 | 4/200 |
|
|
|
[考博] 福州大學(xué)楊黃浩課題組招收2026年專業(yè)學(xué)位博士研究生，2026.03.20截止 +3 | Xiangyu_ou 2026-03-12 | 3/150 |
|