四色问题讲座：第十九讲 平面图不可免构形的科学分类

雷明85639720

四色问题讲座：第十九讲  平面图不可免构形的科学分类
雷明
平面图着色时总有一个最后要着色的顶点。把这还剩下一个顶点未进行4—着色的图就叫构形。未着色的顶点叫待着色顶点，与待着色顶点相邻的顶点叫围栏顶点。
构形分类的原则是：多级分类，每级只分两类，非此即彼，不易遗漏。以防再次发生坎泊证明中把一部分有双环交叉链的构形漏掉了的情况。两类中一类是本级分类中就可以解决4—着色问题的构形，一类是要在下一级分类中进行再分类的构形。等到某级分类中的两类构形的4—着色问题，都在某级中可以解决时，多级分类就完成了。这时所得到的各种不可避免的构形就是完备的。
由于任何平面图中一定至少存在着一个顶点的度是小于等于5的，所以着色时总可以把最后要着色的待着色顶点放在度是小于等于5的顶点之上。因此，一级分类就得到了可避免的构形和不可避免的构形。
不可避免的构形可根据其围栏顶点占用颜色数多少分为可直接着色的构形（围栏顶点占用颜色数小于等于3）和不可直接着色的构形（围栏顶点占用颜色数等于4）。
不可直接着色的构形可根据其可否通过颜色交换技术从围栏顶点中空出一种颜色来，可分为可约的K—构形（坎泊构形）和暂认为是不可约的H—构形（赫渥特构形）。K—构形是坎泊在1879年已经证明是可约的构形了。H—构形中一定含有双环交叉链。
H—构形可根据其是否含有经过了围栏顶点的环形链，可分为有环形链的构形和无环形链的构形。有环形链的构形可以用断形法使双环交叉链断开，使H—构形转化成可约的K—构形，无环形链的构形可以用连续转型法，转型法与断链法联合的方法，直接转化成有环形链的H—构形的方法，再用断链法断链，以用局部断链法，都可以使无环形链的H—构形转化成可约的K—构形。
在BAB型的H—构形中，有环形链的H—构形还可根据环形链的种类，分成有A—B环形链（经过了三个围栏顶点）的构形和有C—D环形链（经过了两个围栏顶点）的构形。有A—B环形链的构形交换经过了围栏顶点C、D的C—D链，双环交叉链断开，构形转化成可约的K—构形；无环形链的构形交换经过了围栏顶点A的A—B链，双环交叉链断开，构形转化成可约的K—构形。
现在四级分类（或者说是五级分类）都已进行完毕，各级各类都是可约的了，四色猜测也就证明是正确的了。
这一讲应该说也是一个对四色猜测的证明。实现了我于1992年3 月8日，在西安空军工程学院参加陕西省数学会第七次代表大会暨学术交流会时，所作《赫渥特图的可4—着色》的学术论文报告时提出的“不画图，不着色”证明四色猜测的目标。