平面图不可避免构形的科学分类与四色猜测被彻底证明是正确的！（一）

雷明85639720

平面图不可避免构形的科学分类与四色猜测被彻底证明是正确的！（一）
雷  明
（二○二二年九月二十日）

【摘  要】通过对平面图的不可避免构形进行科学的多级分类，即，在每一级分类中，按一定的条件把构形都只分为“非此即彼”的两类，以防遗漏。其中一类在本级分类中就可以得到解决（可约），另一类可以留给下一级分类再进行细分。待到某级分类时，所分出的两类构形在本级分类中都可以得到解决时，多级分类即告结束。这样，平面图的各种不可避免的构形在各种情况下就都是可约的了，四色问题也就得到了解决。四色猜测也就得到了证明是正确的。

【关键词】四色问题  四色猜测  平面图的构形  不可避免构形  构形的多级分类  构形的可约性  色链（链）  相反色链  颜色交换技术  染色困局  颜色冲突  关键顶点  环形链  断链交换  转型交换

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

构形的二级分类：按围栏顶点所占用的颜色数是否小于等于3，把不可避免的构形再分成可以直接着色的构形（这类构形中包括度是大于等于4，且围栏顶点所占用的颜色数小于等于3的构形以及度本来就是小于等于3的不可避免的构形）和不可以直接着色的构形（这类构形中围栏顶点所占用的颜色数等于4）。不可以直接着色的不可避免的构形实际上也就只含有度等于4和5的且围栏顶点占用颜色数都是4的两种不可避免的构形（如图1和图2）。
图1的4—度构形的4个围栏顶点各占用了一种颜色，图2的5—度构形的5个围栏顶点中，有两个对角顶点是用了同一种颜色B的。
在这一级分类中，可以直接着色的构形，问题也就已经得到了解决。接下来到下一级分类时，再对不可直接着色的不可避免构形进行细分。不可直接着色的不可避免构形有人也叫“染色困局”构形或“颜色冲突”构形。这类构形看似好象待着色顶点V不用第5种颜色是不行了，但实际上是可以通过使用坎泊在1879年所创造的颜色交换技术，可以给V着上图中已用过的4种颜色之一的。
5、平面图不可避免构形的三级分类：
这级分类得到了4—度构形都是可约构形的结论。


这级分类是把不可直接着色的不可避免构形再分成最多只能有一条连通链的构形（度是4的构形）和最多可以有两条连通链的构形（度是5的构形）两类。4—度构形在这一级分类里都可以用坎泊的颜色交换技术得到解决，5—度构形再去第四级分类进行细分。
所谓坎泊的颜色交换技术，就是把某条链中的两种颜色互相交换位置，就可以达到改变该链中任何一个顶点的颜色的目的。所谓连通链是指由两个对角围栏顶点的颜色所构成的色链，在该两对角顶点间是连通的，并与待着色顶点构成了一个圈（如图4—0和图5—0）。但连通的对角链是不能交换的，因为交换了这样的链，是不可能从围栏顶点中空出颜色来给待着色顶点的。而只有对不连通的对角链，在交换了一支不连通的部分后，才可以从围栏顶点中空出交换起始顶点的一种颜色来。4—度构形只所以最多只能有一条链通链，是因为这种构形的4个围栏顶点只可能构成两种对角链，且这两种对角链又是相反链（即两链中没有相同的颜色），两条链是不能相互穿过的。


4—度不可避免的构形还可分为无连通链的构形（如图3）和有连通链的构形（如图4—0和图5—0）两种（相当于第四级分类）；其中有连通链的构形还可进一步细分为有A—C连通链（如图4—0）和有B—D连通链（如图5—0）的两种（相当于第五级分类）。这两级分类中的构形全都是可约的。
6、平面图不可避免构形的四级分类：
    这级分类得到了无连通链的5—度构形都是可约的结论。
这一级分类是把不可直接着色的5—度构形再分成两类，一类是无连通链的构形，一类是有连通链的构形。这一级分类中，无连通链的构形也都是可约的（如图6）。
有连通链的构形等到第五级分类时再细分。


7、平面图不可避免构形的五级分类：
这级分类得到了有一条连通链的5—度构形都是可约的结论。
这级分类把有连通链的5—度构形再分为有一条连通链的构形和有两条连通链的构形两类。有一条连通链的构形，本次分类都可以解决（有两条连通链的构形等到第六次分类时再细分）。图7，图8，图9和图10分别是有A—C连通链的，有A—D连通链的，有B—C连通链的和有B—D连通链的构形在这四种情况下的着色结果。




