赫渥特H—构形的分类、解决办法与四色猜测的证明（修改稿）

雷明85639720

赫渥特H—构形的分类、解决办法与四色猜测的证明（修改稿）
雷  明
（二○二二年三月十七日）

1、什么是构形？
在给平面图着色时，总是一个顶点一个顶点的去着。也总存在着一个最后要着色的顶点。把这种还有一个顶点未着色而其他顶点都已4—着色的平面图就叫做构形。未着色的顶点叫做待着色顶点（在一般的情况下用大写的英文字母V表示）。而把与待着色顶点V相邻且与待着色顶点构成了轮（这种构形又叫轮构形）的顶点叫围栏顶点（简称“围栏”）。这也就是坎泊1879年对构形的定义。
2、构形的分类：
构形分类的原则是：各级分类一定要只是分成非此即彼的两类，以防止有遗漏。研究四色问题的先驱者——坎泊，也就是因为没有很好的对5—轮构形进行分类，最后终于产生了把含有双环交叉链的构形漏掉的事实，以致11年后的1890年才被赫渥特发现了这一问题。但这一问题直到现在已经过去了133年，还没有得到解决。
3、一级分类：
根据平面图中总是存在着至少有一个顶点的度是小于等于5的理论为基础，把轮构形分为可以避免的且可不再去进行研究的构形和不可避免的且必须进行研究的构形。待着色顶点的度是大于等于6的构形可以不再去进行研究，因为着色时总可以把最后一个要着色的待着色顶点V放在度是小于等于5的顶点之上。而集中力量把注意力放在研究度是小于等于5的不可避免构形的着色方法上。这也就是坎泊给出的不可避免构形集。
4、二级分类：
根据构形中的待着色顶点能不能直接着色，把不可避免的构形分为可直接着色的构形和不可直接着色的构形。围栏顶点占用颜色数小于等于3（包括待着色顶点的度是小于等于3）的构形，待着色顶点是可以直接着色的，因为至少还有一种颜色可以使用；而围栏顶点占用颜色数等于4的构形，待着色顶点是不可直接着色的。
5、三级分类：
根据构形能不能从围栏顶点中直接空出颜色给待着色顶点V着上，把不可直接给待着色顶点着色的构形分为可以从围栏顶点中直接空出颜色的坎泊K—构形（空出的颜色就可直接给待着色顶点着上）和不可直接从围栏顶点中空出任何一种颜色的赫渥特H—构形。可以从围栏顶点中直接空出颜色的K—构形，坎泊早已在1879年进行了解决，是可以4—着色的，即是可约的。现在主要就是集中力量来解决不可直接从围栏顶点中空出任何一种颜色的赫渥特H—构形的着色问题了。
6、破坏双环交叉链是解决H—构形可约性的关键：
由于双环交叉链是构成H—构形的必要条件，没有它不能构成H—构形，但有了它又未必一定都是H—构形（因为有些含有双环交叉链的构形，的确是可以直接从围栏顶点中空出颜色来给待着色顶点着上的的）。因为在BAB型的H—构形中，A—C链和A—D链都是连通的，不可能空出A、C、D三色之一来，而当任意的移去了一个同色B后，就会新生成从另一个同色顶点B到其对角顶点的连通链，不可能连续的移去两个同色B。从而不可能从围栏顶点中空出任何一种颜色来。所以要解决H—构形的可约性问题，必须首先破坏（断开）双环交叉链，使其转化成无双环交叉链的坎泊K—构形，再从围栏顶点中空出颜色给待着色顶点。
7、关键顶点：
要断开双环交叉链，有四个关键的顶点。只要其中有一个顶点的颜色发生了改变，双环交叉链就同时断开了。这就是双环交叉链的共同起始顶点和交叉顶点，以及两链的两个末端顶点。这四个顶点中有三个是围栏顶点，一个是非围栏顶点。其中两链的两个末端顶点又是相邻的两个围栏顶点，另外的两个——两链的共同起始顶点和交叉顶点是不相邻的顶点。
8、含有不含有环形链是能不能断开双环交叉链的关键：
在BAB型的H—构形中，若要同时改变双环交叉链的两个末端顶点的颜色C和D，就必须要有一条经过了任一个关键顶点A的环形的A—B链，把这两个相邻的末端顶点（也是围栏顶点）C和D与双环交叉链中的其他着有颜色C和D的顶点，至少有一对分隔在A—B环的两侧，才不至于在改变了两链的两个末端点顶点C和D的颜色后，致使其他的着有颜色C和D的顶点的颜色也都跟着发生变化，使交换失去作用。同样的道理，若要改变两链的共同起始顶点A和交叉顶点A中的任何一个顶点的颜色时，也必须要有一条经过了双环交叉链的两个末端顶点（关键顶点）的环形的C—D链把这两个A色顶点分隔在C—D环的两侧。H—构形中只要含有经过了关键顶点的环形链这个条件，就可以把双环交叉链断开。但也有个别情况（如后面的图1中的构形），其中虽然含有环形链，也是不能把双环交叉链断开的。
9、四级分类：
根据有没有环形链且能不能把双环交叉链同时断开，又可以把H—构形分为可断开双环交叉链的构形和不可断开双环交叉链的构形两类。但是，含有经过了关键顶点的环形链，只是可断开双环交叉链的必要条件，而不是充分条件。含有经过了关键顶点的环形链的构形却不一定都能断开双环交叉链（如后面的图1中的构形就是这种情况）。
10、用断链法把双环交叉链同时断开：
对于可断开双环交叉链的构形，若构形中含有A—B环形链，交换A—B环形链两侧的任一条C—D链，一定是可以同时断开两条连通链的，也就不存在双环交叉链了；而构形中含有C—D环形链且必须把两个A色的关键顶点分隔在C—D环的两侧时，交换环形链两侧的任一条A—B链也一定可以使两条连通链断开的，也就不存在双环交叉链了（所以把这种使两条双环交叉链同时断开的方法叫“断链法”）。但若C—D环形链不能把两个A色关键顶点分隔在C—D环的两侧时，两条连通链则是不能断开的，双环交叉链则依然是存在的（如图1）。

