证明四色猜测的关键是解决颜色冲突问题

雷明85639720

证明四色猜测的关键是解决颜色冲突问题
雷  明
（二○二○年十二月二十日）

1、把无穷问题转化成了有穷问题：
四色问题因给地图着色而引起，证明时还得先从地图开始。地图是一个3—正则的平面图，每个顶点的度都是3（即三界点）。给地图的面上的染色就是对其对偶图——极大平面图的顶点着色。这就把一个地理问是转化为一个数学问题了。
极大平面图的每个面都是3—边形面，每个顶点都是处在一个轮形图的中心顶点，所以在对极大平面图着色时，在着色的中途，特别是在着色的最后，都一定会遇到待着色的顶点的所有轮沿顶点都已着色的情况。把这种只有一个顶点未着色，而其他顶点都已进行了4—着色的图，叫做“构形”，把与待着色顶点相邻的顶点叫“围栏”顶点。
极大平面图中的任何一个顶点都可能作为待着色顶点，其度也是任意的。正好在图论中已经证明了，任何平面图中一定存在着度是小于等于5的顶点。这样，待着色顶点的度是小于等于5的构形，就成了（极大）平面图中的不可避免构形。这就又把一个无穷问题又转化成了一个有穷的问题。研究四色问题时，只要研究度是小于等于5的待着色顶点的着色问题就可以了。因为在对极大平面图着色时，一定是可以把最后的待着色顶点放在度是小于等于5的顶点上。
2、什么是颜色冲突问题：
着色时，最后所剩下的待着色顶点的围栏顶点数是小于4或围栏顶点所占用的颜色数也小于4时，该待着色顶点一定是至少还有一种颜色可着的；把围栏顶点数是4或5，围栏顶点所占用的颜色数等于4时的这种情况，就叫做发生了颜色冲突。坎泊早在1879年就已经解决了平面图中度是4和5的、不含双环交叉链的不可避免构形，在发生了颜色冲突时的可约性问题（即可4—着色的问题）；目前研究四色问题主要的就是解决度是5的、含有双环交叉链的不可避免构形，在发生了颜色冲突问题时的可约性问题。

所谓双环交叉链，即是在BAB型的5—轮构形中的A—C链和A—D链分别既是连通的，两链在中途又是相交叉的，且又都与待着色顶点构成了一个环，所以叫双环交叉链（如图1）。
图1中的A—C链和A—D链有共同的起始顶点2A和交叉顶点8A，两链的末端顶点分别是5C和4D。这四个顶点就是这类有双环交叉链的构形中的关键顶点。四个顶点中只要有一个顶点的颜色发生了改变，就不存在双环交叉链了，也就成了坎泊已证明过的是可约的构形了。因此这类有双环交叉链的构形又可分为两类，一类是可以断开的双环交叉链的构形，另一类是不可以断开的双环交叉链的构形。
3、用断链交换法解决可以断开的双环交叉链的颜色冲突构形：
在什么条件下才能使双环交叉链断开呢？现分析如下：
如果构形中含有经过了关键顶点2A或8A的环形的A—B链，该链就一定把经过关键顶点4D和5C的C—D链与其他经过双环交叉链的C—D链分隔在了A—B链环的内、外两侧，交换经过4D和5C的C—D链，A—C链和A—D链两条链均没有了各自的末端顶点，当然双环交叉的A—C链和A—D链也就断开了；
如果构形中含有经过了关键顶点4D和5C的C—D环形链，该链也就把经过了关键顶点2A和8A的A—B链与其他经过双环交叉链的A—B链分隔在了C—D环的内、外两侧，交换经过了2A或8A的A—B链，A—C链和A—D链两条链就没有了共同的起始顶点或相交叉顶点，A—C链和A—D链当然也就断开了。
构形中没有了双环交叉链，也就转化成了无双环交叉链的可约的构形了。这种交换的方法叫断链交换法。所依据的理论是一对相反色链是不可相互穿过的原理。
当然，不含有经过了关键顶点的环形链，但有局部的环形链把经过了双环交叉链的相反链分隔在环的两侧时，交换环形链两侧的任一条相反链，也会使构形转化为无双环交叉链的可约构形了。
4、用转型交换法解决不可以断开的双环交叉链的颜色冲突构形：
如果构形中不含有以上的两种经过了关键顶点的环形链时，当然就不可用断链法解决问题了。也只能用转型交换法使构形转型了，看转型后的构形是个什么样的构形。
图2是一个标准的不含有任何经过了关键顶点的环形链的有双环交叉链的5—轮构形，且不能连续的移去两个同色B。在对其进行顺时针、逆时针的各一次转型交换后，都可直接得到可约的构形。
顺时针转型得到的是，有经过了双环交叉链D—A和D—B两链末端顶点2A和1B这两个关键顶点的环形链A—B的、CDC型的双环交叉链的构形（如图3），这就转化成了一个可约的构形；



