有关术语解释与四色猜测的证明

雷明85639720

有关术语解释与四色猜测的证明
雷  明
（二○二一年三月九日）
（这里我不会发图，请到《中国博士网》中去看）

1、地图
这里所说的地图主要是指行政区划地图。地图是一个特殊的平面图，它是一个不含割边的、但可以含有“国中之国”的3—正则平面图。地图中各顶点的度都是3，各面的边数都大于等于1。地图的对偶图是一个含有悬挂顶点的极大平面图，极大平面图中各个面都是3边形面，各顶点的度都大于等于1，且处在一个轮的中心位置。给地图中各面的染色就相当于对其对偶图的顶点着色。这就把一个地理学的问题转化成了一个数学问题。
四色猜测的提出因对地图的染色而开始，证明时也应从地图开始着手，即先从地图的对偶图——极大图——开始。证明了极大图的四色猜测是正确时，一个4—着色的极大图经增顶、加边、去顶和减边后所得到的任意平面图的色数只会是减少，决不会再增加。这也就证明了任意平面图的四色猜测是正确的。
2、构形
图的着色总是一个顶点接着一个顶点的着，任何极大平面图着色的中途，特别是在最后，都一定会遇到一个要着色的顶点，与其相邻的顶点都是着了色的情况。把这种只有一个顶点未着色的图中做“构形”，除了未着色的顶点外其他顶点都已进行了4—着色，且符合着色要求。构形中未着色的顶点叫待着色顶点，与待着色顶点相邻的顶点叫围栏顶点。一个构形中只有一个待着色顶点，而不会有第二个。
3、不可避免构形
“构形”一词是坎泊最早提出并首先使用的。1879年坎泊提出并证明了任何地图中一定至少存在“一国与一国”、“一国与两国”、“一国与三国”、“一国与四国”和“一国与五国”五种相邻关系中的一种。这就是坎泊的不可避免构形集。在对地图的对偶图极大平面图着色时，若遇到了围栏顶点数大于等于6的构形时，一定是可以把待着色顶点移动到度是小于等于5的顶点上，因为图论中已经证明，任何平面图中一定存在着度是小于等小于5的顶点。这就把一个研究对象的围栏顶点是任意大的无穷问题转化成了有穷的问题。与坎泊的构形集相应的极大平面图的不可避免构形集则是：｛1度顶点，2度顶点，3度顶点，4度顶点，5度顶点｝。
4、颜色冲突构形
颜色冲突，有人也叫染色困局。当围栏顶点所占用的颜色数已经达到了四种时，就叫颜色冲突。看来，1度顶点，2度顶点和3度顶点是不会产生颜色冲突的，因为其围栏顶点决不会占用完四种颜色，是直接可以给待着色顶点着上四种颜色之一的。而只有4度顶点和5度顶点才可能会出现颜色冲突的问题，须要通过颜色交换才能空出颜色来给待着色顶点的。
5、不可避免构形的一级分类
分类的重要标志：是有、无双环交叉链。
5、1  坎泊构形：当可能会产生颜色冲突的构形中不含双环交叉链时，坎泊早在1879年已证明是可约的，即可4—着色的。把不含双环交叉链的颜色冲突构形和不会产生颜色冲突的构形合起来，统一叫做坎泊构形。
所谓双环交叉链，就是在BAB型的5—轮构形中，既有从峰点A到其对角C的A—C连通链，又有从峰点A到其另一对角D的A—D连通链，且两链在中途又有相交叉的顶点（着色为A）。把这样的两条链就叫双环交叉链，如图1。

