平面图不可避免构形的分类与四色猜测的证明

雷明85639720

平面图不可避免构形的分类与四色猜测的证明
雷 明
2022年2月10日

1，给图的顶点4一着色时，总是一个顶点，一个顶点的着，总是有最后一个顶点要进行着色的。这最后一个顶点还未着色的图，就是四色猜测证明中所用到的“构形”。对于极大图来说，任何顶点都是处在一个轮的中心顶点位置的，所以这种构形也就叫“轮构形”。
2，构形的分类，最好是分成非此即彼的两类，以防遗漏。现在对构形进行第一级分类。两类分别是：可以避免的构形和不可避免的构形。这一分法的根据是任何平面图中都存在着度是小于等于5的顶点这样一个特征的。因为任何极大图（地图的对偶图）着色时总可以把最后一个要着色的顶点放在度是小于等于5的顶点上。所以度大于等于6的轮构形是可以避免的，而度小于等于5的轮构形是不可避免的。可以避免的构形，就可以不必再专门研究其可约性了。只要研究有限个的不可避免构形的可约性就可以了。这时，一个度可以是无穷大的无穷的地理问题，就转化成了一个只研究度是小于等于5的有限的4种构形（2—轮，3—轮，4—轮，5—轮四种）的数学问题了。
3，现在对不可避免构形进行第二级分类。两类分别是：不发生颜色冲突的构形和发生了颜色冲突的构形。这一分类是根据轮沿顶点占用颜色数是否是小于允许使用的颜色数4的。轮沿顶点占用的颜色数小于4时，是不发生颜色冲突的构形，待着色顶点可以直接着色。这种构形有2—轮构形和3—轮构形。轮沿顶点占用的颜色数等于4的构形，是发生了颜色冲突的构形，待着色顶点是不能直接着色的。而是要经过使用坎泊创造的颜色交换技术，从轮沿顶点中空出一种颜色后，才能给待着色顶点着上。这样的构形是4—轮构形和5—轮构形。
4，坎泊的颜色交换技术的根据是四种颜色可能构成的两种相反的二色链是不可能相互穿过的原理而提出的。比如一个4—轮，4个轮沿顶点分别着以A，B，C，D四种颜色，当有一对对角顶点的两种颜色构成的链是连通的，并与待着色顶点构成了一个环时，则另一对对角顶点间一定是不连通的。这时从后一对对角顶点的任一个顶点开始交换该两个对角顶点的颜色构成的二色链，一定可以空出一种颜色给待着色顶点。这就是坎泊在1879年所创造的颜色交换技朮。
5，现在再对发生了颜色冲突的构形进行第三级分类。两类分别是：可以直接从轮沿顶点空出颜色给待着色顶点的构形和不可直接从轮沿顶点空出颜色给待着色顶点的构形。前者是K—构形，是坎泊早己证明过是可约的构形。后者是H—构形，是坎泊证明中所遗漏了的一种构形。现在解决四色问题主要就是证明H—构形的可约性问题。
6，构形中有沒有双环交叉链是构成H—构形的必要条件。也就是说，没有双环交叉链，不能构成H—构形，但有了双环交叉链，却不一定都是H—构形。所以说H—构形中一定是含有双环交叉链的，而K—构形中，对于双环交叉链来说，则是可有可无的。
7，解决H—构形的可约性问题，必须破坏双环交叉链。如何才能破坏双环交叉链呢？就得改变有关关键顶点的颜色。什么是关键顶点呢？即双环交叉链的共同起始顶点，相交叉顶点和两链的两个末端顶点。这四个顶点中，只要有一个顶点的颜色进行了改变，双环交叉链就立即同时断开了。转化成了无双环交叉链的可约的K—构形。然后再按解决K—构形可约性的办法，从轮沿顶点中空出一种颜色来给待着色顶点就行了。
8，要改变有关关链顶点的颜色，是要有一定条件的。比如，要改变双环交叉链的共同起始顶点或相交叉顶点的颜色，就必须要有一条经过了两链末端顶点的环形链，把上述两个关键顶点分隔在环的两侧，以不致两个顶点同时改变颜色，使双环交叉链不能断开。的确，也就存在着这样的构形，虽有经过了两链末端顶点的环形链，但却不能把上述两个有关的关键顶点分隔开来。又比如，要改变双环交叉链的末端顶点的颜色，就必须有一条经过了两链的共同起始顶点或相交叉顶点的环形链，以把两链的两个末端顶点与其他的相同颜色的色链分隔在环的两侧。由于两链的末端顶点在轮沿处是相邻的，所以只要有一条经过了两链的共同起始顶点或相交叉顶点的环形链时，两链的两个末端顶点一定就是位于环形链的一侧的，与另一侧的相同颜色的色链是不连通的。同时也因为两链的两个末端顶点是相邻的，所以只要改变了一个顶点的颜色，也就得到了两个末端顶点同时改变颜色的效果。在这种情况下，都是可以断链的。
9，现在再对H一构形进行第四级分类。两类分别是：可改变有关关键顶点的颜色使双环交叉链断开的构形和不能用改变有关关键顶点的颜色使双环交叉链断开的构形（即可以转型使构形峰点改变，再按新的构形的特征去进行解决）。
10，两类H—构形中的特征链：现在以BAB型的5一轮构形为例来进行说明。前一类可改变有关关键顶点的颜色使双环交叉链断开的构形中的特征链有两种，即，有A—B环形链（含A—B环形链与C—D环形链同时存在）的构形和只含有C—D环形链且把两个A色的关键顶点分隔在环的两侧的构形。可分别通过交换经过双环交叉链两个端点顶点的C—D链和交换经过任一个A色关键顶点的A—B链，使双环交叉链断开，成为可约的K—构形。
11，后一类不能用改变有关关键顶点的颜色使双环交叉链断开的构形中，有一种构形虽然含有经过了关键顶点的C—D环形链，但却沒有把两个A色的关键顶点分隔在环形链的两侧。另一种构形是任何环形链都没有的构形。如上所述，这两种情况的构形都不能直接把双环交叉链断开，那就只有走转型的道路，使构形的峰点进行改变，成为新的构形，再进行处理了。
12，无环形链的H—构形的转型次数一定是要有上限值的。从埃雷拉E—图（包括米勒图，张彧典先生的第九构形，敢峰先生的终极图和科凯的CK0图）的转型看，都是一个无穷周期循环转型的构型，永远也不可能通过转型从轮沿顶点中空出颜色来给待着色顶点着上。那么无环型链的H—构形转型时会不会也出现这种现象呢？必须进行证明。其转型次数不但应是有限的，而且还应有一个具体的上限值。否则，有限还等同于无限。
13，无环形链的H—构形最大转型次数的证明。由于有E—图构形的存在，它是一个无穷周期循环转型的构形。从而得到了每次转形（包括原构形在内）都是可以改变有关关键顶点的颜色而可约的构形。E—图就有这种性质。根据原命题的逆否命题与原命题有同真同假的逻辑关系，则有“每步转型（也包括原构形在内）都是不可以改变有关关键顶点的颜色而可约的构形，一定不是无穷周期循环转型的构形，即一定是一个有限次转型的构形”的结论是成立的。那么“上限值”是多少呢？因为5—轮构形，有5个轮沿顶点，每个轮沿顶点都作一次峰点时，就是五次转型。转型次数大于五次时，显然就会出现循环现象。所以最大在五次转型后就应该是只有一条连通链的可约的K—构形了。而在最后一次转型的前一次转型后，得到的就一定是一个可以连续的移去两个同色的可约的K—构形了。这就证明了最大转型次数的上限值是四，或者说是五也可以。
14，现在，任何情况下的H—构形都是可约的了。加上坎泊早已证明过是可约的K—构形，所有的平面图的不可避免构形已经都是可约的了。四色猜测也就被证明是正确的了。
（完）
雷  明
二○二二年二月十日于长安

注：此文已于二○二二年二月十七日在《中国博士网》上发表过，网址是：
http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=5042

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，