话说四色问题——研究四色问题三十年之总结（一）

雷明85639720

话说四色问题（一）
——研究四色问题三十年之总结
雷  明
（二○一六年四月三十日）

目录：
（一）1、——15、
1、什么是四色问题                                 （4）
2、四色猜测的最早提出                             （4）
3、有关四色猜测最早提出的另一种说法               （5）
4、凯莱在数学界正式提出四色猜测的问题             （6）
5、坎泊的证明及赫渥特的否定                       （7）
6、四色猜测证明的第一次低潮                       （8）
7、所谓计算机证明了四色猜测                       （8）
8、四色猜测证明的第二次低潮                       （9）
9、互联网开通后四色猜测的手工证明又进入了高潮     （10）
10、用对平面图顶点的着色代替了对地图中区域的染色  （10）
11、坎泊在四色猜测证明中的贡献                    （11）
12、坎泊的颜色交换技只是一种图论运算              （11）
13、地图和平面图的不可免构形集                    （12）
14、地图的不可免集的证明                          （14）
15、平面图的不可免集的证明                        （14）
（二）16、——24、
16、把无穷问题变成了有究问题                      （15）
17、赫渥特图的4—着色方法之一（雷明的方法）       （17）
18、赫渥特图的4—着色方法之二（米勒和张彧典的方法）（18）
19、赫渥特为什么不能对他的图进行4—着色           （20）
20、赫渥特陷入了两种构形的无限转化的循环之中了     （22）
21、赫渥特图的可4—着色并不能代替四色猜测的证明   （24）
22、米勒图的着色方法一（雷明的方法）               （25）
23、米勒图的着色方法二（张彧典的方法）             （27）
24、另两种类型的5—轮构形                          （28）
（三）25、——30、
25、应该用不画图不着色的方法证明四色猜测           （30）
26、关于“同化”的理论并对四色猜测进行证明         （30）
27、米歇尔斯基操作是不会影响四色猜测的证明的       （33）
28、其他几种不画图不着色证明四色猜测的方法         （35）
    （一）用图的最小完全同态的亏格小于等于原图的亏格证明四色猜测的方法（35）
    （二）用多阶曲面上图的色数公式证明四色猜测的方法（36）
    （三）用平面图的欧拉公式直接证明四色猜测的方法 （37）
    （四）用米歇尔斯基操作法证明四色猜测的方法     （37）
    （五）用数学归纳法证明四色猜测的方法           （38）
    （六）用不存在最小五色地图证明四色猜测的方法   （40）
          用反证法进行证明：                       （40）
          用解方程方法进行证明：                   （40）
    （七）换一个角度去认识并证明四色猜测           （41）
29、具体的平面图着色色数的确定                    （42）
30、具体的地图着色时几种特殊情况的处理            （43）
    （一）“海洋国”的处理                         （43）
    （二）“国中之国”的处理                       （44）
    （三）“一国多地”的处理                       （44）
    （四）“三个以上国家相交于一点”的处理         （45）
    （五）“两国夹国”与“三国环国）的处理         （45）
    （六）特殊的南极洲的处理                      （46）
（四）31、——40、
31、关于统一地图着色规范的建议                    （46）
    （一）地图的以模式并不是一成不变的            （46）
    （二）关于统一地图着色规范的建议              （47）
32、关于“构形”的概念                            （47）
33、（5，5）和（5，6）都不是构形                   （49）
34、5—轮构形是不能用别的构形代替的               （51）
35、一个构形只能有一个待着色顶点                  （51）
36、关于“子构形”的问题                          （53）
37、关于图的不可免集的大小问题                    （54）
38、阿贝尔只是对2000个图进行了可4—着色的验证   （54）
39、阿贝尔“证明”的结论含乎不清                  （55）
40、世间只有人是最聪明的                          （56）
（五）40、——附录
41、把物理学中的“放电理论”和“电荷转移”理论用在图论中是不合适的（57）
42、阿贝尔《四色地图问题的解决》一文中矛盾百出    （61）
附：有关四色问题的几则趣事                         (65)