其中，有一条连通链的5—度构形又可分为有关于A的链（如图7和图8）和有关于B的链（如图9和图10）的构形两种（相当于第六级分类）。在有关于有A的链中又有A—C链（如图7—0）和A—D链（如图8—0）之分的两种（也相当于第七级分类）；同样的，在有关于B的链中又有B—C链（如图9—0）和B—D链（如图10—0）之分的两种（也相当于第七级分类）。
有A—C链时，交换A—D链可空出A或D（如图7—1和图7—2）,有A—D链时,交换A—C链可空出A或C（如图8—1和图8—2）。有B—C链时，交换A—D链可空出A或D（如图9—1和图9—2），有B—D链时，交换A—C链可空出A或C（如图10—1和图10—2）。
8、平面图不可避免构形的六级分类：
这级分类得到了有两条连通链且两链只有一个共同顶点的5—度构形都是可约的结论。
这一级分类中把有两条连通链的构形分成了有一个公共顶点的构形和有两个以上公共顶点的构形。只所以会产生两链有共用的顶点，是因为在该构形中存在“相邻链”，即两链中有一种颜色是相同的，所以两链就可以相互穿过了，也就产生了共用顶点（公共顶点）的情况。
其中有一个公共顶点的构形又可分为只有一个交叉顶点的构形（如图11—0）和只有一个共同起始顶点的构形（如图12—0）两种（也相当于第七级分类）。只有一个交叉顶点的构形，可空出A、C、D三色之一（分别如图11—1，图11—2，图11—3和图11—4）；只有一个共同起始顶点的构形，可以空出两个同色B（如图12—1）。
而有两个以上公共顶点的构形等到第七级分类时再细分。两条连通链有两个以上共同顶点的构形，其中只有一个是共同的起始顶点，另外的共同顶点均是交叉顶点。这就是平时大家所说的双环交叉链。



9、平面图不可避免构形的七级分类：
这级分类主要是明确了可约的K—构形与“看似不可约的”H—构形的概念。并且看到了含有双环交叉链的构形不一定都是H—构形。
这一级分类，是把有双环交叉链的构形再分成可以连续的移去两个同色B的构形和不能连续的移去两个同色B的构形。实际上也就是把构形分成了可以移去某一种颜色的可约的K—构形和不可以移去任何一种颜色的“看似不可约的”H—构形。可以连续的移去两个同色B的构形以及上面所提到的所有各种构形，都是可约的K—构形，这都是坎泊在1879年早已证明过了的是可4—着色的构形。而不能连续的移去两个同色B的构形，又由于其中的A—C链和A—D链都是连通的，所以A、C、D三色也都是不可能移去的，这就产生了“看似不可移去任何一种颜色”的赫渥特H—构形。
       

