四色猜测证明的姐妹篇（之一）

雷明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）。把这样的两条链就叫双环交叉链。
5、2  赫渥特构形：1890年赫渥特构造的H—图和1921年埃雷拉构造的E—图都是含有双环交叉链的构形，他们都属于渥特图构形一类的构形。有双环交叉链的构形均属于赫渥特图构形。
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、无经过关健顶点的环形链的颜色冲突构形的解决办法
不含有经过关键顶点的环形链的BAB型构形中，因含有双环交叉链，使得A—C链和A—D链不可能进行交换；又因为构形中不含有经过了关键顶点的环形链，而使得A—B链和C—D链也不可能进行交换；且构形本身又是不可连续的移去两个同色的，所以B—C链和B—D链也不可能连续的进行交换。既然B—C链和B—D链不可连续的进行交换，那么我们先交换一个关于B的链，总应该是可以的。这种交换的结果使得构形峰点的位置和颜色都会发生改变，把BAB型的5—轮构形转化成了DCD型或CDC型的5—轮构形。所以把这种交换叫转型交换。
不含有经过了关键顶点的环形链的5—轮颜色冲突构形，既不是不含有双环交叉链的简单的、可约的、属于坎泊的K—构形的5—轮构形，又不是含有经过了关键顶点的环型链的复杂的、属于赫渥特的H—构形的5—轮构形；既不能用坎泊的K—交换法可以直接空出颜色的交换法进行解决，也不能用上面所说的只是为了使构形转化成不含有双环交叉链的断链交换法进行解决。那么就只有用最后一种能使构形的峰点位置和颜色都发生变化的转型交换法来解决了。
谈到转型交换法，就要先谈不含有任何连通链的（当然也就不含有双环交叉链）简单的、可约的、属于坎泊的K—构形的5—轮构形和含有经过了关键顶点的环型链的复杂的、属于赫渥特的H—构形的E—族5—轮构形在进行转型交换时的情况。这两种构形都是BAB型时，在进行转型交换时都是以BAB—DCD—ABA—CDC—BAB四次转型（逆时针方向转型）或以BAB—CDC—ABA—DCD—BAB四次转型（顺时针方向转型）为一个周期的无穷循环转型的构形；而这里我们所研究的构形却没有它们那样含有形成无穷循环转型的条件，既不是不含有任何连通链的K—构形,也不是含有经过了关键顶点的环形链的H—构形，所以是不会出现无穷循环转型现象的。其转型次数一定是有限的，且一定是不循环的。既然转型次数是有限的，就说明最后一次转型得到的构形再转型时就不可能再得到有双环交叉链的H—构形了，而是一个只有一条连通链的可约的K—构形，再进行一次空出颜色的交换，就一定可以空出一种颜色给待着色顶点着上。
既是有限次的不循环的转型，那么就一定会存在一个最大转型次数的上界来进行约束，无约束的转型就可能成为无穷转型的构形了。简单的可约的5—轮构形和复杂的E—族的5—轮构形都是以每四次转型为周期的无穷循环转形，而我们这里的构形在转型时，就应在以上两种构形转型时的第二个转型周期形成之前（即第八次转型之前），就要转化成可约的构形，才不至于出现无穷的循环现象。第八次转型之前的第7次转型，就是该类构形转型交换的最大转型次数的上界值。这里所说的可约构形，一是指可以连续的移去两个同色的可约构形，二是指有经过了关键顶点的环形链的约形，三是指以上两者同时具备的构形。这三种构形都是可以最多再只经过两次交换（连续两次空出颜色的交换或一次断链交换加一次空出颜色的交换）就可以空出颜色来给待着色顶点着上的构形。
10、无经过关键顶点的环形链的构形最大转型次数是7的逻辑证明
现在，对以上的结论——转型交换的最大转型次数一定是有限次的——再用逆否命题与原命同真同假，以及逆命题与原命同真，逆命题为真是原命题成立的充要条件进行逻辑证明如下：
设A是“某类构形经有限次转型后”这句话。B是“可以转化成可约的构形”这句话。这里，某类构形是指“无经过关键顶点的环型链的构形”；可约构形是指“可以连续的移去两个同色的构形，或者含有经过了关键顶点的环形链的构形”；有限次指的是“7次转型”。
则原命题A到B是：无环形链的构形经有限次转型就可以转化成可约的构形。其逆否命题—B到—A是：通过转型转化不成可约构形的构形一定是无穷转型的构形。这个逆否命题是真的。具体的说就是有最简单的可约的5—轮构形和E族构形这样的例子存在。的确，最简单的5—轮构形和E族构形的转型次数都是无穷的，这两种构形永远也不可能通过转型转化成可约的构形。
根据原命题与其逆否命题具有同真同假的性质，可以判定无环形链的构形经过有限次转型是可以转化成可约构形的原命题是真命题。证毕。
现在，还可以进行验证如下：
原命题的逆命题B到A是：通过转型可以转化成可约构形的构形，其转型次数一定是有限的。这个逆命题也是真命题。无环形链的构形都是在有限次的转型内转化成可约构形的。原命题与其逆命题同真，说明其逆命题为真是原命题成立的充要条件。即没有逆命题成立，原命题一定不成立，而有了逆命题成立，则原命题也一定成立。
这就用不同的方法都证明了无环形链的构形的转型次数一定是有限次的结论是正确的。
11、四色猜测是正确的：
到此，应该说四色猜测的证明就已经结束了，因为我们已经解决了各种情况下的不可避免构形的可约性的问题。四色猜测是正确的。
在对构形的分类过程中，都是采取了只有两种可能情况的办法，非此即彼，避免了漏洞的出现。
整个证明是没有画图和着色的。这就说明了我于1992年在陕西省数学会第七次代表大会暨学术交流会（地点是在西安空军工程学院）上所作《赫渥特图的4—着色》的学术论文报告最后所提出的“不画图不着色证明四色猜测”的目标是能够实现的。
12、用着色实践检验上术结论是否正确：
为了检验无经过关键顶点的环形链的构形转型交换的最大次数的正确性，我们再举几个实际着色的例子，看看其转型次数与上面正文中用逻辑推理所得出的结果是否一致。
1、用非极大图的构形进行验证
图3是一个无经过关键顶点的环形链的BAB型的含有双环交叉链的非极大图的构形。对该构形进行不同方向的连续转型，如果某次转型从一个同色顶点交换了与其对角顶点的颜色构成的色链后，不能新生成从另一个同色顶点到其对角顶点的连通链时，应该说问题就已经得到解决，可以连续的移去另一个同色，空出两个同色顶点用过的颜色，给待着色顶点着上。颜色冲突问题就可以得到解决。

