轮构形可4—着色的研究（修改稿）

雷明85639720

轮构形可4—着色的研究（修改稿）
雷  明
（二○二二年四月二十二日）

1、可直接给待着色顶点着色的构形：

2、4—轮构形的可4—着色：
见《4—轮构形为什么一定是可4—着色的》一文，网址是：
http://www.mathchina.com/bbs/for ... =2051562&extra=。
3、5—轮构形的可4—着色：

3、1  无任何连通链的5—轮构形的可4—着色，一定是可以空出任何一种颜色给待着色顶点V的（见图2）。
3、2  有一条连通链的5—轮构形的可4—着色：见图3。




3、3  有两条连通链的5—轮构形的可4—着色：见图4。



3、4  有两条既连通又交叉的双环交叉链的5—轮构形的可4—着色：
以上的各种构形都是可以通过坎泊的颜色交换技术直接从围栏顶点中空出颜色给待着色顶点的构形，它们都是坎泊1879年已证明是可约的K—构形。而构形中是否含有双环交叉链又是构成不可直接从围栏顶点中空出任何颜色的构形的必要条件。没有双环交叉链不可能构成不可直接从围栏顶点中空出任何颜色的构形，但有了双环交叉链却不一定都是不可直接从围栏顶点中空出任何颜色的构形。比如图5中的几个具体的图中虽然也都含有双环交叉链A—C和A—D，但却只有图5—2一个是不可直接从围栏顶点中空出任何颜色的构形，而其他三个构形都是可以连续的移去两个同色B的构形。这种构形是赫渥特在1890年发现的，所以就把这种不可直接从围栏顶点中空出任何颜色的构形叫做H—构形。


从图5中可以看出，图5—2只所以不可直接从围栏顶点中空出任何颜色，除了不能空出A、C、D外，还有从任何一个B色顶点交换了与其对角顶点的颜色构成的色链后，虽然也移去了一个B色，但又都会新生成从另一个B色顶点到其对角顶点的连通链，使得不可能移去另一个B色，而不可能连续的移去两个同色B。而图5中其他的三个图则不存在这种情况，所以是可以连续的移去两个同色B的。可见图5—2是H—构形，而其他三图都是K—构形。
3、5  H—构形只有断开了双环交叉链，才有可能转化成可以直接从围栏顶点中空出颜色给待着色顶点的构形：
从图5—2中可以看出，两链的共同起始顶点A和交叉顶点A，以及两链的两个末端顶点C和D四个顶点都是关键的顶点，其中只要有一个顶点的颜色发生了变化，构形就可以转化成不含有双环交叉链的K—构形。
3、6  断开双环交叉链的条件是图中含有经过了关键顶点的环形链：
3、6、1  由于双环交叉链的两个末端顶点C和D是相邻的，要改变两链末端顶点C和D的颜色，就要交换含有两链末端顶点的一部分C—D链。这样图中就必须要有一条环形的A—B链，把经过两链末端顶同点的C—D链与其他的C—D链分隔在A—B环的两侧，互不连通。同样的，要改变两个A色关键顶点的颜色，交换的则必须是A—B链，也必须要有一条环形的C—D链，把两个A色的关键顶点分隔有C—D环的两侧。因此，不可直接从围栏顶点中空出任何颜色的H—构形，就可以再细分为两个分类。一是含有环形链的构形，二是不含有环形链的构形。
3、6、2  前一类含有环形链的构形又可分为有A—B环形链的构形和有C—D环形链的构形。在含有A—B环形链的构形中，A—B环形链无论是经过了几个A色的关键顶点，都是可以把经过两链末端顶点C、D的C—D链与其他的C—D链分隔在A—B环的两侧的。而在含有C—D 环的构形中，却有能不能把两个A色的关键顶点分隔在C—D环的两侧的问题。因此，这一含有C—D环形链的构形还可以再细分为两类（见后面的论述）。
下面来看看以上各种情况下的H—构形是否可以做到断开双环交叉链这一点。
3、7  几种H—构形的标准形式：
图6是几种H—构形的标准形式。