图13中的4个“九点形”构形，同样都是有双环交叉的A—C链和A—D链的构形，但只有图13—2一个构形是不能连续的移去两个同色B的，是H—构形；而其他的三个构形却都是可以连续的移去两个同色B的，是坎泊早已证明过的是可约的K—构形。所以，以后研究四色问题的主要方向就只是研究解决H—构形的可约性的问题了。
在前面二级分类中分出的不可直接着色的构形从广义上讲，也都是看似不可约的构形，因为其围栏顶点已占用完了四种颜色。在以下的研究中将会看到，在这种构形中，的确是有一些构形是可以通过坎泊的颜色交换技术，直接可以从围栏顶点中空出某一种颜色（如两个同色B）来给待着色顶点着上的，是属于可约的K—构形一类的构形。所以说不可直接着色的构形从广义上讲，也都是看似不可约的构形。
10、对不可避免的H—构形的分析和平面图不可避免构形的八级分类：
这里提出了双环交叉链是构成H—构形的必要条件。也提出了有环形链的H—构形与无环形链的H—构形的概念。
在BAB型的5—星构形中，含有不含有A—C链和A—D链的双环交叉链，是构成H—构形的必要条件。没有该双环交叉链不能构成H—构形，但有了它却不一定都是H—构形。比如在图13的四个“九点形”构形中，都有双环交叉的A—C链和A—D链（如图中的加粗边），但只有图13—2一个是H—构形，而其他三个都是可以连续的移去两个同色B的可约的K—构形。
有B—C链和B—D链的构形也可以看作是含有两条双环交叉链的构形（如图11—0），在含有这样的两条链的构形中，虽然不能连续的移去两个同色B，但却又是可以移去A、C、D三色之一的，所以含有这种双环交叉链的构形也就不是H—构形了。
看来H—构形中是一定要含有A—C链和A—D链的双环交叉链（如图13—2）的。也正是因为有了双环交叉的A—C链和A—D链，也才有可能从一个同色顶点B开始交换了一条关于B的链后，虽然移去了一个同色B，但又新生成了从另一个同色顶点B到其对角顶点的关于另一个同色顶点B的连通链的可能性，从而也就产生了不能连续的移去两个同色B的情况。加上A、C、D三色又不可能再移去，所以，从狭义上讲，H—构形才是真正的“看似”“不能移去”“任何一种颜色”的“不可约”的构形了。
看来，要解决H—构形的可约性问题，断开双环交叉链A—C和A—D就是一个关键的问题。如何解决这一问题呢？现在分析如下：
在H—构形中都有大于等于四个的关键顶点：即双环交叉链的一个共同起始顶点A和至少一个交叉顶点A（因为有些构形中的双环交叉链是有多个交叉顶点的），以及双环交叉链的两个末端顶点C和D，至少有这四个顶点是关键顶点（如图13—2中的两个A色顶点和围栏顶点中着C色和D色的两个顶点，共四个）。这四个关键顶点只要有一个顶点的颜色改变了，双环交叉的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—B）的内、外两侧，成为互不连通的两部分。即，若要交换的是A—B链，就必须要有一条环形的C—D链，把双环交叉链的共同起始顶点A和至少一个交叉顶点A分隔在环形链C—D的两侧；若要交换的是C—D链，也就必须要有一条环形的A—B链，把双环交叉链的两个末端顶点C和D所构成的C—D链和其他的C—D链分隔在环形的A—B链的两侧。根据这一条件，把H—构形再可分成有经过了关键顶点的环形链的构形和无经过关键顶点的环形链的构形两类。只要构形中有能满足上述条件要求的环形链，就是有环形链的H—构形，否则就是无环形链的H—构形。
有些构形中虽然看似也含有环形的C—D链，并且也经过了围栏顶点或关键顶点，但却不能把其相反链A—B中的两个关键的顶点A分隔在环形链C—D的内、外两侧（如图14—1）。即就是交换了C—D环形链内、外的任一条A—B链，构形中仍然是含有双环交叉链的（如图14—2和图14—3），仍是不能连续的移去两个同色B的构形。所以，象图14—1这样的构形是不应属于有环形链C—D的H—构形的。
       


但该构形应属于哪一类，还要再看构形中还有没有其他的经过了围栏顶点或关键顶点的环形链才能确定。有环形链者（如图14—4和图14—5），就是有环形链的H—构形，无环形链者（如图14—1和图14—6）则是无环形链的H—构形。
这里，可以看成就是对不可避免构形的第八级分类，即对“狭义的”“看似不可约”的H—构形的分类。下面先研究有环形链的H—构形的可约方法。
11、有环形链的H—构形的可约方法：
这一节中提出了解决有环形链的H—构形时，与坎泊解决K—构形时的不同的交换方法，叫做断链交换法。
       

平面图八级分类中的有环形链的H—构形的可约性方法如下：
图15是四个有双环交叉链A—C和A—D且含有环形链A—B的构形，但只有图15—1是一个H—构形，其他的三个都是可以连续的移去两个同色B的可约的K—构形。这与前面所说的虽然都含有双环交叉链，但却不一定都是H—构形的结论是相同的。
可以看出，图15—1从双环交叉链的两个末端顶点C和D开始在A—B环形链内交换C—D链（在环形链A—B外交换另一支C—D 链也是可以的），就可使双环交叉链断开。在转化成的构形中，虽然仍是含有共同起始顶点的两条连通链的构形，但却不是有双环交叉链的H—构形，而是一个可以连续的移去两个同色B的可约的K—构形。因为该两链并没有“十字”相交叉，如同图12—0中的构形一样，是两条不相交叉的色链（图请读者自已画）；


