四色问题的彻底解决

雷明85639720

四色问题的彻底解决
雷  明
（二○二二年八月七日）

1、并不是多余的话：
四色问题，也叫四色猜测。是一个关于给行政区划地图中的区域染色的问题。说的是给任何地图中的区域各染以不同的颜色，要求有共同边界的两个区域的颜色都不能相同，最多四种颜色就够用了。这就是1852年英国的绘图员法朗西斯在给英国地图染色时提出来的一个猜测。至今已有170年的历史了，但仍无得到证明是否正确。
地图中的区划的边界线一般都很细，加上地图中还有河流，山脉，公路，铁路，城市等自然地形地貌以及人为建筑物等，信息量是非常之大的，再把文字标注进去后，这样就很难看清各区划的边界线，也看不明白各区划间的相邻关系到底是什么样子。所以就要给地图中各区划染以不同颜色（较浅的），以便进行区别。但又不会影响到自然地形地貌和人为建筑物的显示以及所标注文字的清晰。
猜测本身中所说的地图是指理论上的地图，即不存在有“国中之国”和“飞地”这样的行政区划的地图，也不存在有多于三条边界线相交于一点的区划的地图等。这就是平时大家所说的“正规地图”。而在实际上的行政区划地图中，不但存在着以上的各种情况，而且还有陆地与海洋之分。实际地图中的确又存在着有四个国家（行政区划）两两均相邻的情况，至少要用四种颜色才能区分开来。这就是说地球地图光陆地区划至少就要占用四种颜色。但又不能把海洋与某些陆地区划都染成相同的颜色吧。如果是这样，怎么能区分出哪一个区域是海洋，哪些区域又是陆地上的行政区划呢？所以实际地图的用色数是一定要大于等于理论上的正规地图的用色数的。但也不能用得太多，太多了，各颜色之间的差别就小了，也起不到清晰区分的作用。月球上没有海洋，全是陆地，如果能证明四色猜测是正确的，那么无论在月球上怎么划分区域，“月图”最多四种颜色就一定够用了。
2、把地理学问题转化成数学问题：
从图论的角度去看，正规地图就是一个各顶点都是3—度（连接着3条边界线）的3—正则的平面图。它的对偶图就是一个各面都是三边形面的极大平面图。给正规地图中面上的染色，就相当于对极大平面图的顶点着色。如果证明了四色猜测是正确的，那么已经4—着色的极大平面图，经“去顶”或“减边”后所得到的任意平面图（极大平面图也是平面图中的一种），其色数是只会减少而不会再增加的。这也就说明了任意平面图的四色猜测是正确的。这样也就把一个地理学中的问题转化成了一个数学问题了。
3、把无穷的问题转化成有穷的问题：
给平面图着色时，总得要遇到最后一个要着色的顶点。把这样的还剩下一个顶点未进行4—着色的图就叫做“构形”。未着色的顶点叫待着色顶点，把与待着色顶点相邻的顶点叫围栏顶点。由于在图论中有这样的已经证明过了的结论：任何平面图中都一定存在着至少一个顶点的度是小于等于5的。也就是说，在任何平面图中，可以没有大于等于6度的顶点，但不可能没有度是小于等于5的顶点。或者说所有顶点全都是大于等于6度顶点的平面图是不存在的。
由于在平面图中存有这样的性质，所以在给任何平面图着色时，总可以把待着色顶点放在度是小于等于5的顶点之上。其余的无穷无尽的度是大于等于6的顶点，就可以不再充当待着色顶点了，也就可以不再去研究度是大于等于6 的构形的可约性了。而只研究度是小于等于5的六种构形（度分别是0、1、2、3、4和5的构形）中的待着色顶点如何着色就可以了。这就又把一个从平面图的个数上看是无穷的问题，从各个图的顶点数上看，也可以是无穷的问题，从图中的各顶点的度数上看，仍可以是无穷的问题，统统就都转化成了一个有穷的问题了。
若把度是大于等于6的构形看做是可以避免的构形，而把度是小于等于5的构形就叫做不可避的构形。不可避免的构形是在对任何平面图着色的过程中总可以遇到的。这样就把“构形”分成了两类。这里可以认为就是对构形的一级分类。
在极大平面图中，每一个顶点与其相邻的顶点所构成的分子图都是一个轮形图，而在非极大的任意平面图中，各个顶点与其相邻的顶点所构成的分子图，有可能是轮形图，也有可能是星形图，还有可能是半轮—半星图。但最基本的还是星形图。所以我们统一把平面图的不可避免构形叫做n—星构形。在这个n—星图的围栏顶点以外，再把围栏顶点间的“链”的连通情况画出来，就是一般非具体图的、且是非极大图的n—星构形的表示方法。把由某两种颜色所构成的交替着色的道路就叫“色链”，简称“链”。
4、平面图不可避免构形的多级分类：
构形分类的原则：多级分类。每级只分两类，非此即彼，以防遗漏。一类在该级分类中就可以得到解决，另一类留下等下一级分类时再进行细分。
一级分类：上一个问题就可以认为是构形的一级分类，即把构形分成了可以避免的构形和不可避免的构形两类。
二级分类：按围栏顶点所占用的颜色数是否小于等于3，把不可避免的构形再分成可以直接着色的构形（小于等于3的）和不可以直接着色的构形（等于4的）两类。可以直接着色的构形，问题也就已经得到解决，接下来再对不可直接着色的构形进行细分。
三级分类：按是否可以通过坎泊在1879年所创造的可以空出颜色的颜色交换技术，能否可以直接从围栏顶点中空出某种颜色来，再把不可直接着色的构形再分成坎泊的可约的K—构形和赫渥特的“看似不可约”的H—构形两类。可约的K—构形早在1879年由坎泊已经证明是可约（即可4—着色）的了，问题也就得到解决了。现在主要就是要解决“看似不可约”的H—构形的可约性问题了。
所谓坎泊的颜色交换技术，就是在不可直接着色的构形的围栏顶点中，在某两个对角顶点间的色链是不连通时，可以从一个顶点开始交换该链中各个顶点的颜色，即可从围栏顶点中空出交换时开始顶点所用的颜色来。这时围栏顶点就减少了一种颜色，把从围栏顶点中减下来的这种颜色可给待着色顶点着上即可。
由于在只有4个围栏顶点的不可直接着色的4—星构形中，一定有一对对角顶点的颜色所构成的色链是不连通的（因为在这种构形中，由四种颜色所构成的两种色链是相反色链，即两链中没有相同颜色的顶点，是相互不能穿过的两条色链），所以，不可直接着色的4—星构形一定是可约的。
5、对不可避免的H—构形的分析：
在BAB型的5—星构形中，含有不含有A—C链和A—D链的双环交叉链，是构成H—构形的必要条件。没有双环交叉链不能构成H—构形，但有了它却不一定都是H—构形。比如在四个“九点形”构形中，都有双环交叉的A—C链和A—D链（如图1—4中的加粗边），但只有一个是H—构形（如图2），而其他三个都是可以连续的移去两个同色B的可约的K—构形（如图1，图3和图4）。


