新浪博客

论肯普证明地图四色猜想的漏洞与错误

2010-01-21 19:04阅读:

很多图论书都谈到Heawood仅举一反例就一票否定了肯普的证明,同时也指出了肯普证明的漏洞。这漏洞到底是什么?除了漏洞,还有没有错误?是一般的错误还是智慧闪光的错误?
Heawood图是肯普“交错着色法”的反例,还是四色的反例?漏洞是交错法,还是肯普证明的指导思想?百余年来,专家学者著书立说,至今仍扑朔迷离;Heawood图成了四色问题的百摹大三角区。好色愚公不到长城非好汉---给H图4着色不惜卿卿性命。好色骗你没商量,不骗白不骗。四色美女潜台词:误会、悟会!
研究四色问题不懂H图就不能悟出四色的真谛。到头来,四色问题的证明还是一场大大的误会。究竟是怎样的误会,虽属近代也要考古一番。
一、专著的各种论述
湖南科学技术出版社1988年4月出版的美国人M•卡波边柯与J•莫鲁卓合著,聂祖安翻译的《图论的例和反例》书中说“他(指坎泊)认为他用下面的方法已经证明了猜测,即用‘证明’:如果一个顶点V与五个其它用四种颜色着色的顶点邻接,那么总能空出诸颜色之一用来给V着色。他用了邻接顶点交错着色的道路(尽管在他的原始论文中一切都是用了地图的术语来说明的),交换这些道路上各顶点的颜色,便可空出一种颜色给V。”

《图论导引》一书在提到坎泊证明中的“缺陷”所在时说:“1890年,Heawood发表了一篇题为Map colouring theorem(地图染色定理)的文章,在该文中他构造一个反例指出Kempe关于四色问题的解决方法中的‘缺陷’,即当区域X被5个区域环绕” 的这种构形没有经过证明,就得出该构形的区域X是可以着上其外围区域已用过的四种颜色之一是有缺陷的。Kempe坚信,前面关于4个区域环绕X情形的证明方法同样适用于5个区域环绕X的情形。这就是他的证明的关键部分,也是证明失败的地方。”赫渥特还构造了一个地图,用以证明“有5个区域环绕X,并且4种颜色都用来给这些区域染色了”的区域X是“不能”用其外围区域已用过的颜色着上的。
《图论导引》一书中还说:“Heawood的例子只是Kempe方法的一个反例,而不是四色猜测的反例”。
有多少四色问题的爱好者,亲自动手,对H图进行认真地四着色,结果获成功。但这仍是徒劳!
首先我指出,Heawood图不是四色的反例!难道还有人怀疑希伍德的着色能力吗?他真的不能给他的图4着色?希伍德花了整整11年的时间,专为肯普的证明量身订做了反例图;何等了得!我们还有些人见到书上的反例图,自认为一百年来没有人会给它4着色;于是爱不释手耗去大量时间。这其实是书上的图---只空出一个顶点没有着色---暗示误导多少好色愚公。“四色”是插在古老数学上的一朵花,就像下凡的仙女,引无数愚公孩子的姑姑热情地款待。
希伍德图由25个区域组成,是个极简单容易着色的图。利用我博客的三角图公理(【四色问题简介】中)的着色法,很轻易得到解决!
二、漏洞与错误
我认为漏洞之一是:肯普利用“交错着色”来减少图的着色数的方法。
请看下图:如图1,图中有:2到5的b—y链,也有:2到4的b—g链;按肯普的指导思想,于是不会有1到4的r—g链、也不会有3到5的r—y链。如此,用肯普的交换颜色法,可以把r色替换出来给点V着上。
但您接下来却遇到了麻烦:当您交换其中一条链(不通的)的颜色后,却把另一条不通的链联通了,最终使您交换颜色不成功!
请看图2,从1开始交换r---- g,可看原图(图外标注颜色);往上直到点7。如此交换后,使得由点3开始的r ---y链(红、黄3—6—7 —5)成了联通的;最终交换不成功!穷图而【漏洞】现。这足以说明,肯普的方法不是永远好用的!尽管您还可以用其它的交换法使之成功。故此,可称为漏洞之一。
一百多年来,人们只认识到肯普证明存在的漏洞,这得归功于希伍德。但聪明的希伍德又利用肯普的证明方法证明了五色定理。这就不要人云亦云了。五色定理有没有错误,不是因为地图四色就够了它才有问题;要想充分认识这个问题,使认识更上一层楼,那还必须再深入到肯普证明的指导思想中去。不入虎穴焉得虎子!漏洞只是认识肯普证明的初级阶段。






