逆时针转型得到的虽然仍是有双环交叉链C—A和C—B的构形，但又是可以连续的移去两个同色D的DCD型的可约构形（如图4）。对图4再进行逆时针同方向的转型一次就可移去一个D（如图5），成为一个只有一条连通链C—B的可约构形，然后再从围栏顶点的另一个D色顶点1D开始，进行D—B链的交换，就可移去另一个D，给待着色顶点V着上（如图6）。
转型交换依据的是：既然构形不能连续的移去两个同色B，那就只好先移去一个B，这就使得5—轮构形峰点的位置和颜色都会发生变化，由原来的BAB型构形转化成了别的类型的构形了。
这种构形还有另外的解决方法，图2中各链中至少有一个顶点（如图7和图8中的加大顶点）的颜色改变后，就可以转化成可以用断链交换法解决的有经过了关键顶点的环形链的构形（如图7和图8）。

5、不含经过关键顶点的环形链的构形的最大转型次数：
可以肯定的说，这类构形的转型次数一定是有限的，因为它根本就没有象E—图（埃雷拉图）那样的形成无穷循环转型的条件——有经过了关键顶点的A—B链。图2是一个非极大的平面图构形，虽然一次转型后就可以转化成可约的构形，但为了寻求该类构形最大的转型次数，即就是在一次转型后，虽然得到了有经过了关键顶点的环形链的构形和可以连续的移去两个色的可约构形，但却也可以不去用断链法直接解决，也不去用连续的移去两个同色进行解决；而是用在平面图范围内，继续的连续构造具有双环交叉链的构形，看在平面图范围内再不能构造出双环交叉链时的构形是个什么样的构形，最大能转型多少次。的确，无论是逆时针转型，还是顺时针转型，均是在进行了6次转型后，就不可能再在平面图范围内构造出有双环交叉链的构形了。这也就相当于在第5次转型后，图就是一个可以连续的移去两个同色的可约构形了（图就不再画了，有兴趣者自已可以画一画）。在这里，说的只是转型次数的上界限最大是5或6，并不是说任何该类型的构形在转型时，一定都得要达到5次或6次转型。
另外，仿照敢峰先生的转型演绎法，从最基本的双环交叉链构形（如图2）开始，也可构造出这类无经过关键顶点的环形链的构形，解决的办法同样也是用转型交换法，最多只是转型4次就是一个可以连续的移去两个同色的可约构形（也即第5次转型后就是一个只有一条连通链的可约构形）。中途每一次转形的结果都是一个含有经过了关键顶点的环形链的构形，也可以提前结束转型。
张彧典先生用改变E—图中的某个四边形的对角线的方法构造的15个Z—构形中，除Z6到Z10五个构形本身就是含有经过了关键顶点的环形链的构形外，其他的10个不含经过关键顶点的环形链的Z—构形，无论是从那个方向转型，都是不超过5次转型，就可以转化成只有一条连通链的构形，或含有经过了关键顶点的环形链的构形，也都是可约的构形。
由于非E—图的构形，都可以用转型交换法在有限次的转型内解决问题，所以对于所有非E—图的构形来说，最大的转型次数将是决定于E—图无穷循环转型的循环周期。
E—图转型时，是以4次转型为一个小的循环周期。主要是构形的类型以BAB—DCD—ABA—CDC—BAB（逆时针转型）为周期和以BAB—CDC—ABA—DCD—BAB（顺时针转型）为周期，进行无穷的类型循环。看一个构形是否是产生了无穷的类型循环，主要是看其转型次数是否能走完了小循环的第二个周期——8次转型。正好我们这里的不含有经过关键顶点的环形链的构形的转型次数都是没有超过8次的；
同时E—图在转型时，又是以20次转型为一个大的循环周期。主要是以构形峰点的位置和颜色（或者说图中各顶点的颜色）再次返回到转型的初始状态时为周期，进行的无穷循环。看一个构形是否是产生了返回到转型的初始状态的无穷循环，主要是看其转型次数是否能走完了大循环的第二个周期——40次转型。正好我们已经知道的几个是非E—图的、含有经过了关键顶点的环形链的构形，转型的次数都是不超过40次的，如张彧先生用改变E—图中某个四边形对角线的方法，构造的转型次数达到8—15次的Z—构形，和对E—图的扩大所构造的转型次数达到20—25次的构形，其转型次数都没有超过40次。
总之，完全是可以用转型交换的方法解决有颜色冲突问题的5—轮构形的，其转型交换的次数都是有限的，绝对是不会超过40次的。在有限的40次转型之内，不管是含有经过了关键顶点的环形链的构形，还是不含有经过关键顶点的环形链的构形，都可以转化成有经过了关键顶点的环形链的构形，或者转化成可以连续的移去两个同色的构形。这两种构形都是可约的，所以有颜色冲突的含有双环交叉链的5—轮构形，不管有没有经过了关键顶点的环形链，都是可约的。
6、四色猜测是正确的，可以上升为定理：
现在，5—轮构形的可约性已经得到了解决，应该说四色猜测也就是正确的了。但我们在证明时，用的是非具体极大平面图的“构形”，而不是具体的极大平面图。所以还得在极大平面图范围内，找到与各“构形”所对应的具体极大平面图的“模型”，再返回到极大平面图和地图。
用敢峰先生的转型演绎法可以分别构造出含有双环交叉链的并含有经过了关键顶点的环形链的具体极大平面图构形（敢峰先生构造）和含有双环交叉链的但不含经过关键顶点的环形链的具体极大平面图构形（雷明构造）。因为这种构形都是具体的极大平面图，所以称其为“基本模型”，以与“构形”相区别。当然坎泊已经解决了的不含双环交叉链的构形，在平面图以内也是可以找到与其相对应的是具体的极大平面图基本模型的。
对基本模型可以采取以下各种措施，以得到任意顶点数的各种具体极大平面图的模型。①可以通过在基本链上连续增加偶数个顶点并着色的办法使基本链加长，再添加边使图变成极大图；②可以通过在极大平面图面中增加顶点和边并对顶点着色的办法，使图的顶点数增加；③也可以通过在基本链以外的边上增加顶点和边，并对顶点着色的方法，使图的顶点数增加。经过增加顶点和边得到的这些任意顶点数的模型中的基本链仍是原来构形中的基本链未变。用与解决构形可约性时同样的方法，也就可以解决这些任意顶点数的模型中待着色顶点的着色问题。
任意顶点数的具体极大平面图的4—着色问题解决了，当然它们的对偶图——任意面数（区域数）的地图（地图与极大平面图是互为对偶图的图）——的四色问题也就解决了。地图四色猜测就是正确的。极大平面图的四色猜测也是正确的。极大平面图的四色问题解决了，由极大平面图通过减边或去顶所得到的任意平面图的四色问题也就解决了。所以任意平面图的四色猜测也是正确的。四色猜测绝对正确。四色足矣！


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

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，