平面图着色中一定会遇到颜色冲突问题的逻辑证明

雷明85639720

平面图着色中一定会遇到颜色冲突问题的逻辑证明
雷  明
（二○二○年十月十五日）

1、平面图着色中一定会遇到颜色冲突问题的逻辑证明
四色问题因给地图的染色而引起，地图又是一个3—正则的平面图，给地图中的面上的染色就相当于对地图的对偶图——极大平面图——的顶点着色，所以我们在这里所说的平面图着色就是指的对极大平面图的着色。
极大平面图的每一个面都是三边形面，每一个顶点都是处在一个轮的中心顶点的位置。我们在对其着色时，又是一个顶点，一个顶点的着，总有一个顶点是最后着色的，叫待着色顶点。这时，与该顶点相邻的顶点都已经是着上了颜色的，叫围栏顶点。把这种只有一个顶点未着色的图就叫做构形。那么就有两种可能存在的情况：一是围栏顶点占用的颜色数小于4，待着色顶点着上图中已用过的四种颜色之一是没有问题的；二是围栏顶点占用的颜色数等于4，这时该给待着色顶点着上哪种颜色呢？。
把围栏顶点所占用颜色数等于4的这种情况就叫做“颜色冲突”。因为它看上去似乎是只有给待着色顶点着上第五种颜色了，但实际上，在运用了坎泊的颜色交换技术后，还是可以把围栏顶点所占用的颜色数由4减少到3的，而空出一种颜色给待着色顶点着上。这种情况不光是在着色到最后一个顶点时存在，对一个图来说，在着色的中途的某一个顶点时，也是可能存在的。
既然是可能产生颜色冲突和可能不产生颜色冲突的两种情况都存在，那么我们就必须从最坏处着想，从可能产生颜色冲的情况出发，提前构造好可能会出现的各种颜色冲突的模型，并对其进行解决。以防在着色过程中遇到了颜色冲突时，措手不及，没有应对的策略和措施。同时，只要解决好了有限的颜色冲突模型的着色问题，也就等于解决了四色猜测的证明问题。
2、各种颜色冲突问题的模型
由于平面图中一定存在着度是小于等于5的顶点，所以我们总可以把待着色顶点放在度是小于等于5的顶点之上。这样就可以把一个研究对象是无穷多（待着色顶点的度可以是无穷多）的问题转化成一个研究对象只是有限多（度是小于等于5的五种待着色顶点）的问题了。由于度小于等于3的待着色顶点是不可能产生颜色冲突问题的，所以就只有度是等于4和5的待着色顶点才能产生颜色冲突问题。度是4的待着色顶点颜色冲突的问题，坎泊早就已经解决了，现在就只剩下度是5的待着色顶点（即5—轮构形）的颜色冲突问题一种情况还没有解决。
度是等于5的待着色顶点颜色冲突的问题中有一种情况，即模型中不存在双环交叉链的情况，坎泊也早已进行了解决；另一种情况是模型中存在双环交叉链的情况（如图1），至今还没有得到解决。尽管现在已有人能够对其进行解决，但至今还未得到数学界的认可。
所谓双环交叉链，就是在一个度为5的颜色冲突模型中，围栏顶点分别着色是1B—2A—3B—4D—5C时，A—C链和A—D链不但有共同的起始顶点2A，而且对于围栏顶点也是连通的，两链分别都与待着色顶点V构成了一个环，并且两链在中途还有相交叉的顶点（如图1中的8A）。所谓链，就是由一条用两种颜色交替着色的顶点所构成的序列，如A—B链就是用A和B两种颜色相间着色的一条道路。
在有双环交叉链的5度颜色冲突模型中，又可分为可以连续的移去两个同色B的模型（如图2，图3和图4）和不可以连续的移去两个同色B的模型（如图5，图6，图7和图8）。前者是可空出两个同色B给待着色顶点着上的，是可约的构形。