…/----------/--/--(7)g\---\---------------\
…|…………/…/....|…...\...\..............\
…|………/…/......|…....\...\.............|
…|……/…../…/---b---\....\...\……….....|
…|……|….|…|…/….\....\...\...\...………|
…|……|….\--r----g----r------y-\.|………..|
…|……|……...\...|..\.|…\.../.|.|………..|
…|……|..../------b----y----g-\.|.|……....|
…|……|.….|………\....|…/…..||.|…......|
…|……\…..|....../.--R1--\....||.|………..|
…|………\..|.../..……..|…..\.||./….…...|
…|……/---5Y-----------V-------B2----\.....|
…|…./………\........./……\.../………\....|
…|….|…/--------4G---------R3--\--\...|….|
…|….|…|………...|....\....|…...|…|.|...|
…|….|…|…..-----Y-----R----B…..|…|.|….|
…|….|…|…./…….|..\..|.\./…\..|..|.|….|
…|….|…|…|……..R-----G--Y---G--|..|.|...|
…|….|…|…|…./…|..\..|../…/...|..|.|….|
…|….|…|…|../….|-----B---/…….|..|.|….|
..|...|..|..|./....|.....\--------\|..|.|...|
…\....\....|/......\----------------Y(6)--/
……(8)B(b)------------------------------/……图1
.
…/----------/--/--(7)r\---\---------------\
…|…………/…/....|…...\...\..............\
…|………/…/......|…....\...\.............|
…|……/…../…/---b---\....\...\……….....|
…|……|….|…|…/….\....\...\...\...………|
…|……|….\--g----r----g------y-\.|………..|
…|……|……...\...|..\.|…\.../.|.|………..|
…|……|..../------b----y----r-\.|.|……....|
…|……|.….|………\....|…/…..||.|…......|
…|……\…..|....../.--g1--\....||.|………..|
…|………\..|.../..……..|…..\.||./….…...|
…|……/---5Y-----------V-------B2----\.....|
…|…./………\........./……\.../………\....|
…|….|…/--------4G---------R3--\--\...|….|
…|….|…|………...|....\....|…...|…|.|...|
…|….|…|…..-----Y-----R----B…..|…|.|….|
…|….|…|…./…….|..\..|.\./…\..|..|.|….|
…|….|…|…|……..R-----G--Y---G--|..|.|...|
…|….|…|…|…./…|..\..|../…/...|..|.|….|
…|….|…|…|../….|-----B---/…….|..|.|….|
..|...|..|..|./....|.....\--------\|..|.|...|
…\....\....|/......\----------------Y(6)--/
……(8)B(b)------------------------------/……图2.