正文如下：
1、什么是四色问题：
四色问题就是四色猜测。四色猜测说的是：把平面或球面分成若干个区域，给每个区域各着以一种颜色，使得有公共边界的两区域不用同一颜色时，猜测最多四种颜色就够用了。一百六十多年来，人们企图证明这一猜测是否正确，但至今仍无结果。可人们通过大量的事实却说明了这一猜测是正确的，并且也找不出需要五种或五种以上颜色来着色的球面（或平面）地图。或许这一猜测就是正确的，是客观存在的。但在科学技术还不发达的时期，人们是不可能发现这个规律的，而只有在生产力和科学技术高度发达后，地图使用得更加广泛的近代，才有可能在对地图的着色过程中发现这个规律。作为一个猜测提了出来。猜测总归是猜测，必须要进行证明看其是否正确。这就引起了自问题的提出至今，一个半多世纪以来，无数数学工作者前赴后继的进行证明，但至今却没有最终结论。
2、四色猜测的最早提出：
四色猜测原来是1852年由英国的绘图员法朗西斯在绘制英国地图时提出来的，由于他不能证明其是否是真的，就请教他当时在上大学的弟弟弗内德里。其弟也不能证明，便于当年10月23日请教他的老师、当时很有名的数学家德•莫根。虽然莫根证明了平面地图中不存在五个国家（区域）两两均相邻的情况，但仍不能对法朗西斯提出的问题给以证明。因此，莫根就将此事写信告诉他的好友、大数学家和物理学家威兼•哈密顿，可惜的是哈密顿对此事并没有引起重视。但莫根并没有放松对这一问题的传播，现已发现有文字记载的一次传播是在1860年4月14日莫根所写的一篇书评。
在自四色问题的提出已经过去了二十八年后的1880年，已成为一名物理学家的弗内德里才在一个刊物上发表文章，说是大约在三十年以前，他还是德•莫根班里的一个学生时，是他的哥哥法朗西斯告诉了他地图四色问题的。时隔二十八年才总算弄明白了地图四色问题首先是谁提出来的，具体时间也只好以有具体日期的、由法朗西斯的弟弟费内德里请教他的老师德•莫根的1852年10月23日为准了。
3、有关四色猜测最早提出的另一种说法：
有关四色问题的提出，还有另外一种说法，即是在1840年由德国数学家莫比乌斯提出的。1840年莫比乌斯提出“五个王子问题”，说是一个国王对他的五个儿子说，他死后，把国家分成五个区域，一人一个区域，但又要求每个区域都要与其他四个区域有共同的边界。问如何来完成这件事。如果说这个问题的解不太明显，那么，从Heinrich Tietze针对这一问题提出的“五座宫殿问题”中，就容易知道这“五个王子问题”是无解的。“五座宫殿问题”是：国王又要求五个儿子各在自已的区域内修建一座宫殿，并且要在每两座宫殿间都修上道路，且又要求各条道路互不相交。
很明显，这是一个在5个顶点间，两两顶点均有边相邻的K5图。但K5图画在平面上，边与边不相交是无法完成的。这也就说明了以上的“五个王子问题”与“五座宫殿问题”都是无解的。这一问题虽然与四色问题是风马牛不相及的事，但却说明了K5图不是平面图，即K5图画到平面上时，一定有在顶点以外边与边相交叉情况的（如图1）。也说明了平面上（或地图中）是根本不存在五个顶点（或区域）是两两都相邻的情况的。虽然不能说地图所需的色数就等于两两均相邻的国家数的最大团值，但这一情况的确又是与四色问题是有关的问题。所以就有了关于四色问题提出的这一种说法。但大家公认的，却还是：四色猜测的最早提出者，应该是1952年英国的法朗西斯，而不是1840年德国的莫比乌斯。

4、凯莱在数学界正式提出四色猜测的问题：
四色猜测由于莫根的不断传播，在时隔二十六年后的1878年6月13日的伧敦数学会上，英国数学家凯莱于6月17日正式询问四色问题是否得到解决。第二年的英国皇家地理学会上，凯莱再次提出这一问题，并在《皇家地理学会会报》上发表。于是，四色问题才引起了人们的足够重视，吸引了很多的专业和非专业的人士去研究它，企图给以证明。
5、坎泊的证明及赫渥特的否定：
1879年7月13日，律师出身的坎泊在《自然》杂志上宣布他解决了四色问题，证明了四色猜测是正确的。在凯莱的建议下，当年坎泊就把他的成果发表在《美国数学杂志》的第二卷上。1880年泰特又根据另一个现在看来是并不正确的猜想“每个平面三次图都有哈密顿圈”给出了四色猜想的另一个“证明”。一时间，人们以为四色难题就这样得到了解决，攻克四色难题的热度也就慢慢的降了下来。