11、用转型法首先断开一条连通链：
对于不可断开双环交叉链的构形，既然不能使两条双环交叉链同时断开，那么总可以通过转型，首先断开其中的一条（即先移去一个同色。这时，构形的峰点会发生改变，这就是转型），再看看断开一条连通链后的构形是否还是H—构形。若仍是H—构形，就继续的进行转型，直到转化成K—构形为止，一定是可以在有限的转型次数之内解决问题的。所以把这种方法就叫做“转型法”。
12、用转型法＋断链法联合解决问题：
图1的原构形中有一条经过了双环交叉链A—C和A—D的两个末端顶点的环形的C—D链，顺时针一次转型后，就转化成了仍有一条经过了新的双环交叉链D—A和D—B的两个末端顶点的环形的A—B链的构形（如图2），一定是可以用断链法解决问题的。这种用先“转型”，后“断链”解决问题的方法可以叫做“转型法＋断链法”。一般在使用转型法的过程中，往往都会生成有环形链的构形，要及时的改用断链法，提前结束转型。
13、转型的最大次数一定是有限的：
由于有埃雷拉E—图构形的存在，它是一个无穷周期循环转型的构形。从而得到E—族图每次转形所得构形（包括原构形E—图在内）都是可以用改变有关关键顶点颜色的断链法而转化成K—构形的构形。E—图就有这种性质。根据原命题的逆否命题与其原命题有“同真同假”的逻辑关系，则有“每步转型（也包括原构形在内）都是不可以用改变有关关键顶点颜色的断链法转化成K—构形的构形，一定不是无穷周期循环转型的E—图构形。即一定是一个有限次转型的非E—图构形”的结论是成立的。这就决定了不可断开双环交叉链的构形转型的最大次数一定是有限的。
14、转型最大次数的上限值：
没有上限值的“有限”仍然是相当于无限。那么“有限次转型”的“上限值”是多少呢？因为5—轮构形有5个轮沿顶点，每个轮沿顶点都作一次峰点时，就是5次转型。转型次数大于5次时，显然就会出现循环现象。所以最大在5次转型后就应该是只有一条连通链的可约的K—构形了。而在最后一次转型的前一次转型后，得到的就一定是一个可以连续的移去两个同色的可约的K—构形。这就说明最大转型次数的上限值是4，或者也可以说是5。着色的实践（图1在移去了一个同色后，再人为的构造从另一个同色顶点到其对角顶点的连通链）也说明了这一点是正确的。另外E—图构形在20次转型后，各顶点的颜色又都复原到最初开始还未转型时的原始状态，以后又开始了新一轮的循环。所以转型的最大次数最大也一定是不会大于20次的。
15、四色猜测的证明：
现在，平面图的各种不可避免的构形都已是可4—着色的（即可约的）了，平面图的四色猜测就是正确的了。地图的四色猜测也就是正确的了。四色猜测也就得到证明是正确的。

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

注：此文已于二○二二年三月十四日在《数学中国》网《哥猜等难题和猜想》栏目中发表过，原标题是《赫渥特H—构形的分类及解决办法》，网址是：
http://www.mathchina.com/bbs/for ... =2051073&extra=
本次修改后并把标题改成了《赫渥特H—构形的分类、解决办法与四色猜测的证明》。

   

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，