3、7、1  图6—1中有一条环形的A—B链，把两链的末端顶点C和D构成的C—D链与其他的C—D链分隔在了A—B环的两侧。在A—B环的任一侧交换C—D链，都可以使图中的双环交叉链断开，使H—构形转化成K—构形。从图6—1中还可以看出，A—B环形链是经过了两个A色的关键顶点的，若是只经过了一个A色的关键顶点，同样也是可以把两链的末端顶点C和D构成的C—D链与其他的C—D链分隔在A—B环的两侧的。用同样的交换办法也可以使双环交叉链断开，构形由H—构形转化为K—构形。
3、7、2  图6—2中有一条环形的C—D链，把两链的共同起始顶点A和交叉顶点A分隔在了C—D环的两侧。在C—D环的任一侧交换A—B链，都可以使图中的双环交叉链断开，使H—构形转化成K—构形。
以上这两种H—构形的解决办法叫做断链法，因为交换的结果是双环交叉链都断开了。

3、7、3  图6—3是不含有任何环形链的构形，不能使用断链法，只能使用使构形的峰点颜色和位置都改变的连续转型法。可以证明，最大的转型次数一定是在不大于40次转型时，就可以使H—构形转化成K—构形，从围栏顶点中空出颜色来给待着色顶点着上。在转过程中，还有可能会转化成含有环形链的构形，应及时改用断链法，以提前结束转型。
3、7、4  图6—4虽然是一个含有经过了两链末端顶点C和D的C—D环形链的构形。但因为C—D环不能把两个A色关键顶点分隔在环的两侧，所以不能使用断链法。即就是使用了断链法，图中仍会含有新的双环交叉链，仍是H—构形。这个图与埃雷拉E—图有点相似，虽然都含有C—D环形链，但都不能在C—D环的两侧使用断链法。E—图的C—D环没有经过关键顶点C和D，却把两个A色的关键顶点分隔在了环的两侧；而图6—4的构形中的C—D环虽经过了关键顶点C和D，但却没有把两个A色的关键顶点分隔在环的两侧。可见，环形链不但要经过关键顶点，而且还要保证C—D环形链能把两个A色的关键顶点分隔在C—D环的两侧，或者A—B环形链能把经过了两链末端顶点C和D的C—D链与别的C—D链分隔在A—B环的两侧，缺一不可。
图6—4既然不能用断链法，那就只有用连续的转型法了，与不含有环形链的构形放在一起进行研究（见后面的论述）。
4、最大转型次数的确定与证明：
有一个构形叫做埃雷拉E—图构形及其同类的E—族构形，其中含有不经过关键顶点C和D的C—D环形链，它在施行连续的转型时，是一个无穷周期转型的构形，使用转型法是不可能得到最终解决问题的。但因该构形中还含有经过了关键顶点A的环形的A—B链，把双环交叉链的两个末端顶点C和D的C—D链与别的C—D链分隔在了A—B环的两侧，又可以用断链法进行解决。那么E—族构形以外的非E—族构形的转型次数是多少呢？
由于存在着以埃雷拉E—图为代表的E—族构形，其在施行转型时是以20次转型为一个周期的无穷周期循环转型的构形，即每20次转型后，图又会返回到了原转型出发时的原始状态（各顶点的颜色又与转型前的颜色完全相同）。另外，我们也不可能把无穷多的非E—族构形，都一个个的进行转型，看其转型次数是多少。而只能根据原命题的逆否命题与原命题是“同真同假”的逻辑关系，来判断非E—族构形的转型次数。
已有命题（即原命题）：E—族构形是无穷周期循环转型的构形；其逆否命题是：有限次转型（即非周期循环转型）的构形是非E—族构形的构形。倒过来说则是非E—族构形的构形是非周期循环转型的构形。原命题“E—族构形是无穷周期循环转型的构形”是真的，那么其逆否命题“非E—族构形的构形是非周期循环转型的构形”也就是真的。即非E—族构形以外的构形都是有限次转型的可约的构形。
这里的“有限次”，上界值是多少？一定得要有一个具体的数值，否则，“有限”也就成了无限。因为E—族构形的循环周期是20次转型，两个方向施行转型时共同转型的次数就是40次。而任何一个非E—族构形都是可以从两个不同的方向施行转型的，两个方向的转型次数一定都不会产生循环，即各自的转型次数一定都是不会大于20次的，也就是说两个方向的转型次数的和也一定是不会大于40次的。所以也可以说，从施行了任何一种方向的任何次数之后所得到的构形开始，再施行相反方向的转型，到转型得到不存在双环交叉链时的非H—构形时，转型的次数都一定是不会大于40的。所以非E—族构形的最大转型次数也一定是不会大于40次转型的。我和张彧典先生都构造过转形次数大于20次以上的但又小于40次的非E—族构形。
我们用了两个逆时针方向转型都需要20次转型的两个构形，其顺时针方向转型分别需要3次转型和6次转型。其中一个构形的两个方向转型的转型次数之和是23次，另一个构形的两个方向转型的转型次数之和是26次，说明了转型次数大于20次而不出现循环的构形是存在的。两种构形在两种方向转型的转型过程中，每相隔20次转型的两个构形，虽然都是峰点颜色和两个同色顶点颜色都相同的同一类型的非E—族构形，但其中的各顶点的颜色却并不都是完全相同的，也就说明了这种转型是不会产生循环现象的，转型次数一定是有限的。转型不会产生循环现象的构形，说明了就只能在40次转型之内就可以解决问题了。


