四色猜测是可以手工证明的

雷明85639720

四色猜测是可以手工证明的
雷  明
（二○一九年元月十四日）
（这里我发不上图，请到《中国博士网》中去看）

在地图中，把相邻的国家都染成不同的颜色，一张地图最多四种颜色就够用了。这就是1852年英图的绘图员法朗西斯提出的地图四色猜测。地图是一个3—正则的平面图，对其面的染色，就是对其对偶图——极大平面图的顶点着色。这就把一个地理学上的问题转化成了一个数学问题了。
1879年坎泊证明了2—轮构形，3—轮构形，4—轮构形以及5—轮构形中的：无连通链，有一条连通链，有两条连通链但两链只有共同的起始顶点，或者只有在中途有交叉顶点的构形是可约的（即可4—着色的）；而遗漏了证明两链既有共同的起始顶点，且中途又有交叉顶点的构形是否可约的问题。这一遗漏在1890年被赫渥特用其构造的赫渥特图揭示了出来。但当时坎泊和赫渥特二人都没有对这个图进行4—着色。直到1990年前后，才有我国的雷明和懂德周，英国的米勒等，对赫渥特图在赫渥特原着色的基础上进行了4—着色。后来又有我国的张域典，刘福，颜宪邦，许寿椿等人，也都对赫渥特图进行了4—着色。
赫渥特图只是一个个别的图，只对它进行了4—着色还不能说明四色猜测就是正确的。而要对具有赫渥特图结构特点的一类图都证明了是否可4—着色时，才能得出四色猜测是否是正确的结论。所以说，目前解决四色问题的关键，就是要解决好具有赫渥特图结构特点的一类图（即H—构形）的可约性问题。
1、雷明的证明方法：
根据构形的结构特点将H—构形分成三类，第一类是含有构形的三个围栏顶点的A—B环形链的构形（如图1），第二类是含有构形的两个转栏顶点的C—D环形链的构形（如图2），第三类是不含任何环形链的构形（如图3和图4）。三类构形均含有两条既有共同起始顶点2，在中途又有交叉顶点8的连通的A—C链和A—D链，而只是A—B链和C—D链的分布结构不同。

图1的解决的办法是交换经过构形两个围栏顶点4和5的C—D链，图中原有的A—C链和A—D链均可变成不连通的，图成为K—构形而可约；而图2的解决的办法则是交换经过构形三个围栏顶点1，2和3的A—B链，图中原有的A—C链和A—D链也就均可变成不连通的，图成为K—构形而可约。因此，解决这两类构形的方法，可以叫做断链法。
但图3就不能这样交换，而只能交换B—C链和B—D链之一，使构形转型，使图变成K—构形或上面的第一类、第二类H—构形，否则，就继续再进行同方向的转型交换。图3与图4是实际上是同一类构形，只是左右不同罢了，所以研究图3一个就可以了。
对图3从顶点1交换B—D链时（一次转型交换），产生了从顶点3到顶点5的连通链B—C（如图5），虽不能连续的移去两个B，但图5却是一个可以连续的移去两个同色D的K—构形。当对图5从顶点4交换D—A链时（二次转型交换），不能生成从顶点1到顶点3的连通链D—B（如图6），这就可以再从顶点1交换D—B链，连续的移去两个同色D，或者从顶点2交换B—D，空也B来（图请读者画）。

图6虽然没有从顶点1到顶点3的连通链D—B，但在平面图范围内，却有构成该链的可能（如图7），这样就不可能连续的移去两个同色D了，只有再进行转型。对图7从顶点2交换A—C链时（三次转型交换），同样的也有从顶点4到顶点1生成连通的A—D链的可能（如图8）。但对图8从顶点5交换C—B链时（四次转型交换），还有可能有再从顶点2到顶点4生成连通的C—A链了，但到第五次转型交换时，就不可能再产生从另一个同色顶点到其对角顶点的连通链了。说明再进行一次交换就可以空出颜色来。总共是六次交换。

若对图3从顶点3交换B—C链时（一次转型交换），产生了从顶点1到顶点4的连通链B—D（如图9），虽不能连续的移去两个B，但图9却是一个第一类的H—构形了，图中有了含有构形两个转栏顶点的A—B环形链，是可约的了。当对图9从顶点5交换C—A链时（二次转型交换），也有可能生成从顶点3到顶点1的连通的C—B链（如图10）。继续转型下去，同样的也是在五次转型交换时，就不可能再产生从另一个同色顶点到其对角顶点的连通链了。第六次交换后就空出了颜色。
第三类构形在连续转型交换的中途都多次可以转化成第一类和第二类构形，改用断链法时，仍可以在五次交换内空出颜色。但对于轴对移的第三类构形（如图11），在第三次转型交换后可得到一个既是第一类，又是第二类的构形（如图12），改用断链法后，虽然也可以在五次交换内空出颜色。但在连续转型交换时，却也需要六次交换才能空出颜色。

这个有限次交换的上界是多少，还得要进行证明：对于那个轴对称的图11的构形来说，两个方向的转型交换均在第四次交换后，图就不再是H—构形了。这样，在两个方向前三次交换所得的三个H—构形的图以及原图图12间，就有7种第三类的H—构形。而这7种构形中，无论那一个，无论是从那个方向进行转型交换，最大的交换次数都是不会大于9的。
以上就证明了任何H—构形都是可约的。四色猜测是正确的。证毕。

2、张域典的证明方法：
按构形在转型交换时的交换次数的有限与无限，把H—构形分为两大类。一类是无穷次转型交换也空不出颜色来的构形（如图13和图14），另一类是有限次转型交换就可以空出颜色来的构形。
图13和图14这两个图的解决肯定不能用连续的转型交换了，而只能用解决上面雷明的第一类构形的断链法。图中有一条含有构形三个围栏顶点的A—B环形链，交换经过构形转栏顶点4和5的C—D链，就可以使图变成K—构形而可约。同时在对以上两图的连续转型交换过程中，图总是在雷明的第一类和第二类构形间反复的转化着，随时都可以用断链法进行解决。张先生把这一方法叫做Z—换色程序。

对于用有限次转型交换就可以空出颜色来的所有构形，用连续的转型交换都可以解决问题。但这里仍要解决的是这个有限次转型交换的上界是多大的问题。
由于无穷次转型交换也空不出颜色来的构形在交换过程中，是以每20次转型为周期而无穷循环的，所以有限次转型交换就可以空出颜色来的构形就必须在第20次交换时，图就得转化成可以连续的移去两个同色的K—构形。然后再交换两次，移去两个同色并空出之。所以有限次转型交换的上界是22，即最大22次交换就可以空出颜色来。实际上在转型交换的过程中，图经常会转化成雷明的第一类和第二类构形，若能及时的改成断链法，则能使交换的次数更少。
证毕。
证明仅管完了，但证明是要为了以后的着色做好准备的。这里就存在一个问题，给出一个图，比如就是图13和图14，你如何能判断出它是一个无穷次转型交换也空不出颜色来的构形，还是有限次转型交换就可以空出颜色来的构形呢。如何决定是按Z—换色程序去交换呢，还是按连续转型去交换呢。这完全不象雷明的分类中，一看图中有没有环形链就可以确定是那一类构形了。请张域典先生回答这一问题。

雷  明
二○一九年元月十四日于金堆城

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，