我凑时间,将希伍德反例图改造一下,一共九个点;对于肯普的漏洞用此图来分析也较简便,请参考。
|
/-------------c---------\---\
/ / | \ \
/ / | B(V')|
/ / | | |
/ / A(V') | |
/ / | | |
B--------- D(V''')-----------V--------------| |
| \ | \ | |
\ \-------------------- C(V'')\ / |
\ | A(V'') / |
\ | / / |
\--------------------d----/--/----------/
新造希伍德(heawood)九点反例图 .
肯普的证明的主要思想是这样的,假定四色猜想不对,可找一个最小的反例,意思是说有些图需要用至少五种颜色,在这些图中选一个点数是最小的;它既是一个单且连通的平面图,必有一点V的次数小于等于5;把V及以它为端点的边抹掉,剩下的图可用四种颜色重新着色.
当V的次数小于四时,很显然仍需原来的四色着色;当V的次数等于4,用'二色互调'法一次就可解决了.问题出在肯普研究的最后一种情形:
V的次数等于5.设与V相连的五点V'/V'/V''/V''/V'''分别涂上A/B/A/C/D色.肯普接着还用上述方法,调换了V'和 V''的着色,分别改为C和D.肯普没有遇到麻烦,顺利给V涂上了原来的四色之一A色.这样按他自己的假设,没有找到反例.即是说四色猜想是对的.希伍德十年磨一剑,仅一个反例,一票否决了肯普的证明.肯普找不到第五色,而希伍德则量身订做,专门给肯普设计了一个图(自然地图),偏偏必须着第五色.书上说是局部反例,因为实际上这个图也是四色的.(全局反例谁也找不到!)这就使我们明白了肯普的漏洞在哪里.就在'二色互调'上!这里的二色互调,必须结合上下文来理解,不能从字面上去理解.
请看新造反例图,由2至4有B----C通链,由2至5有B----D通链;而由1至4(A---C链)不通,由3至5(A---D链)不通。于是当你交换1---4链的颜色后,3---5链则就变成了联通的了!也是使你不能交换成功。
希伍德的反例图就是让'二色互调'失效.好历害的反例图呀,值得后人研讨!
我认为“漏洞”之二是:肯普证明的指导思想,这也是他证明的错误之一。
就肯普的指导思想本身来说是正确的。用它来证明除此以外的任何问题都没有毛病;也不会有人说他有错。但是,肯普偏偏用它来证明四色猜想那就大错而特错了!这话听来奇怪,让我慢慢道来。
有人说,肯普对他坚信那条信念没有证明,所以给Heawood找出漏洞带来机会。写到这,想起了小册子【趣味的图论问题】。它的第57页是关于“五色定理”的证明。那里对肯普坚信的,也是他证明的指导思想间接地有所察觉(请参考)。
利用反证法思想:若不这样,即(不能用外围四色之一给中心顶点着色)外围(至少4个)顶点没有一条点接点不连通的链;则外围每两点间都有联通的链!如此,连同中间顶点一起,那就会出现完全图K(5);而它是非平面图(对此有不清楚的地方,请看我的有关博客文章)。
K(5)是非平面图,这已是不争的定理。有的书上叫欧拉(1707---1783)定理,也有的书上叫该定理的推论。用该定理做指导思想,根本就不需要(对其)证明。你只关注欧拉的生卒年限,就可搞清楚。肯普是知道这个定理的,他不需要去证明!要想知道这个定理是什么意思,有耐性的网友去看【地图四色猜想命题面对面】。“K(5)是非平面图'意思很明显它等价于着五色及以上的图是非平面图;它的逆否命题与其等价:平面图的色数小于5。即平面图的色数小于等于4.这就是四色猜想的数学描述。
从表面来看,欧拉定理与四色猜想面目全非,其实用“DNA”鉴定一下,他们是“同一个人”。
原来肯普证明的指导思想就是四色猜想!麻烦就来自这里。这等于用四色猜想去证明四色猜想。在逻辑上叫循环论证。希伍德用肯普的这一思想去证明“5色定理”是舍本逐末的证明。捡了芝麻丢了西瓜!就是一种倒退,明显的倒退!还有的人说什么离“四色”仅是一步之差,寄“四色证明”于“五色定理”!且类比与陈氏的哥德巴赫猜想证明。用四色定理去证明5色定理,再用5色定理去证明四色定理。这就是数学史上著名的长达百年的循环论证。有兴趣的网友请看我的博客【数学史上著名的跨世纪循环论证】以及对五色定理的质疑、人类误会五色百余年。
三、四色问题是个跨世纪的问题
以上我指出了肯普证明的错误要害之处!不是他有没有证明的“缺陷”。百余年来人们长期没有解决这一问题有两个原因:一是开始没有引起重视。一位教授在给学生上课时,偶尔提起这一问题;他竟要当堂给大家解答出来-------结果挂了黑板!二是后来当凯利把问题正式提出来的时候,由于许多一流的数学家都接触到四色问题而没有成效,于是人们则谈虎色变。
龙之心在评论黎鸣的文章时说,摩根(1806---1871)证明了“地图着五色是不可能的”。这是不对的。实际是,在他还没出生之前的18世纪由欧拉早就给证明了!说摩根和汉密尔顿都知道欧拉定理是正确的。从此以后人们由谈虎色变到谈“色”色变。真正潜下心来研究四色问题的人少了,在一定范围来说,四色问题的研究已经走入了地下。
把我们的研究转入到这个层次来认识,是四色问题研究的新的里程碑!只有找到肯普的错误所在,我们才能明确研究的方向!
1878年Cayley把四色问题公诸于世,他还不清楚欧拉定理能解决这个问题。19世纪提出的问题,人们都习惯想用以后研究的定理来解决;谁曾想18世纪的定理就好使!“命题面对面”就是跨世纪研究的开始;当然并不排除用以后研究的定理也能解决四色问题!人类对四色问题研究的误会也是跨世纪的。因此跨世纪的研究很有必要!要穿越时空隧道去寻找四色问题的解决途径。

我的更多文章

下载客户端阅读体验更佳

APP专享