例如，我们用的两个构形的原图分别如图7—1和图8—1，都是BAB型的构形。逆时针方向转型15次和18次后分别是图7—2和图8—2，顺时针方向转型5次和2次后分别是图7—3和图8—3。图7—2和图7—3中的两个构形，以及图8—2 和图8—3中的两个构形，都是同方向转型相隔20次的构形。虽然分别都是CDC型和ABA型，但图中却不是所有的顶点都有相同的颜色（如图7—2和图7—3中，左侧的多重菱形中就有中间的两个顶点的颜色不同，图8—2和图8—3中，右侧的多重菱形中也有中间的两个顶点的颜色不同），这也都说明了不会出现循环现象。
5、非E—族构形与上面的H—构形间的关系：
E—族构形都是H—构形，属于有环形链的构形，解决时是采用断链法的。而非E—族构形也都是H—构形，应该都是可以用连续转型法解决的。但非E—族构形中，有些构形也是含有环形链的构形，解决时也是可以采用断链法的；而含有环形链的非E—族构形中也还有一部分构形则是不能使用断链法的；还有一些非E—族构形是不含有环形链的构形，解决时也是不能使用断法的。这后两种才是真正要使用连续转型法的构形。也是一定遵守连续转型法的规则的，最大的转型次数也一定是不会大于40次转型的。

由于任何平面图中都一定存在着至少一个度是小于等于5的顶点，所以我们在着色时，一定可以把最后的待着色顶点放在度是小于等于5的顶点之上。这样我们就可以不再去对度是大于等于6的待着色顶点的可约性去进行逐一研究了。这就把一个研究对象是无穷多的问题转化成了一个有穷的问题。以上所研究的构形都是平面图的不可避免的构形。这些不可避免构形在各种情况下已都是可约的了，四色问题也就解决了，四色猜测就被证明是正确的了。

雷  明
二○二二年四月二十二日于长安

注：此文已于二○二二年四月二十二日在《数学中国》网《哥猜等难题与猜想》栏目中发表过，网址是：
http://www.mathchina.com/bbs/for ... =2051585&extra=，这次发表的是修改稿。

朱明君

，，，，，，，

cz1

！！！！！！！！！！！！