平面图的不可避免构形及其可约方法

雷明85639720

平面图的不可避免构形及其可约方法
——兼论四色猜测的证明
雷  明
（二○二○年六月二十七日）
（这里又发不上去图片了，请到＜中国博士网＞上去看）

    1、目前研究四色问题应解决的主要问题
四色问题因给地图的着色而引起，所以证明四色猜测还得从研究地图而着手。地图本身就是一个无割边的3—正则的平面图（每条边都与两个面相邻，每个顶点都连有3条边），给其面上的着色就是对其对偶图——无环极大平面图（每个面都是3—边形面）——的顶点着色。这就把一个地理学问题转化成了一个数学问题了。极大图的每个顶点都是处在一个轮形图的中心位置，又因为任何平面图中都一定至少存在着一个顶点的度是小于等于5的，所以平面图的不可避免构形就只是度小于等于5的轮构形。这又就把一个研究对象是无穷多的问题也转化成了一个研究对象是有穷的问题了。
1879年，坎泊已经证明了不含双环交叉链的构形都是可约的，却没有彻底解决含有双环交叉链的构形的可约性的问题。所谓的“双环交叉链”，是指在BAB型的5—轮构形中，从2A到5C的A—C链和从2A到4D的A—D链既有共同的起始顶点2A，中途又有相交叉的交叉顶点8A，两链与待着色顶点V均构成了一个“环”，所以叫做双环交叉链。图1就是四个含有双环交叉链的构形。虽然同样都是含有双环交叉链的构形，但有的却是可以连续的移去两个同色B的可约构形（如图1，a，图1，c和图1，d三图。其图中除了构形的围栏边外，其他任何边也都可以认为是由该边两个端点顶点的颜色构成的色链）；而有的则是不可以连续的移去两个同色B的构形（如图1，b。同样的，其图中除了构形的围栏边外，其他任何边也都可以认为是由该边两个端点顶点的颜色构成的色链。除此之外，在顶点6C和7D之间也不能存在任何顶点，否则也将是一个可以连续的移去两个同色B的构形）。

不含双环交叉链的构形和虽含有双环交叉链但可以连续的移去两个同色B的构形都已经是可约的构形，就统一叫做K—构形，即坎泊构形；相应的则把含有双环交叉链的又不可以连续的移去两个同色B的构形，叫做H—构形，即赫渥特构形。目前研究四色问题，主要的任务就是解决含有双环交叉链但又不可以连续的移去两个同色B的构形的可约性问题了。
2、H—构形的分类及相应的解决办法
只所以H—构形不可以连续的移去两个同色B，是因为从任何一个B色顶点交换了与其对角顶点的颜色构形的色链后，就会新生成从另一个B色顶点到它的对角顶点的连通链，而不能连续的移去两个同色B。既然这种情况是因具有双环交叉链而引起，那么我们就想办法把双环交叉链进行破坏，使构形转化成不含双环交叉链的可约的K—构形。
双环交叉链上有四个关键的顶点，一是两链的共同起始顶点2A，二是两链的交叉顶点8A，三是两链的末端顶点5C和4D（如图2）。只要这四个顶点的任何一个顶点的颜色进行了改变，就可以使双环交叉链的两条或一条断开，图就转化成了不含双环交叉链的可约的K—构形了。

（1）有环形链的H—构形
如何能使双环交叉链断开呢？就得在A—B链和C—D链上下功夫。因为A—B链和C—D链互为相反链，是不能相互穿过的。所以只要有一条是经过了以上四个栏顶点的环形链时，其相反链一定被隔在该环形链的两侧而不连通（如图3和图4）。这时从以上四个顶点之一交换被隔在环内或环外的任一条相反链，一定可以使双环交叉的两条链都断开或者不存在双环交叉链了（因为4D和5C是相邻的，所以两个顶点是同时改变颜色的，两链也就同时断开了，而2A和8A本身就是两链的共同顶点，改变了任何一个顶点的颜色，两条链也就同时断开了），构形也就转化成了可约的K—构形。这就是有环形链的H—构形及其解决的方法。这一方法也可以叫做“断链交换法”。

（2）无环形链的H—构形