5、2  赫渥特构形：1890年赫渥特构造的H—图和1921年埃雷拉构造的E—图都是含有双环交叉链的构形，他们都属于渥特图构形一类的构形。图1的构形也属于赫渥特图构形。
6、构成赫渥特构形的必要条件
没有双环交叉链，不可能构成赫渥特构形，但有了双环交叉链的构形却不一定都是赫渥特构形。如图1的含有双环交叉链的“九点形”非极大图的构形，当把图通过增加边而变成极大图时，可得到四种不同的结构形式。其中有三种都是可以连续的移去两个同色的可约构形，而只有一种才是真正的赫渥特构形。所以说双环交叉链是构成赫渥特构形的必要条件。真正意义上的赫渥特构形是：含有双环交叉链、且不能连续的移去两个同色的、又出现了颜色冲突的构形。同理，虽然是含有双环交叉的，但只要是可以连续的移去两个同色的构形，也都应是属于坎泊已证明过是可约坎泊构形。
7、赫渥特构形中的关键顶点
既然双环交叉链是构成赫渥特构形的必要条件，那么，解决这类构形的办法就只有把双环交叉链断开。能否做到这一点，我们可以这样来分析：含有双环交叉链的且不能连续的移去两个同色的构形中，有四个顶点是很关键的顶点，一是双环交叉链的共同起始顶点（着A）和交叉顶点（也着A）,二是双环交叉链的两个末端顶点C和D。这四个顶点都在双环交叉链上，只要其中一个顶点的颜色改变了，双环交叉链也就不存在了。但这四个关键顶点的颜色进行改变却是要有一定的条件的，不是随便想改就能改了的。
8、不可避免构形的二级分类（即赫渥特构形的分类）
分类的重要标志：是有、无经过了构形关键顶点的环形链。
如果构形中有一条经过了双环交叉链末端顶点C和D的环形的C—D链，则该链一定把另外两个关键顶点A分隔在了C—D环的两侧，交换该环内外两侧的任一条A—B链，都会使双环交叉链断开，使图转化成可约的坎泊构形，问题就得到了解决。如果构形中有一条经过了双环交叉链的共同起始顶点A或者交叉顶点A的A—B链，则该链也一定把另外两个关键顶点C与D和另外的非关键顶点的C与D分隔在了A—B环的两侧，交换该环内外两侧的任一条C—D链，也都会使双环交叉链断开，使图转化成可约的坎泊构形，问题也就得到了解决。
以上两种交换的结果，主要都是把双环交叉链断开了，并没有空出颜色，所以叫做断链交换法。双环交叉链断开后，还要再进行坎泊的空出颜色的交换，才能解决问题。
9、无经过关健顶点的环形链的颜色冲突构形的解决办法
既然这类构形没有经过关键顶点的环形链，那就一定不能使用断链交换法了。由于该类构形是不可连续的移去两个同色的构形，是否可以先移去一个同色，使构形进行转型呢？然后再按转型后的构形的属性进行处理。在上面的E—图，进行转型交换时，会出现无穷循环转型的现象，但E—图中却有经过了关键顶点的环形链，而这里研究的构形却没有这一特征，所以这类构形一定不会产生无穷循环转型，其转型次数一定是有限且不循环的。E—图的循环周期最小是4，由于在第二个小循环周期（8次转型）没有出现之前，是不能确定其是否是出现了循环现象的，所以这类构形的转型一定要在7次转型之内结束，使图转化成一个可以连续的移去两个同色的可约构形或者转化成有经过了关键顶点的环形链的构形。
但这只是一个用逻辑推理的办法得出的最大转型次数的有限次数有上界，还需要经过逻辑证明。
10、无经过关键顶点的环形链的构形最大转型次数是7的逻辑证明
现在，对以上的结论再用逆否命题与原命同真同假，以及逆命题与原命是同真，逆命题为真是原命题成立的充要条件进行逻辑证明，就可以了。
设A是某类构形经有限次转型后。B是可以转化成可约的构形。这里，某类构形是指无经过关键顶点的环型链的构形；可约构形是指可以连续的移去两个同色的构形，或者含有经过了关键顶点的环形链的构形；有限次指的是7次转型。
则原命题A到B是：无环形链的构形经有限次转型就可以转化成可约的构形。其逆否命题—B到—A是：通过转型转化不成可约构形的构形一定是无穷转型的构形。这个逆否命题是真的。具体的说就是有E族构形是这样的例子存在。的确，E族构形的转型次数是无穷的，永远也不可能通过转型转化成可约的构形。
根据原命题与其逆否命题具有同真同假的性质，可以判定无环形链的构形经有限次转型可以转化成可约构形的原命题是真命题。
现在还可以进行验证如下。
原命题的逆命题B到A是：可以通过转型转化成可约构形的构形的转型次数一定是有限的。这个逆命题是真命题。无环形链的非E族构形都是这样的。原命题与其逆命题同真，说明其逆命题为真是原命题成立的充要条件。没有逆命题成立，原命题一定不成立，有了逆命题成立，则原命题也一定成立。
现在就用不同的方法都证明了无环形链的构形的转型次数一定是有限的结论是正确的。
11、四色猜测是正确的：
到此，应该说四色猜测的证明已经结束了，四色猜测是正确的。
在对构形的分类过程中，都是采取了只有两种可能的办法，非此即彼，避免了漏洞的出现。
我于1992年在西安作《赫渥特图的4—着色》的学术论文报告最后所说的“不画图不着色证明四色猜测”的想法最终实现了。

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

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

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，

雷明85639720

，，，，，，，，