B—C链和B—D链也是两条双环交叉链（如图5），在含有这两条链的构形中，虽然不能连续的移去两个同色B，但是可以移去A、C、D三色之一，所以它也就不是H—构形了。看来H—构形中是一定要含有A—C和A—D双环交叉链的（如图2和图6）。也正是因为有了双环交叉的A—C链和A—D链，也才有从一个B开始交换了一条关于B的链后，虽然移去了一个同色B，但又新生成了从另一个B到其对角顶点的关于另一个B的连通链，因而不能连续的移去两个同色B。加上A、C、D三色又不能移去，所以H—构形就也成了“看似”不能移去任何一种颜色的不可约的构形了。

看来要解决H—构形的可约性问题，断开双环交叉链是一个关键的问题。如何解决这一问题呢？分析如下：
在H—构形中都有大于等于四个的关键的顶点：即双环交叉链的一个共同起始顶点A和大于等于一个的交叉顶点A（因为有些构形中的双环交叉链是有多个交叉顶点的），还有双环交叉链的两个末端顶点C和D（如图6中的四个加大顶点）。这几个顶点只要有一个顶点的颜色改变了，双环交叉的A—C和A—D链就不存在了。而要改变这几个顶点的颜色，就必须交换A—B链或C—D链。有没有这样的可以交换的链呢？完全可以肯定的回答：有。但该链能不能交换，或者交换后能不能起到断开双环交叉链的作用，就得要看构形中，有没有与要交换的链呈相反链的并经过了围栏顶点的环形链。即要交换A—B链，必须要有环形的C—D链；要交换C—D 链，必须要有环形的A—B链。
在H—构形中，由A、B、C、D四种颜色所能构成的A—B链、A—C链、A—D链、B—C链、B—D链和C—D链六种色链中，A—C链和A—D链已不能交换，虽然B—C链和B—D链都可交换，但却只能交换一个，也不能连续的移去两个同色B，所以该两链也等于不能交换。现在就只剩下可交换的A—B链和C—D链了。正好，要断开双环交叉链所需要交换的就是这样的两条链。
为了防止在进行断链交换时，构形中所有的A、B（或C、D）顶点都改变颜色，起不到断链的作用，必须还要有一条经过了围栏顶点的环形的相反链C—D（或A—B）链把A—B（或C—D）链分隔成环形链内、外互不连通的两部分。即若在有环形的C—D链时，双环交叉链的共同起始顶点A和至少一个交叉顶点A一定分别处于C—D环形链的两侧；若在有环形的A—B链时，也有双环交叉链的两个末端顶点C和D构成的C—D链和其他的C—D链也一定分别处于A—B环形链的两侧。按这一条件，把H—构形再可分成有经过了围栏顶点的环形链的构形和无经过围栏顶点的环形链的构形两类。有些构形中虽有环形链，但不经过围栏顶点，也不能把另一种属于相反链中的关健顶点分隔在环形链的内、外两侧，这样的构形仍是属于无环形链的H—构形。这也可以看成是对不可避免构形的第四次分类（即H—构形的分类）。
6、有环形链的H—构形的可约方法：
图7到图10是四个有双环交叉链A—C和A—D且含有环形链A—B的构形，但只有图7是一个H—构形，其他的三个都是可以连续的移去两个同色B的可约的K—构形；图11到图14也是四个有双环交叉链A—C和A—D且含有环形链C—D的构形，也是只有图11是一个H—构形，其他的三个也都是可以连续的移去两个同色B的可约的K—构形。这与前面说的虽然都含有双环交叉链，但却不一定都是H—构形的结论是相同的。



