无环形链的H—构形可约性的研究——兼论四色猜测的证明

雷明85639720

无环形链的H—构形可约性的研究——兼论四色猜测的证明
雷  明
（二○二○年四月五日）
（在这里我发不出图，请到《中国博士网》中去看）

对于含有经过了构形围栏顶点的环形链的H—构形，用断链交换法交换环形链内、外的任一条与环形链呈相反链的色链，就可使构形中的双环交叉链断开，构形转化为无双环交叉链的K—构形而可约。而对于不含有经过了构形围栏顶点的环形链的H—构形，可以有多种解决的办法，现在分析如下：

1、直接使构形转化为含有经过了构形围栏顶点的环形链的构形：
改变某一条经过了构形的围栏顶点的链中的某一顶点的颜色（如图中的加大顶点，改成其相反色链的颜色），就可以直接使另一条经过了构形的围栏顶点的链成为环形链，而使该链断开，成为两条不连通的色链（如图1和图2）。有了环形链，就可使用断链法使构形转化为K—构形而可约。适用这种转化的条件是，全图中经过了构形围栏顶点的两条各不呈环形链的色链均只是一条的无环形链的H—构形。这里，对个别顶点颜色的改变，构形的类型并没有发生变化，即构形的峰点的位置和颜色均未变（如图１和图２的四个图仍都是BAB型的构形）。

2、通过一次转型交换，使构形转化成有环形链的构形：
经过一次转型交换（即交换两个同色之一与其对角顶点的颜色构形的色链），使构形转化成有环形链的构形（如图3和图4）。请注意，图3和图4是不同的两个图。图３是从围栏右上角的B交换了B—C链的结果，图4是从左上角的B交换了B—D链的结果。

适用这种转化的条件是，经过了构形BAB三个围栏顶点的色链，必须又是经过了双环交叉链的交叉顶点A的无环形链的H—构形。可以看出，图如果是含有既经过了构形BAB三个围栏顶点，又经过了双环交叉链的交叉顶点A的有环形链的H—构形，无论是从那个方向施行转型交换，也一定是可以转化成只含有经过构形两个围栏顶点的一类有环形链的构形的。

3、通过一次转型交换，使构形转化成K—构形：

通过一次转型交换，使构形转化成交换了一个同色顶点与其对角顶点的颜色构成的色链后，不再生成由另一个同色顶点到其对角顶点的连通链的可约的K—构形（如图5）。适用这种转化的条件也是，经过了构形BAB三个围栏顶点的色链，也必须又是经过了双环交叉链的交叉顶点A的无环形链的H—构形（但施行转型交换的方向正好与使构形转化成有环形链的构形的方向相反）。第二次转型交换（如图5，c）后，不再生成从另一个同色顶点D到其对角顶点B的连通链D—B，说明第一次转型交换的结果（如图5，b），就是一个可以连续的移去两个同色D的可约的K—构形。

4、通过连续的转型交换，使构形最终转化成K—构形：

通过连续的转型交换，在交换了一个同色顶点与其对角顶点的颜色构成的色链后，若不生成从另一个同色顶点到其对角顶点的连通链时，就人为的构造由另一个同色顶点到其对角顶点的连通链，使构形仍保持是H—构形，使图最后成为不可能再构造出从另一个同色顶点到其对角顶点的连通链，成为可约的K—构形为止（如图6）。图6中到了第6次转型交换（如图6，6）后，不可能再构造出从另一个同色顶点C到其对角顶点B的连通链C—B，说明第5次转型交换的结果（如图6，5），就是一个可以连续的移去两个同色C的可约的K—构形。这一构形的最大转型交换次数是5，最大的交换次数是7。

以上图中，从峰点引出的虚线链，是从另一个同色顶点到其对角顶点的连通链的人为构造部分，实线链是非人为构造部分；另一条虚线链，是已交换过的关于一个同色顶点的链。图6是按顺时针方向进行转型交换的，若按逆时针方向进行转型交换，也是同样的结果，即5次转型，7次交换。如图7。

5、通过一次交换，使构形直接转化成无双环交叉链的K—构形：
以上说的都是非环形链的两条链都只是一条的无环形链的构形，如果至少有一条非环形链的色链是不连通的几个部分时，就可以通过对某种链的某一条进行交换，使构形直接转化成无双环交叉链的K—构形（如图8）。图8，a中A—B链和C—D链都各是两条，图8，b和图8，c中各只交换了一条A—B链和C—D链，两图都已不存在双环交叉的A—C链和A—D链了。如果对另外一条A—B链和C—D链进行交换，也可得到无双环交叉链的K—构形。张彧典先生的《探秘》一书中的第八构形的放大图，就可以这样来处理，该书中的第八构形也都可以用以上的各种方法的任何一种进行处理。