但我们却有意的不去这样做，而是在平面图许可的范围内，增加顶点或边，人为的构造从另一个同色顶点到其对角顶点的连通链，使图仍是一个不可以连续的移去两个同色的构形，再继续的进行转型。如果在后续的某次转型后，不再可能人为的构造从另一个同色顶点到其对角顶点的连通链时，这时的转型次数再减去1，就是转化成可以连续的移去两个同色的最大的转型次数。结果两个方向转型的最大转型次数都是5次，也都是小于7次的。
2、用极大图的构形进行验证
图4是我仿敢峰先生构造E—图构形（敢峰先生称其为终极图）时的转型演绎法，由最简单的双环交叉链构形开始，构造的一个属于极大图的无经过关键顶点的BAB型的含有双环交叉链的极大图构形。该构形好象是含有经过了关键顶点——双环交叉的A—C链和A—D链的两个末端顶点C和D（图中的两个加大顶点C和D）——的C—D环形链，但该环形链却并没有把另一对关键顶点——双环交叉的A—C链和A—D链的共同起始顶点A和交叉顶点A（图中的两个加大顶点A）——分隔在该环的两侧，所以不是含有经过了关键顶点的环形链的构形。

这个构形两个方向转型的最大次数只是4次，也都是小于7次的。逆时针方向转型时，不用转型（即转型次数是0时）就是一个可以连续的移去两个同色B的BAB型的可约构形；顺时针方向转型时，1至4次转型的结果全部都是含有经过了关键顶点的A—B环形链的构形，都可以改用断链交换法提前结束转型；而且第4次转型的结果既是一个可以连续的移去两个同色B的可约构形，也是一个含有经过了关键顶点的A—B环形链的构形。
3、用具体图着色实例进行验证

①  1935年欧文给出的那个无经过关键顶点的环形链的构形（如图5，待着色顶点V是隐型画法），由于其中的A—B链和C—D链都是对于构形的峰点A与5—轮构形的两个底角顶点C和D（即两条双环交叉链的末端顶点）的中点的连线呈对称状态的，所以无论从那个方向转型时，转型次数都是4次，也不大于7。且都在第3次转型时就得到含有经过了关键顶点的环形链的构形，也都可以用断链交换法提前结束转型。
②  张彧典先生的Z—构形中，Z1到Z5和Z11到Z15的十种Z构形都是属于无经过关键顶点的环形链的构形，转型次数都是在小于5次时，就转化成了可以连续的移去两个同色的可约构形或是转化成了含有经过了关键顶点的环形链的构形。
③  张先生的第八构形的放大图也是无经过关键顶点的环形链的构形，但该构形中却含有局部的环形链，也是可以用断链法使其中一条双环交叉链断链的，从而转化成只有一条连通链的可约构形。
④  前面的图3是标准的无经过关键顶点的环形链的构形，A—B链和C—D各都只有一条，且是非树状的单条道路。各条链中相同颜色的首、尾顶点间，只隔着一个与其呈相反色链中的顶点，改变该顶点的颜色为其相反色链中的颜色时，图就转化成了含有经过了关键顶点的环形链的构形，也就可以直接使用断链交换法了。由此也可以看出，无经过关键顶点的环形链的构形，也是可以直接转化成含有经过了关键顶点的环形链的构形的。但这是个个别的现象，还是普遍的规律，我们现在还不知道。可以作为一个猜想提出，如果真是这样，平面图的4—着色就更加方便了。

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

注：此文已于二○二一年三月十日在《中国博士网》上发表过，网址是：
这次编入《四色猜测证明的姐妹篇》时，进行了一定的修改。

（未完，接下贴）

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，