判断一个已部分着色的图（构形）是否是赫渥特H—构形的方法

雷明85639720

判断一个已部分着色的图（构形）是否是赫渥特H—构形的方法
雷  明
（二○二二年四月十日）

    当给一个极大平面图着色时，到最后遇到一个5—度的待着着色顶点，且围栏顶点已占用完了4种颜色时，如何判其是否是赫渥特的H—构形呢？现在我们来分析一下：
1、看有没有双环交叉链：如果没有就是坎泊的K—构形，用坎泊用过的可空出颜色的颜色交换技术去解决；当含有双环交叉链（如图1，为了研究方便，对图中的“九点形”的顶点按习惯进行了编号）时，就有可能是H—构形。

2、在图1 的这个BAB型的有双环交叉链A—C和A—D的5—轮的基本模型中，若在6C和7D间还有别的顶点（如图2）时，在从任一个B色顶点进行了对角链的交换后，都不会新生成从另一个B色顶点到其对角顶点的连通链，即不可能是H—构形；若在6C和7D间就只是一条边时，才有可能是H—构形。
3、图1中。如果从3B到8A（或从1B到8A)只是一条边（如图3），则从3B（或1B）交换了B—C（或B—D）链后，一定不会新生成从1B到4D（或从3B到5C）的B—D（或B—C）链，都是可以连续的移去两个同色B的K—构形；若如图4那样，虽有环形的A—B链，但也是可以连续的移去两个同色B的K—构形。


4、图1中。如果从4D到6C（或从5C到7D)是一条边（如图5），则从3B（或1B）交换了B—C（或B—D）链后，都一定会新生成从1B到4D（或从3B到5C）的B—D（或B—C）链，但这时还不能确定其是否是H—构形；若如图6那样，就成为不可连续的移去两个同色B的H—构形了。赫渥特的H—图的简化结果就是这种“九点形”构形，是一个含有环形的C—D链的H—构形。张彧典先生的第二构形就是这样的构形。
5、把图3和图5进行组合，当3B和8A以及1B和8A都是单边时，可得到图7和图，都是可以连续的移去两个同色B的K—构形。张彧典先生的第一构形和第二构形分别就是这样的构形；当3B和8A以及1B和8A都是一条单边，一条多边时，可得到图9和图10。图9是无任何环形链的H—构形，图10则是有环形A—B的K—构形。张彧典先生的第四、第五、第六和第七构形分别就是这样的构形，都是可以连续的移去两个同色B的构形。



当3B和8A以及1B和8A都是多条边的道路时，可得到图11，图12 ，图13和图14，全都是H—构形。其中一个有环形链A—B，两个有环形链C—D，一个无任何环形链。张彧典先生的第八构形就是如图14的构形，不含任何的环形链（如图15），但当把图中加大的顶点A的颜色改换成C后（如图16），图就转化成了如图13那样的有环形链C—D的构形了。但这时图中就只有一条连通的A—C链了（A—D链已断开），成为一个K—构形（如图17）；当3B和8A以及1B和8A都是多条边的道路，但移去了任一个B时，都不能新生成从另一个B到其对角顶点的连通链时，就是有环形链的两个K—构形（如图18和图19）。





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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，