还有一种是没有环形链的H—构形，即通过经上四个顶点的链均不是环形链的构形（如图5）。对这种无环形链的H—构形来说，虽是不可能用断链交换法解决问题，但这种构形的解决方法却是较多的。
一是把图5中其中的一个加大顶点的颜色进行改变，就可以使图转化成如图３和图４一样的有经过了上述关键顶点的环形链的H—构形（如图3和图4），可以再通过断链交换方法转化成可约的K—构形。
二是交换一个关于两个同色B的链，使构形转型，并转化成有经过了关键顶点的环形链的H—构形，或者直接转化成可以连续的移去两个同色的可约的K—构形。图6是对图5从顶点3交换了B—C链的结果，是一个CDC型的有经过了双环交叉链末端的A—B环形链的H—构形；图7是对图5从顶点1交换了B—D链的结果，是一个DCD型的可以连续的移去两个同色D的可约的K—构形（读者可以自已做一下，看是否可以连续的移去两个同色D）。
三是用连续转型交换的方法解决无环形链的极大图（H—构形）的可约性问题。
以上研究的图都是非极大图型的H—构形，也都是可约的。但对于极大图来说，有环形链的H—构形也一定是可以通过“断链关换法”解决问题的；而对于无环形链的极大图构形来说，“转型交换”的次数是否是有限的呢？
我们可以这样来考虑和分折问题。在对图5的非极大图的构形进行转型时，当遇到了转型对果是可以连续的移去两上同色时，我们可以人为的在平面图的范围内，适当的增加顶点和边，使其不能连续的移去两上同色。也就是说，当交换了一个关于两个同色的链后，就人为的在平面图范围内构造从另一个同色顶点到其对角顶点的连通的对角链，然后再对其进行连续的转型。看一看转型的次数是否是有限的。如果有限，四色问题就得到了彻底解决，否则四色猜测就是错误的。这样连续的构造连通链，也就相当于把非极大图转化成了极大图。
现在对图5进行逆时针和顺时针两个方向的连续转型如下：
㈠逆时针方向转型，在第五次转型后，图就是一个可以连续的移去两个同色的可约的K—构形。共进行了有限的五次转型，七次交换（如图8，0到图8，7）。

㈡顺时针方向转型，转型的次数及结果与逆时针方向转型是相同的（如图9，0到图9，7），也是五次转型，七次交换，也是在第五次转型后，图就是一个可以连续的移去两个同色的可约的K—构形。

为什么两个方向都是在第五次转型后就转化成了可以连续的移去两个同色的可约的K—构形了呢？还要进一步证明这是一个必然的结果。因为每转型交换一次，构形的类型即发生一次变化，逆时针转型的变化规律是：BAB型—DCD型—ABA型—CDC型—BAB型；顺时针转型的变化规律是：BAB型—CDC型—ABA型—DCD型—BAB型。都是每转型四次一个周期，所以前四次转型所得的图都仍是H—构形的图，只有到了第五次转型后，所得的图才变成了K—构形的图了。
（3）无环形链的H—构形的最大转型次数
现在来回答最大的转型次数道底是多少的问题。两个方向的第五次转型得到的都是K—构形，说明小于等于四次转型的结果都仍然是H—构形，共有9个H—构形。这9个构形进行逆时针方向和順时针方向转型时的转型次数之和都是10，交换次数之和也都是14。因此，单方向转型的最大转型次数是5（10/2），最大交换次数是7（14/2）。也就是说，对于任何一个无环形链的H—构形来说，总有一个方向的转型次数是小于等于5的，也总有一个方向的交换次数是小于等于7的。其交换次数也一定等于转型次数加2
在对无环形链的极大图（H—构形）做连续转型交换时，还经常会遇到图转化成了有环形链的H—构形的情况，这时就要尽早的用断链交换法进行解决。我这里所说的最大转型次数与张彧典先生所说的最大“颠倒次数”是有区别的。我的结论是只适用于无环形链的H—构形，并不是包括有环形链的构形在内的所有非埃雷拉图的构形。
3、四色猜测是正确的
现在，含有双环交叉链，又但不可以连续的移去两个同色B的构形的可约性问题已经解决了，则平面图的所有不可避免构形就都已经是可约的了，那么四色猜测也就证明是正确的了。
附：平面图的不可避免构形图表
（见下页的图表）

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


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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，