 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 1036 | 回復(fù): 4 | |||
| 當前只顯示滿足指定條件的回帖，點擊這里查看本話題的所有回帖 | |||
[交流]
介紹四色問題的肯普證明（節(jié)選自《數(shù)學證明》、大連理工大學出版社 著 蕭文強）
|
|||
|
為方便朋友們的學習,下面將《數(shù)學證明》（大連理工大學出版社，著 蕭文強）一書中有關(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)于最后一種情況,當我們把那些從v'出發(fā)的路線上的a和c二色互調(diào)時,可能制造了一條從v'"至v'""的路線,上面的點隔個涂上a和d!(v'"-d-c-v'""  因此,當我們再把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)形變成"可約"的.這樣做可能導致一組個數(shù)很多的"無可避免"的構(gòu)形,曾經(jīng)一度大家以為約有一萬多個,其中有些還包含很多點的,即使運用電子計算機去驗證一個這樣的構(gòu)形是否"可約",亦得花上100個小時.撇下儲存問題不理,單是計算也得花上100年左右!后來美國數(shù)學家哈肯與阿佩爾成功地把"無可避免"構(gòu)形數(shù)縮減至1478個,把驗算時間縮短至1200小時.在1976年,他們宣稱四色猜想是對的.文章在1977年發(fā)表,長達139頁,還附上電子計算機程序的微形膠片400頁!過了10年后,還有人對他們的證明提出質(zhì)疑,認為存在著漏洞.哈肯與阿佩爾亦有回應(yīng).據(jù)他們說,那些漏洞都給補足了.對于四色猜想是否解答了,數(shù)學家的意見還是莫衷一是. 四色問題由肯普的證明至今已一百多年,究竟有多少人研究過他的方法,又有多少人親自動手去操作實踐一下他的方法的過程,不得而知.請有意為學之精神者認真讀書.這是我親自從蕭教授的書上節(jié)選的,保證無誤.并希廣泛發(fā)表意見,以鼓勵本人繼續(xù)學習. *這里的圖指原書希五德舉出的反例圖,該圖是塊地形圖,在電腦中很難畫.故本人經(jīng)認真分析研究后選取用圖3表示.根據(jù)最少著色原則,他所舉的圖例可用四種顏色著色. 有關(guān)的圖另發(fā)。 |
回復(fù)此樓» 猜你喜歡
290分調(diào)劑求助
已經(jīng)有4人回復(fù)
-
0703化學調(diào)劑，求導師收
已經(jīng)有12人回復(fù)
-
320分，材料與化工專業(yè)，求調(diào)劑
已經(jīng)有14人回復(fù)
-
求調(diào)劑
已經(jīng)有5人回復(fù)
-
070300化學354求調(diào)劑
已經(jīng)有9人回復(fù)
-
求調(diào)劑：085600材料與化工，考材科基，總分319
已經(jīng)有10人回復(fù)
-
本科211生物醫(yī)學工程085409求調(diào)劑339分
已經(jīng)有5人回復(fù)
-
313求調(diào)劑
已經(jīng)有5人回復(fù)
-
362求調(diào)劑
已經(jīng)有3人回復(fù)
-
化學工程085602 305分求調(diào)劑
已經(jīng)有27人回復(fù)
» 本主題相關(guān)價值貼推薦，對您同樣有幫助:
- 圖論方面的一個小問題
已經(jīng)有14人回復(fù)
- 求助：怎么證明這個數(shù)學式子？？
已經(jīng)有6人回復(fù)
- 求問導師資助證明
已經(jīng)有11人回復(fù)
- 關(guān)于導師資助證明有問題請教
已經(jīng)有8人回復(fù)
- 怎樣證明0和1之間沒有整數(shù)？
已經(jīng)有6人回復(fù)
- 本人考大連理工大學，分數(shù)已出，如何著手復(fù)試�。�
已經(jīng)有4人回復(fù)
- 求助解一道數(shù)學證明題
已經(jīng)有2人回復(fù)
- 有關(guān)數(shù)學期望的證明題
已經(jīng)有4人回復(fù)
- 一道關(guān)于商空間的證明題
已經(jīng)有13人回復(fù)
- “優(yōu)先出版”的問題？
已經(jīng)有7人回復(fù)
- 國家行政學院出版社-《公共基礎(chǔ)快速過關(guān)》
已經(jīng)有336人回復(fù)
- 代爾夫特理工大學 面試主要問什么？
已經(jīng)有7人回復(fù)
|
看來第一個圖，還可用；缺點是大小寫字母有些混淆。畫第二圖： ......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
|
先謝謝版主的夸獎。至于是否為資源帖，無所謂；不過，我得真誠地告訴網(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
★
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
5樓2011-04-29 12:03:18
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 320分，材料與化工專業(yè)，求調(diào)劑 +10 | 一定上岸aaa 2026-03-27 | 14/700 |
|
|---|---|---|---|---|
|
[考研] 334求調(diào)劑 +6 | Trying] 2026-03-31 | 6/300 |
|
|
|
[考研] 哈爾濱工業(yè)大學材料與化工專碩378求調(diào)劑 +3 | 塔比烏斯 2026-03-30 | 3/150 |
|
|
|
[有機交流] 考研調(diào)劑 +8 | watb 2026-03-26 | 8/400 |
|
|
|
[考研] 0703本科鄭州大學求調(diào)劑 +7 | nhj_ 2026-03-25 | 7/350 |
|
|
|
[考研] 318求調(diào)劑 +7 | 陳晨79 2026-03-30 | 7/350 |
|
|
|
[考研] 材料與化工304求B區(qū)調(diào)劑 +4 | 邱gl 2026-03-26 | 7/350 |
|
|
|
[考研]
 一志愿武漢理工，總分321，英一數(shù)二，求老師收留。
+11
|
nnnnnnn5 2026-03-25 | 11/550 |
|
|
|
[考研] 291求調(diào)劑 +5 | Y-cap 2026-03-29 | 6/300 |
|
|
|
[考研] 315求調(diào)劑 +4 | akie... 2026-03-28 | 5/250 |
|
|
|
[考研] 071000生物學求調(diào)劑，初試成績343 +7 | 小小甜面團 2026-03-25 | 7/350 |
|
|
|
[考研] 調(diào)劑 +3 | 好好讀書。 2026-03-28 | 3/150 |
|
|
|
[考研] 求調(diào)劑推薦 材料 304 +15 | 荷包蛋hyj 2026-03-26 | 15/750 |
|
|
|
[考研] 一志愿南師大0703化學 275求調(diào)劑 +4 | Ripcord上岸 2026-03-27 | 4/200 |
|
|
|
[考研] 復(fù)試調(diào)劑，一志愿南農(nóng)083200食品科學與工程 +5 | XQTJZ 2026-03-26 | 5/250 |
|
|
|
[考研] 求調(diào)劑 +6 | 林之夕 2026-03-24 | 6/300 |
|
|
|
[考研] 一志愿 南京郵電大學 288分 材料考研 求調(diào)劑 +3 | jl0720 2026-03-26 | 3/150 |
|
|
|
[考研] 334分 一志愿武理-080500 材料求調(diào)劑 +4 | 李李不服輸 2026-03-25 | 4/200 |
|
|
|
[考研] 材料專碩 335 分求調(diào)劑 +4 | 拒絕冷暴力 2026-03-25 | 4/200 |
|
|
|
[考研] 各位老師您好：本人初試372分 +5 | jj涌77 2026-03-25 | 6/300 |
|