不可以连续的移去两个同色B的模型还可分为有经过了围栏顶点的环形链的模型（如图5和图6）和无经过围栏顶点的环形链的模型（如图7和图8）。
可以看出，以上图中的围栏顶点2A，4D，5C和两链的交叉顶点8A以及顶点6C和7D都是非常关键的顶点（如图1中的加大顶点），其中只要有一个顶点的颜色发生了改变，图中就不再存在双环交叉链了，就成了坎泊早已解决过了的可约构形。利用这一点，我们就可以解决有经过了围栏顶点的环形链的颜色冲突问题模型的着色问题。

有经过了围栏顶点的环形链的模型又可以分为有经过了两个围栏顶点的C—D环形链的模型（如图5）和有经过了三个围栏顶点的A—B环形链的模型（如图6）。前者的解决办法是从8A（或2A）开始交换A—B链，模型就变成了无双环交叉链的可约构形了（如图9）。赫渥特图模型就是这样解决的；后者的解决办法是从4D（或5C）开始，或者从6C（或7D）开始交换C—D链，模型也就变成了无双环交叉链的可约构形了（如图10）。埃雷拉图模型也就是这样解决的。把这种交换的方法就叫“断链交换法”或“邻角链交换法”（相对的，把坎泊所用的交换方法也就叫“对角链交换法”）。
对于无经过围栏顶点的环形链的模型来说，A—B链和C—D链都不是环形的，且都只有一条，所以是不可能使用断链交换法的。虽然如此，但解决这种模型的方法还是较多的：
一是改变图中某个顶点的颜色，就可以使图转化成有经过了围栏顶点的环形链的模型，再用解决有经过了围栏顶点的环形链的方法进行处理即可解决问题。图11，图12，图13和图14就是把图7和图8分别改变了个别顶点（如图中的加大顶点）的颜色后得到的有经过了围栏顶点的环形链的构形。

二是当某一条连通且相交叉的A—C链或A—D链中有某一个顶点被一个用A、B或C、D两种颜色着色的偶圈（如4—圈）所包围，形成了“孤点链”时，这时可认为是在一个局部范围内的环形链，改变这个“孤点链”的颜色，就可以使一条连通且相交叉的链断开，模型转化成无双环交叉链的可约构形。张彧典先生的第八构形的放大图就可以用这样的办法来解决。
三是先从一个两个同色B的顶点交换一个关于两个同色B的链，使模型转型，转化成有经过了围栏顶点的环形链的模型或者是可以连续的移去两个同色的可约构形。图15和图16分别是对图7和图8从顶点1B逆时针方向交换了B—D链的结果（如图中加粗的虚线边1D—7B），模型均由BAB型转化成了DCD型。图15是一个有经过了两个围栏顶点的A—B环形链的颜色冲突模型，图16是一个可以连续的移去两个同色D的可约构形。

图17和图18分别是图7和图8从顶点3B顺时针方向交换了B—C链的结果（如图中加粗的虚线边3C—6B），模型也均由BAB型转化成了CDC型。图17是一个可以连续的移去两个同色C的可约构形，图18是一个有经过了两个围栏顶点的A—B环形链的颜色冲突模型。
这种交换的方法可以叫做“转型交换法”，因为每交换一次，模型的类型就发生一次改变。这里要注意的是，连续移去两个同色D或C时的交换方向，要与转型时的交换方向是相同的，否则图就会又转化成原来未转型时的构形。
有人可能会说，你的图7和图8并不是极大图，当在极大图时从顶点3B交换了B—C链或从顶点1B交换了B—D链后，可能不一定就会得到能够连续的移去两个同色的构形。是的，这完全是会有可能。但是在遇到这种情况时，我们可以进行连续的转型交换，一定是会在有限的转型次数内，图就会转化成一个可以连续的移去两个同色的构形。证明如下：