不料，11年后，到了1890年，在牛津大学读书的学生赫渥特构造了一个图，由于赫渥特和坎泊两人当时都不能对该图进行4—着色，坎泊也就只得承认自已“弄错了”，从而也就否定了坎泊在1979年对四色猜测的证明，四色问题又成了一个有待解决的难题。赫渥特图如图2。与赫渥特“否定”坎泊一样，同样的，在过了66年后的1946年，塔特构造了一个没有哈密顿圈的平面三次图，也就否定了泰特1880年的“证明”。到了1972年，Saatybn仍构造了同赫渥特图一样图，来对坎泊的证明进行否定。
此后，人们都称赫渥特图是“反例图”，并且说，这并不是说赫渥特图是不可4—着色的，它并不是四色猜测的反例，而是坎泊证明方法的反例。但在二十世纪末以前，所有文献资料上也没有看到过一个赫渥特图4—着色的模式。反而赫渥特又采用了坎泊的方法得到了一个所谓的“五色定理”。事实上，赫渥特的图是可以4—着色的。在1990年前后及其以后的时间里，分别有爱好者雷明，张彧典，董德周，米勒，刘福，郑敏等人都能用手工对赫渥特图进行4—着色（见后面的17和18），还有中央民族大学（北京）的许寿椿教授使用电子计算机，用自已所编的“算法”（程序），也对赫渥特图进行了4—着色。但不管是用手工，还是用计算机，在对赫渥特图着色时，所用的方法仍然离不开坎泊所创造的颜色交换技术（见后面的11和12）。
6、四色猜测证明的第一次低潮：
自赫渥特“否定”了坎泊的证明后，对四色难题的证明就转入了低潮时期，几乎停止不前。直到过了四十九年后，才有人对四色猜测的证明又用手工开始进行研究。从1939年的富兰克林起，到1976年的Jean Mayer止，共三十七年，多少杰出的数学家，前赴后继，才证明了从有22个国家的地图到有95个国家的地图，四色猜测都是正确的。但却都没有得出“任何”地图都是可4—着色的结论。
7、所谓计算机证明了四色猜测：
1976年6月，美国的阿贝尔和哈根宣布他们用电子计算机“证明”了四色猜测。他们构造了近2000个图，用高速运转的电子计算机一一进行了验证，占用了1200多个机器小时，证明了这些图都是可4—着色的（他们把这近2000个图叫做“可约构形的不可免集”。关于构形和不可免构形以及构形可约，请见后面的11）。从而认为四色猜测是正确的（阿贝尔等人宣布证明后，当地邮局还特别制作了叫做“四色足矣”的邮戳以纪念）。但数学界对此还有不同的看法，因为该证明正如阿贝尔所说的“证明的正确性不靠计算机是无法检验的”（阿贝尔《四色地图问题的解决》一文），其证明正确与否，是没有人可以对其进行检验的。
后来又过了近20年，1993年由托马斯、罗伯逊又根据阿贝尔的思路，把那个有近2000个构形的可约构形的不可免集的元素缩小到了633个。检验633个图是否可4—着色，所用的机器时间仅管缩短很多，但问题仍没有得到根本性的变化，仍然是不用计算机也是无检验其是否可靠的。阿贝尔的证明虽然有人已经发现他们的十几处错误，但阿贝尔的回复说这都是枝节问题，不影响他们证明的结论。在随后的时间里，他们不断的修改自已的计算机程序，并报告有关结果，但他们的程序一直都没有被他人重复运行检验过。对于这个“证明”，“大部分的数学家都持很高的怀疑态度，并对这个证明很不满意”，并由此“引起了关于什么是数学证明的许多讨论”。
8、四色猜测证明的第二次低潮：
1976年以后，用手工对四色猜测的证明，又进入了一个底潮阶段。几乎所在的有关数学的杂志刊物和有关的部门，对于四色问题等难题研究的论文，都是拒登的，找各种理由进行推辞。有关部门中也没有设立专门的研究和审理四色问题的专业部门。
9、互联网开通后四色猜测的手工证明又进入了高潮：
在进入二十世纪以后，互联网的开通，又给爱好者们研究四色问题搭建了一个更好的平台，可以随意的在网上进行交流，并发表自已的有关论文。研究四色问题等难题的爱好者也就越来越多了。各爱好者从不同的角度出发，用不同的方法都在对四色猜测展开了各种证明，爱好者在网上表现得非常用活跃。当然网上也有反对用手工研究四色问题的，但他们都是一些盲目的认为计算机真的“证明”了四色猜测的追随者。他们跟本就不知道计算机是人创造人，也不知道计算机完全是在人的指挥下去工作的，更不知道离开了人，电子计算机只是一堆废铁。
10、用对平面图顶点的着色代替了对地图中区域的染色：
地图四色问题，主要是对地图中的区域（面）的着色，在还没有“图论”这门新生学科之前，坎泊，赫渥特等，他们都是直接用地图的术语来研究的，很难以看懂。后来由于人们对四色问题的研究，不断的提出新问题，解决新问题，一门新兴的科学——图论，迅速的发展起来了。用图论的观点看，实际上地图也是图，且是一个平面图，又是3—正则的平面图。地图中每一个顶点都连有三条边，这就是“三界点”，就是平时所说的“三不管地区”，故名曰3—正则图。给地图的面上的着色，实际上就是对地图的对偶图——极大平面图——的顶点着色。所以从1946年塔特否定泰特的错误证明起，对四色猜测的证明就彻底的由对地图的面的着色，转到了对平面图的顶点的着色上来了。的确，这一转变，研究时也比较方便，图也容易看明白。
11、坎泊在四色猜测证明中的贡献：
坎泊在对四色猜测进行研究时，首先提出了“正规地图”的概念，规定正规地图中不含“国中之国”的情况，也不存在一国分处多处的情况，也不存在三个以上的国家在一点相邻的情况；还首先提出了“构形”，“不可免构形”，与“构形可约”的概念；也首先提出和证明了任何地图中至少存在着一个区域的相邻区域数小于等于5，即任何地图中至少存在以下四种“不可免构形”中的一种：即｛一国与两国相邻，一国与三国相邻，一国与四国相邻，一国与五国相邻｝。这就是地图的“不可免构形集”。同时坎泊也证明了不存在所有区域都与六个区域相邻的地图和任何地图中都不存在五个区域两两都相邻的情况。
坎泊还创造了颜色交换技术，即在一条由两种颜色构成的色链上，交换两种颜色所着的位置，就可以使链中的任何顶点的颜色得到改变。这一颜色交换技术用在对构形中的待着色顶点的着色上是很成功的。把构形中的待着色顶点能着上图中已使用过的四种颜色之一时，就叫“构形可约”。坎泊就是用了这一颜色交换技术，证明了一国与两国相邻的构形，一国与三国相邻的构形，一国与四国相邻的构形都是“可约的”，而对一国与五国相邻的构形的证明却没有进行到底，这才有后来的赫渥特，构造了赫渥特图，对其证明进行了“否定”。
12、坎泊的颜色交换技只是一种图论运算：
在前面的5中已经说到，自从1890年赫渥特构造了赫渥特图以后，人们都认为赫渥特图是坎泊证明方法的反例，并不是四色猜测本身的反例。现在我们就分折一下什么是坎泊的证明方法。在11中已提到了坎泊创造的颜色交换技术，可以说这也是图的一种“运算”，与拆边、去顶、收缩等运算相同，只是一种运算方法而已。同一种运算方法，可以使用在不同的地方，而不能说某种运算只能使用在某处，而不能使用在别处。颜色交换技术也是同样的，若交换的链是由轮构形中轮沿顶点上两对角顶点的颜色所构成的，该链又在两对角顶点间是不连通的，那么交换的结果就可以从轮构形的轮沿顶点上空出一种颜色，给待着色顶点着上。这是交换技术的一种应用。若把颜色交换技术用在交换与轮构形不相邻的链的交换上，当然也是可以的，以达到改变链中任一个顶点的颜色的目的。这又是交换技术的另一种应用。
赫渥特图中的5—轮构形不能从轮沿顶点进行交换空出颜色，那么，想办法从别的非轮沿顶点进行交换后，创造可以从轮沿顶点交换的条件，再空出颜色给待着色顶点着上还不行吗（见后面的16，17和18）。坎泊没有想到在这样的情况下如何的使用他的颜色交换技术，难道就说明这一交换技术就是错的吗。既然是错的，那么赫渥特为什么又要用它来证明所谓的“五色定理”呢。
13、地图和平面图的不可免构形集：
由于地图（3—正则图）的对偶图是一个极大的平面图，每一个面均是三角形面。地图中每一个区域在对偶图中对应的都是一个顶点，对偶图中的每一个顶点与其周围的顶点构成的都是一个轮。所以坎泊的地图的不可免构形集｛一国与两国相邻的构形，一国与三国相邻的构形，一国与四国相邻的构形，一国与五国相邻的构形｝，在地图的对偶图中对应的就是由2—轮构形，3—轮构形，4—轮构形和5—轮构形构成的构形集｛2—轮构形，3—轮构形，4—轮构形，5—轮构形｝。这就是平面图的不可免集。
但上面的不可免集并不完全，因为平面图中还有顶点度为1的1—轮（如悬挂顶点和两个顶点的K2）和顶点度为0的0—轮（如孤立顶点K1），所以平面图的不可免集应是｛0—轮构形，1—轮构形，2—轮构形，3—轮构形，4—轮构形，5—轮构形｝，共有六个元素（如图3）。


