不含环形链的H—构形的4—着色办法

雷明85639720

不含环形链的H—构形的4—着色办法
雷  明
（二○一九年七月二十三日）
（在这里我发不上图，请到《中国博士网》中去看）

1、不含环形链的H—构形的特征：
图1就是一个不含环形链的H—构形。

图中却既有连通的A—C链，又有连通的A—D链，且两链在中途又相交叉，具备了构成H—构形的必要条件（如图2）。当从左B开始交换B—D链时，就会产生连通的从右B到其对角C的连通链B—C（如图3），当从右B开始交换B—C链时，也会产生连通的从左B到其对角D的连通链B—D（如图4），说明图1的确是一个H—构形。从图中还可以直接看出，图中既没有环形的A—B链，也没有环形的C—D链，这两种链这均是直链（如图5）。但图1只是这种H—构形的一种情况，还有另一种情况正好是和图1左右相反的（如图6），其实质是同一类构形，所以这里只研究图1就可以了。

这种构形着色时，只能用转型交换法，在有限次的转形后，构形就会转化成一个可以连续的移去两个同色的K—构形，再进行两次空出颜色的交换，即可给待着色顶点着上图中已用过的四种颜色之一。
2、用逆时针转型法着色：
第1步，对图1从左B交换B—D链，产生了从右B到其对角C的B—C连通链（如图7），是DCD型。
第2步，对图7从右下D交换D—A链，没有产生从左D到右B的连通链D—B（如图8），但在平面图内可以构造出连通的D—B链（如图9），成为ABA型。
第3步，对图9从顶A交换A—C链，也不产生从右下A到左D的连通链A—D（如图10），但在平面图内也可以构造出连通的A—D链（如图11），是CDC型。这时图已转化成一个可以连续的移去两个同色C的K—构形了。

第4步，对图11从左下C交换C—B链，再也不会产生从顶C到右下A的连通链C—A（如图12），因为前方有B—D链的阻隔，C—A链是不能穿过B—D链的。
第5 步，再从顶C交换C—A链，即可空出颜色C来给待着色顶点V着上（如图13）。

总共最大只进行了5次交换，其中前三次交换是转型交换。如果不是人为的构造连通链，则交换次数将更少。
3、用顺时针转型法着色：
第1步，对图1从右B交换B—C链，产生了从左B到其对角D的B—D连通链（如图14），是CDC型。

第2步，对图14从左下C交换D—A链，没有产生从右C到左B的连通链C—B（如图15），但在平面图内可以构造出连通的C—B链（如图16），成为ABA型。

第3步，对图16从顶A交换A—D链，也不产生从左下A到右C的连通链A—C（如图17），但在平面图内也可以构造出连通的A—C链（如图18），是DCD型。这时图已转化成一个可以连续的移去两个同色D的K—构形了。

第4步，对图18从右下D交换D—B链，再也不会产生从顶D到左下A的连通链D—A（如图19），因为前方有B—C链的阻隔，D—A链是不能穿过B—C链的。
第5 步，再从顶D交换D—A链，即可空出颜色D来给待着色顶点V着上（如图20）。

也是总共最大只进行了5次交换，其中前三次交换也是转型交换。如果不是人为的构造连通链，则交换次数将更少。
4、总结：
这里的图1，是一个非常一般的非具体图的H—构形，最多5次交换就可以解决问题。张彧典先生的Z类构形只所以产生了16次交换，或者还需要更多交换构形，主要是他把本来可以直接用断链交换（即张先生的Z—换色程序）解决的构形，硬要也用转型交换法（即张先生赫渥特颠倒法）来解决，所以交换的次数就多起来了。这实在是一个少慢差费的办法，应该废除！

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

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，