数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 1004|回复: 5

四色猜测的历史评述和最终证明(第四稿)(二)

[复制链接]
发表于 2019-8-21 10:43 | 显示全部楼层 |阅读模式
本帖最后由 雷明85639720 于 2019-10-9 06:56 编辑

四色猜测的历史评述和最终证明(第四稿)(二)
英文标题:Historic Review and Final Proof of Four Colour Conjecture(4CC)
雷  明
(陕西金堆城钼业公司退休高级工程师   邮编:710100
Email:lm85639720@163.com
(二○一九年八月十日)
(接上贴)

22、无任何环形链的H—构形转型交换次数一定有限的理论证明:
无任何环形链的构形,在连续转型交换时,一定会分别在两个方向转型的第20次转型之前(包括第20次),图就一定会转化成为一个可以连续的移去两个同色的K—构形而可约。否则,图将是一个无穷转型交换也空不出颜色的图。但这却十在是不可能的事,因为无穷转型交换也空不出颜色的敢峰—米勒图类的构形,其中不但含有经过围栏顶点的A—B环形链,而且还含有不经过围栏顶点的C—D环形链,且A—B链和C—D链都是轴对称分布的,而现在这里所研究的对象(无任何环形链的H—构形)中,却是任何环形链也没有的构形,且A—B链和C—D链也不是轴对称分布的。

虽然1935年由Kittell给出了一个无任何环形链的轴对称的H—构形(如图9,其中a图是地图形式,b、c两图是两种不图画法的原图a的对偶图),但其“裸图”(即未着色时的图)也只有一个对称轴,且不是中心对称的;而敢峰—米勒图“裸图”却是有五个对称轴(即张彧典先生所谓的“十折对称”)的图,且是中心对称的。所以无任何环形链的H—构形,决不可能是可以无穷的转型交换下去而空不出颜色的构形。两个方向的转型交换,一定都是可以在20次转形交换之前,变成一个可以连续的移去两个同色的K—构形的。再进行两次空出颜色的交换,可以连续的移去两个同色,即可解决问题(见后面第24节的图27和图28)。

由于转型是可以向不同的两个方向进行的,假设一个构形向两个方向转型时,都是在第20次转化成了可以连续的移去两个同色的K—构形,那么,两个第19次之内(包括两个第19次)就有39个H—构形。把顺时针转型第19次后所得到的构形(因为第19次所得的图仍是H—构形,而第20次后的图就成了K—构形了(如图10)),再进行逆时针转型时,一定是在第40次转型后,图就会转化成一个可以连续的移去两个同色的K—构形(同样的,把逆时针转型第19次后所得到的构形再进行顺时针转型时,也会得到同样的结果),再进行两次空出颜色的交换,就可以给待着色顶点着上图中已用过的四种颜色之一,共计42次交换。
设构形逆时针转型的次数是X,顺时针转型的次数是Y,从上面的结果可以看出,对于任何无环形链的H—构形,都有X≤40,Y≤40和X+Y≤40的关系。再进行两次空出颜色的交换,共计交换总次数则是:X+2≤42,Y+2≤42和X+Y+2≤42。这就是由一个已知的构形构造转型交换次数不超过42次的不同构形的原理。
当然在转型过程中,若所得到的图中含有经过围栏顶点的环形链时,也可以交换环形链内、外的任一条相反链,使图变成K—构形,提前结束转型。
23、几个需要交换20次以上才能空出颜色的构形:

我们先给出一个逆时针转型时总交换次数是21次的构形(如图11,a),读者可以验证一下,是不是需要21次交换。再把这个构形进行顺时针转型,在第7次交换时就空出了颜色,那么第5次交换就是一个可以连续的移去两个同色的K—构形,则前4次交换所得的图分别是CDC型、ABA型、DCD型和BAB型的H—构形。对这些图再进行逆时针转型时,就是分别需要总交换次数是22次、23次、24次和25次的构形。图11,b就是逆时针转型时,需要25次交换才能空出颜色给待着色顶点的构形。
请注意,图11的这两个构形中都含有环形的C—D链,是可以用断链法很快解决问题的。为什么我们不这样去作,而要进行多达20次以上的连续转型交换呢?是因为张彧典先生不但把所有含有A—C和A—D两条相交叉链的构形统统都定义为H—构形,而且又把除了敢峰—米勒图类构形以外的其他H—构形也都统统叫做Z—构形的,并且认为统统都得用转型交换的方法来解决。所以我们所构造出来的图中虽然也含有环形链,也不去用断链交换法去解决,仍把它看成是Z—构形,而用连续的转型交换法进行解决的。这几个图连续转型交换的总交换次数都大于20,这就说明了张先生所说的Z—构形只有15类和最大的总交换次数不大于16的结论是错误的。
24、无任何环形链的H—构形转型交换次数一定有限的实践验证:
我们可以仿照敢峰先生构造终极图(即埃雷拉图)的办法,先画一个非常一般的不含连通链的H—构形,然后进行转型交换,每交换一次,都要人为的在平面图范围内再构造成H—构形。直到在平面图范围内不可能再构造成H—构形,图成为可约的可以连续的移去两个同色的K—构形为止。

图12是两个一般的无环形链的H—构形,左右结构正好是相反的,实际上同一个构形,所以我们只要研究图12,a就可以了。
现在我们对图12,a进行逆时针转型交换如下:
第一步,对图12,a从顶点1开始交换B—D链,得到的图13中虽然已生成了从顶点3到顶点5的连通的B—C链,但图却转化成了一个DCD型的H—构形,并且已经是一个可以连续的移去两个同色D的K—构形了。这一点可以从第二步转形交换得到的图14中没有形成从顶点1到顶点3的连通链可以看出。

第二步,对图13从顶点5开始交换D—A链,得到的图14中没有生成从顶点1到顶点3的连通链D—B,应该说问题已经可以解决。但在平面图范围内还可以构造出从顶点1到顶点3的D—B连通链(如图15),这是一个ABA型的H—构形。

第三步,对图15从顶点2开始交换A—C链,得到的图16中也没有生成从顶点4到顶点1的连通链A—D,问题也应得到解决。同样的,在平面图范围内也还是可以构造出从顶4到顶点1的连通的A—D链的(如图17),这是一个CDC型的可以连续的移去两个同色C的K—构形,而不再是H—构形了。
第四步,对图17从顶点5交换C—B链,得到的图18中虽没有生成从顶点2到顶点4的连通链C—A,但在平面图范围内再不可能构造从顶点2到顶点4的连通链C—A了,因为其前面有一条连通的相反色链B—D在阻隔着,C—A链是不可能通过的。很明显的是一个只有一条连通的B—D链的K—构形了。

第五步,对图18再从顶点2交换C—A链,就连续的移去了图16中的两个同色C,把C给待着色顶点V着上(如图19)。着色结速。

以上只进行了三次转型交换,加上最后的两次交换,共计是五次交换。这就是无环形链的H—构形的最大交换次数。以上是对图12按逆时针转型交换的,若按顺时针转型交换时,也会得出同样的结论(如图20到图26)。请读者自已也再试一试。
顺时针转型也只进行了三次转型交换,加上最后的两次交换,共计也是五次交换。两个方向的转型交换得出相同的结果,这就说明无环形链的H—构形的最大交换次数的确是不大于5的。如果把图12的任意图变成极大图时,则交换的次数将会更少。这就从对构形的着色实践上验证了无环形链的H—构形转型交换时的最大交换次数一定是“有限的”,这个“有限”的上界是5,最大也决不会超过42次。



对图9,c的轴对称的无环形链的H—构形,进行转型交换(如图27),第4次转型得到一个可以连续的移去两个同色B的构形(如图27,d),再交换两次,空出了B(如图7,f),共计6次交换,远小于42次。




但该图却在第3次转型后,形成了具有环形链的构形(如图27,c和图28,a),然后按有环形链的构形去解决,5次交换就可解决问题。如果把该图某一个方向的第3次转型后的图(如图27,c)再进行相反方向的转型时,则总共只要9次交换就可以解决问题,距上界42次仍相差很远。
25、除了有环形C—D链的九点形构形仍是H—构形外,其他的九点形构形都是K—构形:
把图4中加粗的曲线链变成单边时,图就成了九点形构形(如图29),而图9,c的轴对称无环形链的构形变成九点形构形则是图28,b。可以看出,图29,a、图29,c和图28,b均变了可以连续的移去两个同色B的K—构形;而只有图29,b仍是H—构形(有环形C—D链的H—构形,赫渥特图就可以简化成图29,b),不可能连续的移去两个同色B,只能通过交换C—D环形链内、外的任一条A—B链后,图才能变成K—构形而可约。

然而这些九点形构形中却都含有连通且相交叉的A—C链和A—D链。这一现象再一次说明了连通且相交叉的A—C链和A—D链只是构成H—构形的必要条件,而并非是充分条件。没有它,不可能构成H—构形,但有了它的构形却不一定就都是H—构形。
26、平面图的着色流程:
图30就是平面图的4—着色流程图。
首先把着色时可能遇到的待着色顶点分为染色困局顶点和非染色困局顶点。非染色困局顶点用坎泊链法(即坎泊已用过的交换法或空出颜色的交换法),染色困局顶点用非坎泊链法(即坎泊没有使用过的颜色交换法)。非染色困局的顶点包括度是小于等于4的顶点和围栏顶点占用颜色数小于等于3的顶点。其他的围栏顶点占用了4种颜色的待着色顶点,不管其是不是H—构形,都按染色困局顶点对待。然后再按各种染色困局的解决办法分别解决。

27、四色猜测是正确的:
现在各种情况下的不可免H—构形都是可约的了,加上坎泊早已证明了是可约的K—构形,平面图的任何不可免构形就都是可约的了,平面图的四色猜测也就得到了证明是正确的。当然地图的四色猜测也就是正确的了。从提出至今已有一百六十七年历史的地图四色猜测,就可以上升为地图四色定理了。结束这一个半世纪的证明历史了。
28、电子计算机是不能证明四色猜测的:
1976年,美国的阿贝尔等用高速运转的电子计算机,花了1200个机上小时,对近2000个平面图进行了4—着色。于是就宣布他们用计算机“证明了”四色猜测(请注意,他们这里只是用了“证明了”一词,并没有说明“证明”的结论是什么,四色猜测道底是正确呢,还是不正确,没有明确的说法)。一时轰动了全世界,美国的邮政业还专门发行了“四色足矣!”的纪念邮票,为电子计算机的发展应用做了一次免费的广告宣传。前面我们已经说过了,平面图有无穷多个,四色问题的研究对象也是无穷的,证明四色猜测不能只对一个个的平面图进行着色,因为永远也是着不完的。所以说计算机再快,着过的图再多,也还是有限的,是个别的。与我们用手工对图的着色没有什么区别。
由于计算机是人创造的,就决定了它必须要人去控制和操作,它才能进行工作,它的工作完全是在人的控制之下进行的。没有人,它就相当于一堆废铁,什么也不是。所以说,人比计算机是聪明的,人还不能办到的事,计算机也是办不到的。但人可以把自已想要办的事,编成程序,让计算机去执行。必竟计算机的效率比人要高得无比。人可以把着色的方法写好,教给计算机,让它代替人对图去进行着色。但计算机却没有人脑的思维能力,它是不可能代替人对任何一个命题去进行证明的。正象计算机可以解一元二次方程,但它却不会知道一元二次方程一定有两个根一样。它只会按人教给它的解一元二次方程的求根公式去一折不扣的执行。人把公式给错了,它也就计算错了,它是决没有修正错误的能力的。所以说,计算机如果出错了,归根到底还是人出错了。可是现在大多数人还一直认为,人不能解决的四色问题,却被电子计算机解决了,“计算机比人还聪明”。悲哀呀!
29、坎泊的颜色交换技术的三种作用:
通过以上的研究可以看出,坎泊的颜色交换技术共有三种作用:
一是从围栏顶点中空出一种颜色给待着色顶点的作用,坎泊的证明中就只用了这一种作用;
二是断链的作用,使连通的A—C链和A—D链断开,构形成为K—构形,为下一步空出颜色的交换创造条件。我们在解决有环形链的构形时,就是用了这种作用;
三是转型的作用,我们在解决无任何环形链的构形时,也就是用了这种作用的。这种作用的交换,也可以用在除了敢峰—米勒图类以外的任何构形上。比如1992年,米勒就是用转型交换给赫渥特图在赫渥特原着色的基础上进行4—着色的(一次转型,就可使图变成可以连续的移去两个同色的K—构形,再进行两次空出颜色的交换,就可空出两个同色给待着色顶点着上。但同一种方法,当他用在敢峰—米勒图上时,却失败了)。
30、三种交换法:
在坎泊对K—构形的证明中,所交换的链都是对角链,所以把坎泊的证明方法也可以叫对角链法;我们在证明有环形链的H—构形中,所交换的链都是邻角链,所以也可以叫邻角链法;在证明无任何环形链的H—构形中,所交换的B—D链和B—C链,既是对角链,又是邻角链,所以只能叫转型交换法。
31、对角链和邻角链:
从某一条链的属性(即链中的两种颜色在围栏顶点中的位置)来分,有对角链和邻角链之分。对角链是由围栏的某一组对角顶点的两种颜色所构成的色链;邻角链则是由围栏顶点中的某两个相邻顶点的两种颜色所构成的色链。
32、连通链和非连通链:
从某对角链与待着色顶点是否可以构成“环”来分,有连通链和非连通链之分。对角链+待着色顶点是一个环时,是连通链;对角链+待着色顶点不是一个环时,是非连通链。连通的对角链是不能交换的,而只有非连通的对角链才可以交换,是可以空出颜色给待着色顶点的。邻角链不存在连通与不连通的问题。
33、环形链与非环形链:
从某邻角链是否是环形链来分,有环形链与非环形链之分。我们在对H—构形分类时,就是按A—B和C—D两种邻角链是否是环形而把H—构形分为有环形链类和无环形链类两大类。邻角链不管是环形的还是非环形的,都是可以交换的。交换邻角链则是可以断链的。如在含有环形链的H—构形中,分别交换了A—B链或C—D链,都可以使两条相交叉的A—C链和A—D链断开,构形成为K—构形而可约。
34、        相反链,相邻链和相同链:
从两条以上的链的相互关系上来分,有相反链,相邻链和相同链之分。
① 链中两种颜色均不相同的两条链链,叫相反链。一对相反链只能是两条。因为总共只有四种颜色,每条链中各有两种,共占有四种,所以一对相反链只能是两条。如A—B链和C—D链就是一对相反链。四种颜色所能构成的相反链,只有三对。相反链是不能相互穿过的,因为两条相反链中没有共同的颜色。我们在对H—构形进行分类和解决有环形链的构形时,就用到了相反链A—B链和C—D链不能相互穿过的这一性质。
② 链中的两种颜色有一种相同,另一种不同的两条链,叫相邻链。一组相邻链只能是三条,也因为总共只有四种颜色,每一种颜色都只能与其他三种颜色的顶点分别构成三种含有同一种颜色的色链。如B—C链,B—D链和A—B链就是有共同颜色B的一组相邻链。断链交换中,所断开的A—C链和A—D链以及所交换的A—B链也是有共同颜色A的一组相邻链。相邻链是可以相互穿过的,因为它们有共同颜色的顶点。我们在解决有环形链的构形时的断链交换,就是用到了相邻的A—C链,A—D链和C—D链三者间两两可以相互穿过的这一性质。
③ 链中两种颜色都相同的两条链叫做相同链。两条相同链一定是不连通的。在有环形链的H—构形中,环形链A—B(或C—D)两侧并与环形链呈相反链的两条C—D(或A—B)链就是相同链。我们在解决有环形链的构形时的断链交换,也用到了相同链A—B(或C—D)是位于环形链C—D(或A—B)的两侧而不连通的这一性质。
35、结束语:
世界上的任何问题,只要有了人,困难再大,都是可以解决的。而且解决的办法也不是只有一种,而是从不同的角度出发,就有不同的解决办法。四色问题的证明也不例外。它从提出到现在,已经穿越了一个半世纪之多的时空,从英伦三岛蔓延到全世界,最终还是要解决的。我们在本文中只是用了坎泊创造的颜色交换技和使用过的求不可免构形的可约性的方法进行了举例,说明猜测是可以证明的。其他的方法还有笔者雷明创造的不可同化道路法,米歇尔斯基操作法,泰特猜想法,哈拉里的最小完全同态法,极大图的数学归纳法,公式推导法,拓扑法或赫渥特多阶曲面上地图着色公式法等等。所有这些,都是人在起主导作用的,电子计算机是不可能办到的。电子计算机只能是在人把各种着色的方法编成程序输入计算机,再把要着色的图也输入计算机后,它才能按人的意志去给图进行着色。如果人编的程序错了,它也就着错了,一点也不会偏离的。所以说人是起主导作用的。


雷  明
二○一九年八月十日于长安

注:此文的初稿已于二○一九年六月三日在《中国博士网》上发表过,网址是:

修改稿也于二○一九年六月十一日在《中国博士网》上发表过,网址是:

最终稿也于二○一九年七月十一日在《中国博士网》发表过,网址是:

此第四稿也于二○一九年八月二十一日在《中国博士网》上发表过,网址是:





本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-3-29 10:11 , Processed in 0.067383 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表