四色猜测的最终证明（简短版）（二）

雷明85639720

四色猜测的最终证明（简短版）（二）
英文标题：Final Proof of Four Colour Conjecture
雷  明
（二○一九年八月十一日）
（接上贴）

5、无任何环形链的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—构形的。再进行两次空出颜色的交换，可以连续的移去两个同色，即可解决问题（见后面的图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—构形，提前结束转型。
6、几个需要交换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的结论是错误的。
7、无任何环形链的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次仍相差很远。

8、除了有环形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—构形。
三、平面图的着色流程：
图30就是平面图的4—着色流程图。

首先把着色时可能遇到的待着色顶点分为染色困局顶点和非染色困局顶点。非染色困局顶点用坎泊链法（即坎泊已用过的交换法或空出颜色的交换法），染色困局顶点用非坎泊链法（即坎泊没有使用过的颜色交换法）。非染色困局的顶点包括度是小于等于4的顶点和围栏顶点占用颜色数小于等于3的顶点。其他的围栏顶点占用了4种颜色的待着色顶点，不管其是不是H—构形，都按染色困局顶点对待。然后再按各种染色困局的解决办法分别解决。
四、四色猜测是正确的：
现在各种情况下的不可免H—构形都是可约的了，加上坎泊早已证明了是可约的K—构形，平面图的任何不可免构形就都是可约的了，平面图的四色猜测也就得到了证明是正确的。当然地图的四色猜测也就是正确的了。从提出至今已有一百六十七年历史的地图四色猜测，就可以上升为地图四色定理了。结束这一个半世纪的证明历史了。

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

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，