一个123—BAB型的5—轮（如图19），是一个可以使用坎泊的颜色交换技术后空出任何一种颜色给待着色顶点V的颜色冲突模型。但5—轮在连续转型时，却以每20次转型为一个周期，又会转化成123—BAB型的5—轮，与原来的图一模一样，是一个无穷周期循环转型的模型，并不能空出任何颜色来给待着色顶点。但5—轮也不是极大图，也还不能说明问题。
那么，还有没有连续转型20次，也不能转化成可以连续的移去两个同色的极大图模型呢？有。这就是埃雷拉图（即E—图，如图20）。该图有双环相交叉且连通的A—C链和A—D链，有经过了3个围栏顶点的环形的A—B链（如图中的双线边所示），是一个标准的有经过了围栏顶点的环形链的颜色冲突模型。是可以用断链交换法解决问题的。
但若对埃雷拉图也进行连续的转型交换时，无论是逆时针方向还是顺时针方向转型，都是以每20次转型为一个周期的无限循环转型的模型，永远不可能转化成可以同时移去两个同色的可约构形。而我们这里所说的无经过围栏顶点的环形链的模型中，根本就没有经过围栏顶点的环形链A—B，更没有象图20中那样，还有一条不经过围栏顶点的环形的C—D链（图中未进行特别表示）。所以它一定是不会象埃雷拉图那样，是一个无穷周期循环转型的模型，因为它就没有产生无穷周期循环转型的条件。
这样，就证明了无经过围栏顶点的环形链的模型在用连续转型交换法进行转型时，一定是会在有限的20次转型之内转化成可以连续的移去两个同色的可约构形的。并且在转型的过程中，还可能有多次机会直接转化成有经过了围栏顶点的环形链的模型，可以改用断链交换法转化成无双环交叉链的可约的构形，以减少转型的次数。
到此，就不但证明了任何可能出现的颜色冲突问题都是可以解决的，而且也证明了对于任何的平面图来说，四色猜测都是正确的，地图的四色猜测也是正确的。
3、“减少法”着色是否会遇到颜色冲突的问题
焦永溢先生的所谓“减少法”证明四色猜测的方法，实际上就是用轮形图着色法对极大平面图进行的着色，只是一种着色的方法而已，并不是对四色猜测的证明。轮形图着色时，不计中心顶点的偶轮用三种颜色，不计中心顶点的奇轮用四种颜色。但由多个轮共同构成的极大平面图着色时，四种颜色是否够用呢？焦先生用他的减少法对极大平面图着色的结果，认为四种颜色的确就够用了。这样他就认为他证明了四色猜测是正确的。作为一个证明，焦先生没有证明在遇到了颜色冲突时，是否可以解决，如何去进行解决。只凭对几个个别的图的着色就得出四色猜测是正确的结论，是不符合证明的要求的。而焦先生还认为用他的减少法着色时，是不会遇到颜色冲突问题的。
减法法着色中，是否会遇到颜色冲突的问题呢？请看一下焦先生自已对中国地图着色中的文字说明吧。焦先生说：湖南“只所以不用与外面一样的黄色，是因为若用黄色会使重庆外围的颜色多达四种”。这里我要加以说明的是，焦先生所说的“外面”，是指中国边境以外的所有区域，包括陆地和海洋在内。这句话明显的说明了按他的减少法着色，湖南该用黄色了。但若给湖南用了黄色，“重庆外围的颜色就多达四种”！请问，这不就是一个颜色冲突的问题吗？
焦先生只所以认为这里没有出现颜色冲突问题，是因为他提前已经发现了这一问题存在的可能，并且提前已经解决了这一问题，把湖南改着上了红色。但这一改着，又违背了他的减少法的着色规律。
若按减少法着色的规律，把湖南着上黄色后，重庆也是可以着上图中已用过的四种颜色之一的，这就是解决颜色冲突问题的过程。当然处理的方法仍是坎泊的颜色交换技术。处理的结果可能是把湖南改着成红色，也可能是把与重庆相邻的其他省区的颜色进行改变，不一定非要改变湖南的颜色不可。总之问题总是可以解决的，重庆是可以着上图中已用过的四种颜色之一的。
焦先生这样的提前进行处理，无形中把颜色冲突问题就给掩盖了起来。不是没有遇到颜色冲突问题，而是焦先生已经自觉或不自觉的把问题已经处理好了。所以他才认为他的减少法在着色中是不会遇到颜色冲突问题的。
焦先生对中国地图的着色中，最后一个省区是云南省，与云南相邻的西藏，四川，贵州，广西和“外面”只用了三种颜色，当然顺便就可以把云南省着上第四种颜色就可以了，是不会发生颜色冲突问题的。焦先生的着色中，除了遇到重庆的外围省区都已着了颜色外，还遇到过多次外围省区都着了颜色的情况，但都是与云南省有相同的情况，其外围省区用色数都是小于四种的，也不属于颜色冲突的问题。
所以说焦先生的文章作为证明，就必须要把解决颜色冲突的问题补充上来，否则就只能是一种着色的方法。即就是作为着色的方法，也要把为什么不会遇到颜色冲突问题进行证明，然后大家才能放心的去按照他的减少法去着色。但即就是证明了该着色方法不会遇到颜色冲突问题，也还不能算作是对四色猜测的证明，因为任何人都不可能对所有的平面图进行一次全面的4—着色，也就不能说明任何极大平面都是可4—着色的。
4、阿贝尔提出的（5，5）构形和（5，6）构形
焦永溢先生遇到的重庆与湖南的着色问题，不就是阿贝尔提出的（5，6）构形吗（如图21）？这时，因为湖南的外围正好只用了两种颜色B和C，湖南还可以在另外两种颜色A和D间进行选择；如果湖南的外围已用了A，B，C三种颜色时（如图22），则湖南就只能用D色了，不可能再有选择的余地。这时，重庆的外围不就仍是四种颜色吗？不也就是遇到了颜色冲突问题了吗？这时总不能把以前所有的着色都推倒重来吧！也只能寻求解决重庆颜色冲突的办法了，想办法解决这种颜色冲突的问题。如何去解决，这就得看重庆这个颜色冲突的问题，是属于我们在上面的《2、各种颜色冲突问题的模型》中的那一种模型，有针对性的去进行解决。