可以看出，图7从双环交叉链的两个末端顶点C和D开始在A—B环形链内交换C—D链（在环形链A—B外交换另一支C—D 链也是可以的），可使双环交叉链断开，构形转化成虽然仍有双环连通链，但却不交叉的可约的K—构形；图11从双环交叉链的共同起始顶点（峰点）A开始在C—D环形链内交换A—B链（在环形的C—D链外从双环交叉链的交叉顶点A开始交换另一支A—B链也是可以的），也可使双环交叉链断开，构形转化成无任何连通链的可约的K—构形。
然后各再按解决K—构形可约性的方法去解决K—构形的可约就可以了。

这里所使用的方法仍是坎泊1879年创造的颜色交换技术，但它没有从围栏顶点中空出颜色，而是把双环交叉链断开了，使构形转化成了可约的K—构形。为了相互区别，就把这里所用的交换方法叫做“断链交换法”，而把坎泊使用过的交换方法叫做“可空出颜色的交换法”。1890年赫渥特的H—图是一个有环形链C—D的H—构形，1921年埃雷拉的E—图则是一个有环形链A—B的H—构型，都是可以用断链法进行解决的。
7、无环形链的H—构形的可约方法：
图15到图18是也四个有双环交叉链的但又不含有环形链的构形，也只有图15和图16两个是无环形链的H—构形，其他两个也都是可以连续的移去两个同色B的可约的K—构形。与上面的结论是一致的。再一次说明了不能把只要是含有双环交叉链的构形都说成就是H—构形。




从图15和图16可以看出，把图15中的C—D链中的一个顶点C的颜色改成A（如图19中的加大顶点）时，把图16中的C—D链中的一个顶点D的颜色改成A（如图20中的加大顶点）时，两个构形都转化成了有环形链A—B的H—构形；另一方面把图15中的A—B链中的一个顶点A的颜色改成D（如图21中的加大顶点）时，把图16中的A—B链中的一个顶点A的颜色改成C（如图22中的加大顶点）时，两个构形就都转化成了有环形链C—D的H—构形了。
这说明了无环形链的H—构形是可以向有环形链的H—构形转化的。然后再按解决有环形链的H—构形的办法去解决即可。图15和图16这样的转化过程也是可以逆向进行的，这说明不光是无环形链的H—构形可以转化成有环形链的H—构形，而且有环形链的H—构形也是可以转化成无环形链的H—构形的。
现在要问，有没有无环形链的H—构形不可以转化成有环形链的构形呢？回答是：没有。用反证法进行证明：如果说有不能转化成有环形链的H—构形的无环形链的H—构形，就说明H—构形有三类，一类是有环形链的构形，二类是可以与有环形链的构形相互转化的无环形链的构形，三类是不能转化成有环形链的构形的构形。但我们这里所说的H—构形中，前提条件是，只有有环形链的构形和无环形链的两种构形，是非此即彼的两类构形。但这里证明的假设与前提条件是矛盾的，应该否定假设。这就证明了无环形链的H—构形一定是可以转化成有环形链的H—构形的。也就是说根本就不存在不可转化成有环形链的H—构形的无环形链的H—构形。
这样的反证法证明似乎好象理由有点不大充分，似乎还不能说明无环形链的H—构形就一定不存在不可转化成有环形链的H—构形。难以使人所接受。为了弥补这一问题，在下面第8个问题中，还有用连续转型的方法解决无环形链的H—构形的可约性的办法。
以上所看到的是有环形链的H—构形与无环形链的H—构形的相互转化，实际上有环形链的两种H—构形也是可以相互转化的。把图7中的有环形链A—B的H—构形中的两个顶点A的颜色分别改成D和C（如图23中的两个加大顶点），有环形链A—B的H—构形就转化成了有环形链C—D的H—构形了（如图24）；这样的过程也是可以逆向进行的，一个有环形链C—D的H—构形（如图11和图24），也是可以转化成有环形链A—B的H—构形的（如图23和图7）。

