| 查看: 1008 | 回复: 4 | |||
| 当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖 | |||
[交流]
介绍四色问题的肯普证明（节选自《数学证明》、大连理工大学出版社 著 萧文强）
|
|||
|
为方便朋友们的学习,下面将《数学证明》（大连理工大学出版社，著 萧文强）一书中有关肯普的错误证明介绍给大家. 要明白肯普的证明错在哪里与后来希五德怎样修正,较清晰地叙述是采用普通的图论语言.一个图由某些点和相连其中一些点的边组成,每个点的次数是以该点为一个端点的边的数目.如果每两点顶多只有一条边相连,又没有一点自己与自己有边相连,这个图叫做单图.如果任意两点必有一条点接点由若干条边合起来的路线连着,这个图叫做连通图.如果全部点和边都在一平面上,而且任意两条边没有相交点[端点不计],这个图叫做平面图.平面图的边,把平面分为若干份,每份叫一个面.设有v个点,e条边和f个面,著名的殴拉公式v+f-e=2把这三个数字联系了起来.设平面图是单图且为连通图,则可证明必有一点的次数不大于5.利用反证法:设若不然,则每点的次数均不小于6,即:6v<=2e.同时又由于每个面至少有三条边,即:3f<=2e.将两式代入殴拉公式得:2<=e/3 + 2e/3 - e = 0 ,产生矛盾!所以一个单且连通的平面图必有一个点的次数不大于5.作:deg<=5. 给定一个地图在每个国家里取一点,若两个国家有共同a/b/c/d(图1).观察所有以v'为起点,点接点由若干条边组成的路线,上面的点隔个涂上a和 c.如果没有一条这样的线路以v'"为终点的话,我们只用把这些路线上的a和c两色互调,便可以把v'的色改为c,仍维持四种颜色着色，把 v 涂上a色补回去,便知道原来的图只需要四种颜色,与图的选取产生矛 盾(图1). 如果从v'至v'"有一条这样的路线,便不可能从v"为起点,有一条点接点由若干条边组成的路线,上面的点隔个涂上b和d,终点是v"".于是用类似的推断,亦产生矛盾(见图2)! 情况2:v的次数是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'出发的路线上的a和c二色互调,把这些从v'"出发的路线上的a和d二色互调,便可以把v'与v'"的色分别改为c和d,于是把v涂上a色补回去,便知道原来的图只需用四种颜色,与图的选取产生矛盾! 肯普以为他排除了全部可能情况,所以没有找到反例.即是说,四色猜想给证实了.希五德指出的漏洞出现于最后一种情况,当我们把那些从v'出发的路线上的a和c二色互调时,可能制造了一条从v'"至v'""的路线,上面的点隔个涂上a和d!(v'"-d-c-v'""  因此,当我们再把a和d二色互调时,只是把v'""的d色换作d色,把v'"的a色换作d色,对v来说仍然要涂上第五色!他给了一个反例(见图3).固然这是一个局部反例,说明了原来的证明行不通,却不是全局反例,因为他的图(*)是可用四种颜色着色的.希五德还指出肯普的想法,可以搬来证明五种颜色是足够了,读者愿意试证明吗?肯普的想法虽然行不通,却是一个很有意思的想法.他的战术是找出一组"无可避免"的构形,意思是说任何单且连通的平面图肯定包含至少一个这类构形作为里面的一部分,然后设法证明每一个这类构形都是"可约"的,即它不能在四色猜想的最小反例里出现.肯普的证明所选的"无可避免"的构形,由那些次数小于5和它的相邻点组成,他以为已经证明了每一个都是"可约"的,但希五德指出了最后一个并不是"可约",故证明不完全.后来从事这方面研究的人还是循着这条路走,把那些并不"可约"的"无可避免"构形再分解,试图证明分解了的构形变成"可约"的.这样做可能导致一组个数很多的"无可避免"的构形,曾经一度大家以为约有一万多个,其中有些还包含很多点的,即使运用电子计算机去验证一个这样的构形是否"可约",亦得花上100个小时.撇下储存问题不理,单是计算也得花上100年左右!后来美国数学家哈肯与阿佩尔成功地把"无可避免"构形数缩减至1478个,把验算时间缩短至1200小时.在1976年,他们宣称四色猜想是对的.文章在1977年发表,长达139页,还附上电子计算机程序的微形胶片400页!过了10年后,还有人对他们的证明提出质疑,认为存在着漏洞.哈肯与阿佩尔亦有回应.据他们说,那些漏洞都给补足了.对于四色猜想是否解答了,数学家的意见还是莫衷一是. 四色问题由肯普的证明至今已一百多年,究竟有多少人研究过他的方法,又有多少人亲自动手去操作实践一下他的方法的过程,不得而知.请有意为学之精神者认真读书.这是我亲自从萧教授的书上节选的,保证无误.并希广泛发表意见,以鼓励本人继续学习. *这里的图指原书希五德举出的反例图,该图是块地形图,在电脑中很难画.故本人经认真分析研究后选取用图3表示.根据最少着色原则,他所举的图例可用四种颜色着色. 有关的图另发。 |
回复此楼» 猜你喜欢
初试 317
已经有3人回复
-
279分求调剂 一志愿211
已经有15人回复
-
286求调剂
已经有4人回复
-
279求调剂
已经有4人回复
-
求调剂
已经有3人回复
-
求调剂
已经有3人回复
-
299求调剂
已经有3人回复
-
330求调剂0854
已经有3人回复
-
299求调剂
已经有6人回复
-
286分人工智能专业请求调剂愿意跨考！
已经有5人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 图论方面的一个小问题
已经有14人回复
- 求助：怎么证明这个数学式子？？
已经有6人回复
- 求问导师资助证明
已经有11人回复
- 关于导师资助证明有问题请教
已经有8人回复
- 怎样证明0和1之间没有整数？
已经有6人回复
- 本人考大连理工大学，分数已出，如何着手复试！？
已经有4人回复
- 求助解一道数学证明题
已经有2人回复
- 有关数学期望的证明题
已经有4人回复
- 一道关于商空间的证明题
已经有13人回复
- “优先出版”的问题？
已经有7人回复
- 国家行政学院出版社-《公共基础快速过关》
已经有336人回复
- 代尔夫特理工大学 面试主要问什么？
已经有7人回复
5楼2011-04-29 12:03:18
|
先谢谢版主的夸奖。至于是否为资源帖，无所谓；不过，我得真诚地告诉网友，随便在百度搜搜，是不会搜到的；不信您试试！现在我画第一个图： ........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，为什么总存在某两点没有联通对角链？您能否找出其理论根据？ [ 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
|
前两个好用，第三个图是有关希伍德的反例；不过我这里是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
