数学中国

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

四色猜测证明方法的创新

[复制链接]
发表于 2019-8-16 15:15 | 显示全部楼层 |阅读模式
本帖最后由 雷明85639720 于 2019-8-26 23:15 编辑

四色猜测证明方法的创新
雷  明
(二○一九年八月十六日)
(我在这里发不上图,请到《中国博士网》中去看)

我们把5—轮构形的5个围栏顶点已占用了四种颜色的构形统一叫做“广义的染色困局”。在遇到这样的“染色困局”时,可以不管其是否是H—构形,都可以用相同的方法进行处理。现在以BAB型的“染色困局”举例如下:
1、如果是含有经过了围栏顶点的环形链,也不管是A—B链还是C—D链(如图1和图2),都可以在环形链内或外任意交换与环形链呈相反色链的链(即“断链交换”),使得A—C链或A—D链均成为不连通的(已连通的变得不连通,不连通的则仍旧不连通),使图成为可约的构形。再进行一次或两次“空出颜色”的交换即可空出四种颜色之一给待着色顶点V。

2、如果不含有经过围栏顶点的环形链,也不管是什么情况,先看从一个B色顶点到其对角顶点是否有连通的B—D链或B—C链:
㈠ 若有这条连通链(如图3),则一定没有从峰点A到C或D的A—C(或A—D)连通链,则从A或C(或D)开始交换A—C链或A—D链,就可空出A或C(或D)给待着色顶点V(如图4或图5);
㈡ 若没有这条连通链(如图6),则交换B—D链或B—C链后,再看有没有新生成从另一个B色顶点到其对角顶点的B—C连通链或B—D连通链:

① 若没有生成B—C(或B—D)链通链(如图7),则从另一个B色顶点开始交换与其对角顶点的颜色构成的B—C链或B—D链,可连续的移去两个同色B,给待着色顶点V着上B(如图8);

②  若生成了B—C(或B—D)连通链(如图9),则继续对新的类型的“染色困局”施行同方向的“转型交换”,一定可以在有限的42次交换之内空出颜色给待着色顶点V的(这可以单独的给以证明)。

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

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


附:回答张彧典先生的42次颠倒的证明问题
雷  明
(二○一九年八月十七日)
(在这里我发不上图,请到《中国博士网》中去看)

③ 无任何环形链的构形:构形中A—B链和C—D链均不能交换,现在也就只能先交换一条关于B的链,先移去一个B,使构形转型了。对于BAB型的构形,从左B交换了B—D链后,成为DCD型;从右B交换了B—C链后,成为CDC型。然后再看转型后的构形,是否已成为可以连续的移去两个同色D(或C)的K—构形,或者成为以上两种有环形链的可约的H—构形。若仍不可约时,就继续进行同方向的转型,一定是可以在有限次的交换内,空出颜色给待着色顶点的。这种构形及其解法,就是我国的张彧典先生的第八构形及其解决办法。这种“转型交换”的交换次数为什么是“有限的”,在后面第22节到第24节将给以证明。
19、5—轮构形转型交换的周期是20:
5—轮构形有5个围栏顶点,围栏顶点共占用了4种颜色。进行连续的转型交换,使得构形又转型成为BAB型,峰点A又回到原来的5—轮最上方一个顶点时,需要的交换次数是4和5的最小公倍数20次。这时,围栏各顶点的颜色均与最初转型前的颜色完全相同。再继续进行转型交换时,构形将以每20次交换为一个周期,无穷的转型下去,永远也不能空出颜色来。无论是进行逆时针方向转型,还是进行顺时针方向转型,都有同样的特点。
20、敢峰—米勒图类构形虽是无穷转型也空不出颜色的图,但却是可4—着色的:

有没有无穷次转型交换也空不出颜色来的构形呢?有。这就是敢峰—米勒图类的构形(如图7)。该类构形的确是无穷次的转型交换也空不出颜色的,两个方向的转型均是如此。许多学者的研究都说明了该图的转型过程的确是无穷循环的,循环的周期是20。但由于该类构形中有一条经过了围栏顶点的环形的A—B链(见图7,b中的外圈加粗边),可以交换A—B环形链内、外的任一条C—D链,使图变成K—构形而可约。该构形虽是无穷转型的,但却是可以4—着色的。
我们只知道敢峰—米勒图是在1992年前后,分别由我国的敢峰先生和英国的米勒构造出来的。但米勒解决不了该图是否可约的问题,而敢峰先生却用交换环形的A—B链内、外的任一条C—D链的方法解决了该图的可约性问题,所以我把该图叫做敢峰—米勒图。后来看到张彧典先生在网上发文介绍,说敢峰—米勒图实际上早在1921年就由埃雷拉(A•Errera)给出过,并且在1935年已由Kittell对该图进行了4—着色,同样也是走了交换A—B环形链外侧的C—D链才使构形变得可约的,移去了两个同色B。由于这一情况我们知道得较晚,已经把敢峰—米勒图叫了出去,并且已经叫习惯了,所以仍叫它为敢峰—米勒图(看来以后还得要把该图叫做埃雷拉图或Errera—图了)。
张彧典先生介绍Kittell解决埃雷拉图(E—图)的文章一篇叫《对已部分4—染色地图的一组操作》作者是Irving•Kittell,发表时间是1935年;另一篇叫《坎泊再研究》,作者是Joan Hutchinson and Stan Wagon(琼•哈钦森和斯坦•马车),发表时间是1998年。两文说的Kittell解决的办法都与敢峰先生的解决办法是完全相同的。
后来在2010年我国的张彧典先生也用与Kittell和敢峰先生同样的办法解决了敢峰—米勒图的4—着色问题。虽然敢峰—米勒图是无穷次的转型交换也空不出颜色的构形,但其转型的每一步所得的结果,却都是含有环形链A—B的构形,交换环形的A—B链内、外的任一条C—D链,都可使图变成K—构形而可约。
21、敢峰—米勒图类构形的特征:
敢峰—米勒图中含有经过了围栏顶点的A—B环形链和不经过围栏顶点的C—D环形链(见图7,b中的加粗边)。而在敢峰—米勒图中增加了一些“四色构件”(即在图中增加一些顶点和边,并对所增加的顶点进行4—着色,但却不能影响图中原来任何顶点的颜色)的图,虽然图中原有的经过了围栏顶点的A—B环形链和不经过围栏顶点的C—D环形链依然存在,但有些图依然是敢峰—米勒图一类的构形(如图8,a),仍是无穷次转型交换也空不出颜色来的;而有些图却不再是无穷次转型交换也空不出颜色来的构形了,如图8,b逆时针转型交换13次就空出了颜色B,而顺时针转型交换4次又可以空出颜色A。

而在敢峰—米勒图中增加了四色构件的图中,即就是原有的A—B环形链依然存在,但只要不存在原有的C—D环形链了,或者改变了该图中某些四边形对角线的图,或者根本就没有敢峰—米勒图特征的图,就都不再是或者不是敢峰—米勒图类的构形了。无任何环形链的H—构形就是这种构形,根本就不具备敢峰—米勒图的任何特征,所以一定是可以经过有限次的转型交换,就可以空出颜色来的构形。
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—构形,都按染色困局顶点对待。然后再按各种染色困局的解决办法分别解决。

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

注:此文已于二○一九年八月十七日在《中国博士网》上发表过,网址是:



本帖子中包含更多资源

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

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

本版积分规则

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

GMT+8, 2024-3-29 20:41 , Processed in 0.083985 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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