图16也是四个有双环交叉链A—C和A—D且含有环形链C—D的构形，也是只有图16—1是一个H—构形，其他的三个也都是可以连续的移去两个同色B的可约的K—构形。这也与前面所说的虽然都含有双环交叉链，但却不一定都是H—构形的结论也是相同的。
同样的，图16—1从双环交叉链的共同起始顶点（峰点）A开始在C—D环形链内交换A—B链（在环形的C—D链外从双环交叉链的交叉顶点A开始交换另一支A—B链也是可以的），也可使双环交叉链断开，构形转化成无任何连通链的可约的K—构形（图也请读者自已画）。
现在，两种有环形链的H—构形都转化成了无双环交叉链的可约的K—构形了。然后各再按解决K—构形可约性的方法去解决K—构形的可约性就可以了。
这里所使用的方法虽然仍是坎泊1879年所创造的颜色交换技术，但它却没有从围栏顶点中空出颜色，而只是把双环交叉链断开了，使构形转化成了可约的K—构形。另外，这里所交换的链也不一定都是含有围栏顶点的，即就是含有围栏顶点，但也是含有至少两个相邻围栏顶点的邻角链，而不是只含有一个围栏顶点的对角链。为了相互区别，就把这里所用的交换方法叫做“断链交换法”，而把坎泊使用过的交换方法叫做“可空出颜色的交换法”。
1890年赫渥特构造的H—图，是一个含有双环交叉链的两个末端顶点C和D的环形链C—D的H—构形；而1921年埃雷拉构造的E—图，则是一个含有双环交叉链的共同起始顶点A的环形链A—B的H—构型；我们这里所构造的图14—4等图，也都是有环形链A—B（或C—D）的H—构形。也都是可以用断链法进行解决的。
12、平面图不可避免构形的九级分类：
这一分类中解决了可以直接转化成有环形链的H—构形的无环形链的H—构形的可约性问题。
本级分类是把无环形链的H—构形分成可直接转化成有环形链的H—构形和不可直接转化成有环形链的H—构形两类。可直接转化成有环形链的H—构形的问题也就解决了，而不可直接转化成有环形链的H—构形在下一级分类时再进行细分。



图17是六个有双环交叉链的但又不含有任何环形链的构形，也只有图17—1和图17—2两个图是无环形链的H—构形，其他的四个图也都是可以连续的移去两个同色B的可约的K—构形。这也与前面说的虽然都是含有双环交叉链的构形，但却不一定都是H—构形的结论也是相同的。这再一次说明了不可以把只要都是含有双环交叉链的构形就都说成就是H—构形的结论是正确的。
从图17—1和图17—2可以看出，把图17—1中的C—D链中的一个顶点C的颜色改成A（如图18—1中的加大顶点）时，把图17—2中的C—D链中的一个顶点D的颜色也改成A（如图18—2中的加大顶点）时，两个构形就都转化成了有环形链A—B的H—构形；


另一方面把图17—1中的A—B链中的一个顶点A的颜色改成C（如图18—3中的加大顶点）时，把图17—2中的A—B链中的一个顶点A的颜色改成D（如图18—4中的加大顶点）时，两个构形也就都转化成了有环形链C—D的H—构形了。
这都说明了无环形链的H—构形是可以向有环形链的H—构形转化的。然后再按解决有环形链的H—构形的办法去解决即可。图17—1和图17—2这样的由无环形链的H—构形转化成有环形链的H—构形的过程也是可以逆向进行的。说明不光是无环形链的H—构形可以转化成有环形链的H—构形，而且也说明有环形链的H—构形也是可以转化成无环形链的H—构形的。尽管如此，但这还不能说明所有的无环形链的构形与有环形链的构形都是可以相互转化的。例如，图19的两个无环形链的H—构形就不可能向有环形链的H—构形转化。

13、平面图不可避免构形的十级分类：
这级分类中提出了用局部断链法也可以解决无环形链的H—构形可约性的问题。

这一分类是把不可直接转化成有环形链的H—构形分成可局部断链的构形和不可局部断链的构形。可局部断链的构形，问题也就解决了，不可局部断链的构形就得用连续的转型交换法进行解决了。
如若在图19—1中的构形的双环交叉链中，有局部的环形链A—B经过了双环交叉链的A—C链（如图20—1右下角的A—B环），就可以在局部的环形链A—B内进行与环形链呈相反色链的C—D链的交换，把构形的一条连通链A—C断开，使构形转化成只有一条连通链A—D的可约的K—构形（如图20—2）。

（未完，接下一贴）

注：此文原名为《四色问题的彻底解决——四色猜测是正确的！》，并于二○二二年八月三十一日在《数学中国》网的《哥猜等难题与猜想》栏目中发表过，网址是：
http://www.mathchina.com/bbs/for ... &extra=page%3D1，本次修改后改名为《平面图不可避免构形的科学分类与四色猜测被彻底证明是正确的！》，于二○二二年十一月二十三日同时在《数学中国》网的《哥猜等难题与猜想》栏目中发表，网址是：http://www.mathchina.com/bbs/for ... &extra=page%3D1（一）和http://www.mathchina.com/bbs/for ... &extra=page%3D1（二）

雷明85639720

,,,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，