平面图不可避免构形的分类及着色时如何进行判断

雷明85639720

平面图不可避免构形的分类及着色时如何进行判断
雷  明
（二○二一年十一月九日）

1、平面图不可避免构形的分类：
1、1  K—构形和H—构形：
由于含有双环交叉链是构成H—构形的必要条件，但含有双环交叉链的构形却不一定都是H—构形，所以首先把构形分成坎泊的K—构形和赫渥特的H—构形两大类。前者用坎泊已经使用过的可以空出颜色的颜色交换技术进行解决，后者用坎泊还没有使用过的可以断开双环交叉链的断链交换法和转型交换法，把构形先转化成K—构形，再使用空出颜色的颜色交换技术去进行解决。
1、2、 含有环形链的H—构形和不含有环形链的H—构形：
由于含有和不含有经过了构形的关键顶点的环形链的构形解决的办法的不同（前者用断链交换法，后者用转型交换法），所以又可以把H—构形分成含有环形链的构形和不含有环形链的构形两个亚类。
1、3、 含有A—B环形链的构形和含有C—D环形链的构形：
H—构形中除了双环交叉的A—C链和A—D链与待着色顶点成环外，还有A—B链和C—D链是可以各自成环的（因为两链是相反的色链，所以两条环链是不能交叉的），且解决的办法也不同（前者因含有A—B环形链，用的是交换C—D链断链的；后者因含有C—D环形链，用的是交换A—B链断链的）。所以有环形链的H—构形又可再细分为含有A—B环形链和含有C—D环形链的两个次亚类构形。
这样的分类办法是没有遗漏的，这样的不可避免集是完备的。
2、如何判断某个构形是属于那一类：
2、1、 找双环交叉链并看其是否可以连续的移去两个同色：
不含有双环交叉链以及虽然含有双环交叉链但可以连续的移去两个同色者是属于K—构形，而含有双环交叉链但不可以连续的移去两个同色者则是属于H—构形。
2、2  找有没有经过了关键顶点的环形的A—B链或C—D链：
含有环形链A—B者，用交换经过了关键顶点的C—D链去进行断链，使构形转化成K—构形；含有环形链C—D者，用交换经过了关键顶点的A—B链去进行断链，使构形转化成K—构形。不含有任何环形链者，用转型交换法去进行解决，最多不会超过五次转型，就会转化成K—构形。最后都可以用坎泊已经使用过的可以空出颜色的颜色交换技术去解决。

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，