通过我们的证明，各种颜色冲突问题都是可以解决的。并不是象象焦先生所说的是“死胡同”，死胡同是不能出去的，只能退回，或者推倒重来。但退回到什么地方去呢？如果再遇到了颜色冲突问题，又退到别的“死胡同”去了，又该怎么办呢，还要再退回来吗？不可能的事！所以说，这并不是死胡同，一定是有出路的，只能向前看，不能再向后退。这个出路也一定是能够找到的，这个出路就是我们在上面的《2、各种颜色冲突问题的模型》中的各种应对方法。
若把图22中以湖南为中心的6—轮的轮沿顶点减少一个，并取掉各个顶点的实际内容（省区名称），则图22不是也就变成了一个（5，5）构形了吗（如图23）？
我估计阿贝尔就是认为他不能解决5—轮构形的可约性问题，才构造出了这两个构形的。这个（5，5）构形的两个待着色顶点中的任何一个只要着上了可以使用的唯一一种颜色，则另外一个待着色顶点就变成了一个颜色冲突的5—轮构形的中心顶点。由于阿贝尔不能解决5—轮构形的问题，所以他虽构造了（5，5）构形和（5，6）构形，并且认为这两个构形是“不可避免”的，他也不得不在他的《四色地图问题的解决》一文中最终又说这两个构形是“不可约”的。

既然（5，5）构形和（5，6）构形是不可避免的，又是不可约的，这不就正好说明了四色猜测是不正确的吗？但阿贝尔并不这么说，为了表明他们对证明四色猜测是做了工作的，而在他的《四色地图问题的解决》一文中只能是含糊的说他们只是“证明了”四色猜测，而不明确的给出四色猜测道底是正确还是错误的肯定结论。他们虽然进行了那么多的工作，但最终还是没有解决问题的。
现在人们还盲目的认为是阿贝尔用电子计算机证明了四色猜测是正确的，这种看法十在是错误的。我只能说阿贝尔以不惜浪费大量的电子计算机资源为代价，换来的只是在当时（1976年）对宣传电子计算机起到了一定的作用的效果。这可能就是阿贝尔工作的实际意义。的确从那时起，电子计算机发展的速度之快，也的确是非常惊人的。


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

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