由于地图中有“国中之国”，这样的国家在地图的对偶图中就是一个1—度顶点，即是一个1—轮；一个地图也可以只有一个国家或无国家可区别的一个区域，其对偶图就是一个孤立顶点，也就是一个0—轮。这样，地图的不可免集就成了有六个元素的｛一国与零国相邻的构形，一国与一国相邻的构形，一国与两国相邻的构形，一国与三国相邻的构形，一国与四国相邻的构形，一国与五国相邻的构形｝（如图4）。
两个不可免构形集的元素个数是相同的，都是6。这两个不可免构形集分别都是可以证明的。证明方法如下面的14和15。
14、地图的不可免集的证明：
地图的不可免构形集是通过欧拉公式证明的：不含“国中之国”的地图中，国家数为f＝∑fi（i≥2，i是各国边界的条数，也是同边界条数的国家的个数）；各个国家边界条数的总和是2e＝∑（i•f）i（i≥2），所以地图中的边数e＝｛∑（i•f）i｝/ 2（i≥2）；由于地图中的顶点全是3—度顶点，应有的3v＝2e的关系，所以地图中的顶点（三界点）数v＝｛∑（i•f）i｝/ 3（i≥2）。地图是一个平面图，把以上的v，f，e代入平面图的欧拉公式v＋f＝e＋2中得；｛∑（i•f）i｝/ 3＋f＝∑fi＝｛∑（i•f）i｝/ 2＋2，化简后得∑（6－i）fi＝12。即4f2＋3f3＋2f4＋f5―f7―2f6―3f9―……―（6－i）fn＝12；第四项后全是负数，公式右边又等于12，是正数。要保证公式左边也是正值时，公式左边前四项中就必须至少有一项是大于0的。这就说明了不含“国中之国”的地图中至少有一个国家的边界条数（或相邻国家数）是小于等于5的。因此也就产生了上述｛一国与零国相邻的构形，一国与一国相邻的构形，一国与两国相邻的构形，一国与三国相邻的构形，一国与四国相邻的构形，一国与五国相邻的构形｝的地图的不可免集。
15、平面图的不可免集的证明：
平面图的不可免构形集是用图论中的理论证明的：顶点数v≥3的极大平面图，顶点与边数之间的关系是e≤3v－6，则各顶点度的总和是2e≤6v－12，各顶点的平均度是d≤2e /v≤（6v－12）/ v，当顶点数v趋近于无穷大时，平均度的极限是lim（6v－12）/ v＝6，各顶点度的平均值6只是一个极限值，永远也是不会等于6的。这也就说明了顶点数v≥3的极大平面图中至少有一个顶点的度是小于等于5的。然而所有的非极大图的边数一定是比同顶点数的极大图要少的，图中就更应该有顶点度是小于等于5的顶点了。因此也就产生了上述由｛0—轮构形，1—轮构形，2—轮构形，3—轮构形，4—轮构形，5—轮构形｝构成的平面图的不可免集。
（转下贴）

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

,,,,,,,,,

雷明85639720

,,,,,,,,,

雷明85639720

,,,,,,,,,,

雷明85639720

,,,,,,,,k,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，