轮构形4—着色的研究

雷明85639720

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

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

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

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




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



3、4  有两条既连通又交叉的双环交叉链的5—轮构形的着色：
以上的各种构形都是可以通过坎泊的颜色交换技术直接从围栏顶点中空出颜色给待着色顶点的构形，它们都是坎泊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—构形。下面来看各种情况下的H—构形是否可以做到这一点。
3、6  几种H—构形的标准形式：
图6是几种H—构形的标准形式。

图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—构形。
图6—2中有一条环形的C—D链，把两链的共同起始顶点A和交叉顶点A分隔在了C—D环的两侧。在C—D环的任一侧交换A—B链，都可以使图中不含有双环交叉链，使H—构形转化成K—构形。
以上这两种H—构形的解决办法叫做断链法。
图6—3是不含有任何环形链的构形，不能使用断链法，只能使用使构形的峰点颜色和位置都改变的连续转型法。可以证明，最大的转型次数一定是在不大于40次转型时，就可以使H—构形转化成K—构形，从围栏顶点中空出颜色来给待着色顶点着上。在转过程中，还有可能转化成含有环形链的构形，应及时改用断链法，以提前结束转型。

图6—4虽然是一个含有经过了两链末端顶点C和D的C—D环形链的构形。但因为C—D环不能把两个A色关键顶点分隔在环的两侧，所以不能使用断链法。即就是使用了断链法，图中仍会含有新的双环交叉链，仍是H—构形。这个图与埃雷拉E—图有点相似，虽然都含有C—D环形链，但都不能在C—D环的两侧使用断链法。可见，环形链不但要经过关键顶点，而且还要保证C—D环形链能把两个A色的关键顶点分隔在C—D环的两侧，或者A—B环形链能把经过了两链末端顶点C和D的C—D链与别的C—D链分隔在A—B环的两侧，缺一不可。图6—4既然不能用断链法，那就只有用连续的转型法了。
现在不可避免的各种构形都可以4—着色了，四色问题也就得到解决了。

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