8、无环形链的H—构形经有限次同方向连续转型也是可约的：
无环形链的H—构形中由于既没有环形的A—B链，也没有环形的C—D链，所以C—D链和A—B链也就都不能交换了。四种颜色所能构成的六种链中，已有四条不能交换了。剩下的两条关于两个同色B的链，又不能连续的进行交换，也不能移去两个同色B。只交换一条时，虽不能移去两个同色B，但可以使构形转型，这也就出现了转机。然后再看转型后的构形是否可约。现在，唯一的办法也只能是先交换一条关于两个同色B的链，使构形转型了。
所谓转型 ，就是从一个B色顶点开始，交换一条关于两个同色B的链，使构形峰点的颜色和位置都发生变化，生成另一类型的新的5—星构形。如图25是对图15从左B开始进行交换的逆时针方向转型，把BAB形的构形转化成了DCD型的构形；图26是对图15从右B开始进行交换的顺时针方向转型，把BAB型的构形转化成了CDC型的构形。图25再转型一次后，是一个可以连续的移去两个同色的可约的K—构形，图26目前已经是一个含有经过了两个围栏顶点的环形链A—B的H—构形了，可以再按有环形链的H—构形的处理方法进行解决了。

现在的问题是，这个“有限次”的转型交换，是如何得来的，并且要解决有限次的上界值是多少的问题？要知道，没有上界值的有限仍相当于是无限的。那么，不解决这个问题，无环形链的H—构形的可约性问题就还等于没有解决。
上面我们说了，埃雷拉E—图（如图27和图28。图27的待着色顶点是隐形画法，图28的待着色顶点是显形画法）是可以用断链法进行解决的有环形链的H—构形。但是若对E—图构形使用转型法时，却是一个无穷周期循环转型的构形，永不得解。
E—图是一个特殊的H—构形，除了含有双环交叉的A—C链和A—D链、且不能连续的移去两个同色B外，还含有经过了三个围栏顶点的环形的A—B链和含有不经过围栏顶点的环形的C—D链。这两条环形链并没有相交叉的相互穿过，而是象两个同心园一样结构的两条环形链，是没有交叉顶点的。E—图又是一个左右对称的轴对称图。有了这些特殊的特征，当然就有与一般的H—构形不同的性质。

根据E—图是一个无穷周期循环转型也不得解的结论，利用“逆否命题与其原命题同真同假”的逻辑关系，可以判断得出有限次转型可以解决问题的H—构形一定不是E—图构形。也就是说，不光仅仅是无环形链的H—构形的转型次数一定是有限的，而且是任何只要不是E—图构形的H—构形，其转型的次数一定都是有限的，也包括有环形链的H—构形在内。但“有限的”上界值是多少呢？现在来进行分析：
任何5—星构形（包括E—图在内）转型时，即就是转型次数达到了5—星构形的“固有周期”（20次）时，由于第二个周期（40次）还没有来临，所以还是不能判断是否是无穷周期循环的构形。只有等到第二个循环周期第40次转型来到时，才能确定。而我们这里所研究的无环形链的H—构形，已经知道其是有限次转形的，第二个循环周期一定是不可能来到的，连续转型必须在第二个循环周期40次转型到来之前结束。这样，有限次的上界值就可以确定为40次。即任何无环形链的H—构形在连续转型时的转型次数一定在不会超过40次时，就可以解决问题。在转型的过程中，随时也都有转化成有环形链的H—构形的可能。也都可以随时转变成用断链法进行解决，以提前结束转型。
的确，笔者与另一位未曾谋面的山西省的业余四色爱好者同行朋友张彧典先生都曾构造出过转形次数高达20次以上的H—构形，但转型次数的确又没有超过40次这就证明了无环形链的H—构形一定是会在有限的40次转型之内解决问题的，没有到达第二个转型周期的来临。
无环形链的H—构形的解决方法除了以上的直接转化成有环形链的H—构形和转型法外，还可利用有局部环形链的局部断链法（即只断掉一条连通链的方法）解决问题的。总之，无环形链的解决办法不但多种多样，而且还是可以相互转化的，非常的灵活，用起来也很方便。
这就证明了无环形链的H—构形一定是会在有限的40次转型之内解决问题的。即无环形链的H—构形也是可约的。
9、四色猜测被彻底证明是确的：
现在，平面图不可避免的构形在各种情况下都是可约的了，四色猜测也就证明是正确的了。

雷  明
二○二二年八月七日于长安

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，