6、对无环形链的H—构形可约性的分析：
从以上对各种无环形链的H—构形的可约性的研究看，除了连续的施行转型交换并人为的构造从另一个同色顶点到其对角顶点的连通链的方法外，其他几种方法都是一次转型后，图就变成了可以连续的移去两个同色的可约的K—构形，或者是变成有环形链的H—构形了，有的还可以直接变成无双环交叉链的K—构形，最多3次交换就可以空出一种颜色给待着色顶点。而只有连续的施行转型交换并人为的构造从另一个同色顶点到其对角顶点的连通链的方法，需要交换的次数多一些；但也是在不超过有限的5次转型交换后，图就变成了一个可以连续的移去两个同色的可约的K—构形了。最大的交换次数只是7。
从连续的转型交换并人为的构造从另一个同色顶点到其对角顶点的连通链的方法看，逆时针方向转型与顺时针方向转型的结果是左右不相同的（因为转型前图的左右就是不相同的），转型前是非极大图，转形结束后仍是非极大图。把转型过程中增加的顶点和边，都增加到原图中去（这时图仍是非极大图），再施行连续转型交换时：同方向的转型仍是转型5次，交换7次就可空出颜色来；而相反方向的转型却在第2次转型后，就不可能生成从另一个同色顶点到其对角顶点的连通链；说明一次转型后就是一个可以连续的移去两个同色的可约的K—构形了。若把两种方向施行连续转型交换中增加的顶点和边分别都增加了原图中去，并在图中再增加边，变成极大图后，再分别施行两个方向的转型交换时，无论是逆时针方向转型，还是顺时针方向转型，则最多转型两次，就不可能生成从另一个同色顶点到其对角顶点的连通链了。这一现象说明，极大图的转型交换次数一定是比非极大图的转型交换次数要少的。
无环形链的H—构形，不管是极大图还是非极大图，都是有多种方法使其可约的；构形本身不但可以作为一个单独的图是可约的，而且作为一个分子图（分子构形）嵌入某个极大图的一个面内，构成一个极大或非极大的图时，也都一定是可约的。
7、对张彧典15个Z构形的剖析：
图就不再一一的画了，有愿意研究者，请按张先生的15个Z构形自已去画，其结果就是以下文字中所说的内容。
Z1构形：A—B链和C—D链各只有一条；逆时针不转型，共交换两次，可空出两个同色B来；顺时针转型5次后，得到含有经过三个围栏顶点的C—D环形链的构形，再交换两次可空出一种颜色。严格的说，Z1就不是H—构形，因为其进行了一次逆时针转形后，不生成从第二个同色B到其对角顶点的连通链B—C，是一个可以连续的移去两个同色B的可约的K—构形。
Z2构形：A—B链有两条，C—D链只有一条。但不能交换任一条A—B链，使图成为无双环交叉链的K—构形。因为隔断A—B链的C—D环形链并没有经过构形的围栏顶点。仍保有留着埃雷拉图不能交换C—D环形链内、外的任一条A—B链的基本特征；逆时针转型1次，共交换3次可空出一种颜色；第2次转型后不生成从另一个同色顶点到其对角顶点的连通链，可见从第1次转型交换后，就是一个可约的K—构形；顺时针转型时也是5次转型后，得到含有经过三个围栏顶点的A—B环形链的构形，再交换两次可空出一种颜色。
Z3构形：A—B链和C—D链各只有一条；逆时针转型2次，共交换4次可空出一种颜色；第3次转型后不生成从另一个同色顶点到其对角顶点的连通链，可见从第2次转型交换后，就是一个可约的K—构形；顺时针转型3次后，得到含有经过三个围栏顶点的C—D环形链的构形，再交换两次可空出一种颜色。
Z4构形：A—B链有两条，C—D链只有一条；逆时针转型3次，共交换5次可空出一种颜色；第4次转型后不再生成从另一个同色顶点到其对角顶点的连通链，可见从第3次转型交换后，就是一个可约的K—构形；顺时针转型2次后，得到含有经过三个围栏顶点的A—B环形链的构形，再交换两次可空出一种颜色。
Z5构形：A—B链和C—D链各只有一条；逆时针转型4次，共交换6次可空出一种颜色；第5次转型交换后，不生成从另一个同色顶点到其对角顶点的连通链，可见从第4次转型交换后，就是一个可约的K—构形；顺时针转型1次后，得到含有经过三个围栏顶点的C—D环形链的构形，再交换两次可空出一种颜色。
Z6构形，Z7构形，Z8构形，Z9构形，Z10构形：这5个构形都是含有经过围栏顶点的环形链的构形，可以用断链法而不用连续的转型交换法。
Z11构形：A—B链和C—D链各只有一条；逆时针转型1次，就转化成含有经过围栏顶点的环形链的构形，可用断链法，不再用转型交换法。顺时针转型4次，共交换6次可空出一种颜色；第5次转型交换后，不再生成从另一个同色顶点到其对角顶点的连通链，可见从第4次转型交换后，就是一个可约的K—构形，再交换两次可空出一种颜色。
Z12构形：A—B链有两条，C—D链只有一条；逆时针转型2次，就转化成含有经过围栏顶点的环形链的构形，可用断链法，不再用转型交换法。顺时针转型3次，共交换5次可空出一种颜色；第4次转型交换后，不再生成从另一个同色顶点到其对角顶点的连通链，可见从第3次转型交换后，就是一个可约的K—构形，再交换两次可空出一种颜色。
Z13构形：逆时针转型3次，就转化成含有经过围栏顶点的环形链的构形，可用断链法，不再用转型交换法。顺时针转型2次，共交换4次可空出一种颜色；第3次转型交换后，不再生成从另一个同色顶点到其对角顶点的连通链，可见从第2次转型交换后，就是一个可约的K—构形，再交换两次可空出一种颜色。
Z14构形：A—B链有两条，C—D链只有一条；逆时针转型4次，就转化成含有经过围栏顶点的环形链的构形，可用断链法，不再用转型交换法。顺时针转型1次，共交换3次可空出一种颜色；第2次转型交换后，不再生成从另一个同色顶点到其对角顶点的连通链，可见从第1次转型交换后，就是一个可约的K—构形，再交换两次可空出一种颜色。
Z15构形：A—B链和C—D链各只有一条；逆时针转型5次，就转化成含有经过围栏顶点的环形链的构形，可用断链法，不再用转型交换法。顺时针时，不转型就是一个可以连续的移去两个同色B的可约的K—构形。
从以上对张先生的15个Z构形的剖析看，连续施行转型交换的转型次数均没有大于5的，总的交换次数也没有大于7次的。这其中有些图转型的结果是得到了可以连续的移去两个同色的可约的K—构形，有些图转型的结果却是得到了有环形链的构形，再进行一次断链交换和一次空出颜色的交换后，就可空出一种颜色。可见，我们从前面“4、通过连续的转型交换，使构形最终转化成K—构形：”中的图6和图7得出的结论是正确的，即转型交换的最大转型交换次数是5，总的最大交换次数是7。
8、对所谓交换次数大于20次的构形的剖析：
现在再来看一看所谓的交换次数大于20次的构形，是不是需要交换20次以上。
我和张先生给(构造)出的转形交换次数大于20次的构形中,都含有经过了构形围栏顶点的环形链,都可以用断链交换法(即张先生的Z—换色程序)进行解决。不需要用转型交换法。交换的次数最多是三次。
转形交换21次的构形中有经过了2个围栏顶点的C—D环形链；
转形交换22次的构形中有经过了3个围栏顶点的A—B环形链；
转形交换23次的构形中有经过了2个围栏顶点的C—D环形链；
转形交换24次的构形中有经过了3个围栏顶点的A—B环形链；
转形交换25次的构形中有经过了2个围栏顶点的C—D环形链；
转形交换26次的构形中有经过了3个围栏顶点的A—B环形链；
需要3次转型交换的赫渥特图和无穷次转型交换的埃雷拉图：
赫渥特图（H—图）构形中有经过了2个围栏顶点的C—D环形链；
埃雷拉图（E—图）构形中有经过了3个围栏顶点的A—B环形链；
张先生《放大》一文中的所有图都有经过了3个围栏顶点的A—B环形链；
我构造的需要交换10次的构形和需要交换16次的构形，以及张先生构造的需要交换11次，12次，13次，14次和15次的构形，其中不是含有经过了围栏顶点的环形链，就是转型次数不大于5时，就已转化成了含有经过了围栏顶点的环形链的构形，再交换两次都可以空出一种颜色来，都不需要高达10次以上的转型交换。
9、最大的转型交换次数是多少：
从以上的研究可以看出，任何无环形链的H—构形，都可以在5次转型交换（包括第5次）内，使图转化为有环形链的构形，或转化为可以连续的移去两个同色的可约的K—构形，或者直接转化为无双环交叉链的可约的K—构形。包括埃雷拉图在内，不但其本身就是有环形的构形，经过一次转型后，也仍然是有环形链的构形；而且以后每一次转型，得到的都是有环形链的构形，都可以用断链交换法进行解决。这样看来，任何无环形链的H—构形，都是可以在有限的5次转型之内，使构形转化为直接或间接的可约的构形而解决问题。再也不需要证明转型交换的最大交换次数是多少的问题了。
10、四色猜测的证明：
H—构形分为“有环形链的构形”和“无环形链的构形”两大类，有环形链的构形用“断链交换法”进行解决，而无环形链的构形则用“转型交换法”进行解决，总可以在有限的5次转型交换之内，使图转化为直接可约的K—构形或转化为间接可约的有环形链的构形。这样，所有的H—构形都是可约的了，加上坎普已证明都是可约的K—构形，所有的平面图的不可免构形就都是可约的了。四色猜测就被证明是正确的了。

雷  明
二○二○年四月五日于长安

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

,,,,,,,,,,

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，