极大平面图的画图、着色、构造颜色冲突模型与证明四色猜测的关系

雷明85639720

极大平面图的画图、着色、构造颜色冲突模型与证明四色猜测的关系
雷  明
（二○二○年十月二十五日）

1、极大平面图的画法
地图四色问题已经由一个给地图（3—正则的平面图）中面的染色的地理问题转化成了一个给极大平面图顶点着色的数学问题了。所以在研究四色猜测时，首先必须了解地图和极大平面图。
图是由顶点与边构成的。边（用直线或曲线表示）与边相交叉的地方就是顶点，由几条边所围成的封闭区域就是面。
地图是一个3—正则的平面图，即地图中的每一个顶点都是3度的，即每个顶点都连有3条边，也即是地图中的“三界点”。地图的对偶图就是极大平面图。所谓对偶图就是把原图的面作为顶点，原来两面间的边仍是现在对应顶点间的边，所得到的新图就是原图的对偶图。可见对偶图的对偶图就是原图了。所以对偶图与其原图是互相对偶的。
地图的对偶图——极大图——也是平面图，图中的每一个面都是三边形面，该图的边数也在相同顶点数的平面图中是最多的。设平面图的顶点数是v，边数是e，则边数与顶点数的关系是e≤3v－6，等式对应的就是极大平面图的边数，不等式对应的是非极大平面图的边数。所谓非极大平面图就是图中至少有一个面的边数是大于3的。极大平面图中的每一个顶点都是处在一个轮形图的中心位置。
由于极大平面图的边数是相同顶点数的平面图中的最多者，所以只要把极大平面图的四色问题解决了，由去顶和减边所得到的任意平面图的四色问题也就解决了。
一个三角形也就是一个顶点数是3的极大平面图，所以在画极大平面图时，首先可先画一个三角形，再在三角形中增加一个顶点并用边连接新增加的顶点与原三角形中的三个顶点，得到一个顶点数是4的极大平面图。以后可以不断的按照这样的办法，任意在新的极大平面图中的面中增加顶点和边，或在边上增加顶点和边，就可以得到顶点数任意多的极大平面图。
2、给平面图的4—着色
四色猜测说的就是给任意平面图着色时，四种颜色就够用了。
由于极大平面图中的每一个顶点都是处在一个轮形图的中心位置，所以在给一个任意的极大平面图进行4—着色时，不论用什么样的着色方法，在中途或最后都一定会遇到一个这样的未着色的顶点，与该顶点所相邻的其他顶点都着了颜色的情况。把这种还有一个顶点未着色的图就叫构形。未着色的顶点叫待着色顶点，与待着色顶点相邻的所有顶点叫围栏顶点。待着色顶点就处在由其与围栏顶点所构成的轮的中心顶点上。
由于平面图中总存在着度小于等于5的顶点，所以在着色时，我们总可以把构形的待着色顶点放在度是小于等于5的顶点上。这就把一个研究对象——构形——是无穷多的问题，转化成了只有有限的5种构形了。把待着色顶点是小于等于5的构形就叫做不可避免构形。
当不可避免构形的围栏顶点所占用的颜色数小于4时，没有问题，待着色顶点是一定至少还有一种颜色可着的，这时，图的4—着色问题也就解决了；当不可避免构形的围栏顶点所占用的颜色数是4时，待着色顶点将如何进行着色呢？这种情况就叫做颜色冲突（有人也叫染色困局）。但这种颜色冲突情况是可以通过坎泊的颜色交换技术解决的，后面我们还要进一步证明之。
不可避免的构形中，待着色顶点的度是2和3的构形是不会出现颜色冲突现象的，只有待着色顶点的度是4和5的两种构形才可能出现颜色冲突的情况。待着色顶点是4度时的颜色冲突情况，坎泊在1879年早已证明了这种情况下的待着色顶点是一定可以着上图中已用过的四种颜色之一的。现在就只剩下待着色顶点是5度时的颜色冲突问题还没有得到解决。
坎泊解决待着色顶点是4度时的颜色冲突问题的原理是这样的：把由两种颜色交替着色的序列叫做色链（简称链），在A、B、C、D四种颜色中，把由A、B两种颜色构成的链和由C、D两种颜色构成的链叫做相反链。由于相反链是不能相互穿过的，所以当一条链自身或与待着色顶点构成了环（圈）时，一定会把另一条相反相链分隔在环的内、外两侧，互不连通。待着色顶点是4度时的颜色冲突构形中，有了连通的A—B链就不可能再有连通的C—D链，有了连通的C—D链就不可能再有连通的A—B链，二者只可能有一个是连通的，并与待着色顶点构成了一个环。这时从环的内、外交换任一条相反链，就可以从围栏顶点中空出一种颜色给待着色顶点着上。
3、解决5度构形的颜色冲突问题
解决颜色冲突问题的过程也是属于着色的过程，只不过这个过程进行完毕后，即把颜色冲突问题解决之后，一个图的着色就可以说是已经完成了。
5度构形颜色冲突问题，坎泊也在1879年把无双环交叉链的情况解决了，但又把有双环交叉链的情况遗漏了。目前研究四色问题，主要就是要解决有双环交叉链的5度构形的颜色冲突问题。在5度构形的颜色冲突中，围栏顶点外两条连通的A—C链和A—D链不但有共同的起始顶点A，在途中还有相交叉的顶点（着A色），它们各自又都与待着色顶点V构成了环，所以叫双环交叉链。由于A—C链和A—D链都是连通的，所以是空不出A、C、D三色之一的（如图1）。现在只能先看是否可以连续的空出两个同色B。如果可以，当然问题也就解决了。否则，就只能想别的办法，把围栏顶点所占用的颜色数由4减少到3。

这种颜色冲突构形可以分为两大类，一是有经过了围栏顶点的环形链的构形，一类是无经过围栏顶点的环形链的构形。有经过了围栏顶点的环形链的构形，还可再细分为有经过了三个围栏的A—B环形链的构形（如图2），和有经过了两个围栏顶点的C—D环形链的构形（如图3）。
从图中可以看出，围栏顶点1和4—5，A—C链和A—D链的交叉顶点8以及顶点6—7都是关键的顶点，其中一个顶点的颜色如果改变了，则双环交叉链就不存在了。只要有经过了三个围栏顶点的A—B环形链，顶点4—5和顶点6—7一定是被分隔在A—B环链两侧的；但有了经过两个围栏顶点的C—D环形链，却不一定都能把顶点1和顶点8分隔在C—D环的两侧（如图4）。虽然如此，但C—D环仍然把A—B链分隔在了环的两侧，其中某一侧一定含有双环交叉链上的顶点（见图4中的加大的A色顶点）。
由于这些原因，所以解决图2的办法就是在A—B环内或外交换经过围栏顶点4—5或顶点6—7的C—D链，就可以使构形转化成坎泊已经证明过是可约的无双环交叉链的构形了；而解决图3的办法则是在C—D环内或外交换经过围栏顶点1—2—3的A—B链或另外一条经过双环交叉链的交叉顶点8的A—B链，构形也就可以转化成坎泊已经证明过是可约的无双环交叉链的构形了。

关于有经过了三个围栏顶点的环形的A—B链的颜色冲突问题的构形，还想再多说几句。由于该A—B链中有三个顶点在围栏顶点上，所以能够形成的环形链并不只有一种，而是有多种的（如图5）。从图5中可以看出，有的环经过了三个围栏顶点，有的环经过了两个围栏顶点，还有的环只经过了一个围栏顶点；有的环经过了双环交叉链的交叉顶点8A，有的环则又不经过双环交叉链的交叉顶点8A。
图5中，A—B链把图分成了四个部分，每一部分中都有一条C—D链（或单个的C或D点），互不连通。交换任一部分中的C—D链，都可以使构形转化成坎泊已经证明过是可约的无双环交叉链的构形了。
对于无经过围栏顶点的环形链的构形（见图6），由于经过围栏顶点的A—B链和C—D链都不构成环，所以两链都不能交换。那么就只能使构形进行转型了。所谓转型就是使构形的峰点位置与颜色都发生变化。如从围栏顶点1B开始交换B—D链，构型就由原来的123—BAB型转化成了451—CDC型了，从围栏顶点3B开始交换B—C链，构型就由原来的123—BAB型转化成了345—DCD型了；构形的峰点位置分别由原来的顶点2变成了顶点5和4，峰点的颜色分别由原来的A色变成了D色和C色（见后面各图）。这种颜色冲突的构形，解决的办法也是较多的。

一是，改变图6中某个顶点的颜色（如图6中的加大顶点），就可以使构形转化成有经过了围栏顶点的环形链的构形（如图7和图8），用相应的解决有经过了围栏顶点的环形链的办法去处理就可以了。
二是，用转型交换法使构形转型，对图6从顶点1B开始交换B—D链，构形就转化成了有经过了两个围栏顶点的A—B环形链的构形（如图9），也可以用相应的办法去解决；但若顶点2A和7D间还有别的顶点，不能转化成有经过了围栏顶点的环形链的构形时，可以继续的按同一方向（逆时针方向）进行再转型，从顶点4D交换D—A链，构型就可以转化成一个可以连续的移去两个同色A的可约构形（如图10）。再从顶点2A交换A—C链后，就可以移去一个A（如图11），再进行一次交换后，就可以空出A或C来给待着色顶点V。共进行了两次转型。


若对图6从顶点3B开始交换B—C链，构形就转化成可以连续的移去两个C的可约构形（如图12）。再从顶点5C交换C—A链后，就可以移去一个C（如图13），再从顶点3C交换C—B链后，就可以连续的移去两个C，把C给待着色顶点V着上（如图14），当然也可以从顶点1B交换B—C，空出B来给待着色顶点V。只进行了一次转型。
这里的图6中是从顶点3B到双环交叉链的交叉顶点8A有A—B链（张彧典先生的第八构形就是这样），也有从顶点2A到8A有A—B链的（张彧典先生的第八构形的扩大图就是这样），这里就不再画图了。
三是，有时在非围栏顶点以外，还有不经过围栏顶点的局部环形链，该环形链内又有双环交叉链上的顶点存在（如图15，张彧典先生的第八构形的扩大图就是这样），这时用断链交换法，交换该局部环形链内的相反链，便可以使一条双环交叉链断开，构形成为无双环交叉链的可约构形如图（如图16）。这一方法不光是在这种情况下可以使用，无论是那种颜色冲突的构形，只要是有局部环形链存在，环内又存在着双环交叉链上的顶点时，都可以用这种方法进行解决。


以上我们研究无经过围栏顶点的环形链的颜色冲突构形时，用的都是非极大的非具体图的构形，转型的次数各不相同。现在我们再看一个具体的极大图构形（如图17）。这是1935年欧文提出的但却没有解决的颜色冲突构形（原图是地图形式的3—正则平面图，是一个轴对称图形，我把它改画成了它的对偶图——极大平面图了）。图中有一条从顶点2A到双环交叉链的交叉顶点8A的A—B链。再进行一下拓扑变化，就是一个轴对称的极大平面图构形（如图18）。
由于图17（即图18）的轴对称性，所以两个方向的转型结果一定是会相同的，所以我们就只进行逆时针方向转型（如图19到图24）。


在连续转型四次后，图就转化成一个可以连续的移去两个同色B的可约构形，再进行两次交换后，即可空出颜色B给待着色顶点V着上。其中第三次转型后的图21是一个既有经过了三个围栏顶点的C—D环形链，又有经过了两个围栏顶点的A—B环形链的构形，用两种解决有环形链的构形的方法都可以提前结束转型。
可以肯定的说，无经过围栏顶点的环形链的构形一定是可以通过转型交换法解决问题的。但现在还有一个问题就是转型的次数最大是多少的问题？这个问题解决不了，四色猜测还是不能被证明是正确的。在下一个问题中，我们再回答这一问题。

4、构造颜色冲突构形的模型
我们在研究无经过围栏顶点的环形链的颜色冲突构形时，用的是非极大的、非具体图的构形，并不是具体的极大平面图。这些构形是不是对应的都有一个顶点数最少的极大平面图存在呢？必须进一步的研究。
各种情况下的颜色冲突构形只要能找到一个顶点数最少的极大平面图，就可以用画任意极大平面图的方法，在某些面内增加顶点和边，并且对增加的顶点进行着色（一定可以着上颜色的），还可以对已知的链进行加长，就会得到各种情况下的任意顶点数的极大平面图构形，然后用相应的解决办法解决之。把各种情况下的颜色冲突问题所对应的顶点数最小的极大平面图，就叫做各种情况下的不可避免的颜色冲突模型。在解决颜色冲突问题时所用的非极大的平面图基础上，通过添加边的办法，一定是可以把非极大的、非具体图的构形变成一个具体的极大平面图构形的。这就是一种颜色冲突构形的模型。

无双环交叉链的构形对应的颜色冲突模型：4—轮构形模型如图25，5—轮构形可连续的空出两个同色B的模型如图26，5—轮构形可分别空出A、C、D三色之一的模型如图27。


有双环交叉链的构形对应的颜色冲突模型：可连续的移去两个同色B的模型如图28（可随便先移去那个B）的“九点形”、图29（可先移去顶点3的B）的“九点形”和图30（可先移去顶点1的B）“九点形”。而不可以连续的移去两个同色B的构型中，有经过了两个围栏顶点的C—D环形链的模型如图31；有经过三个围栏顶点的A—B环形链的模型如图32；无经过围栏顶点的环形链的模型如图33。
在以上模型的面中适当的增加顶点和边，就可以得到任意顶点数的颜色冲突的构形，都可采用3中解决5度构形的颜色冲突问题的各种方法进行解决。每一个模型都对应有一个地图，如图25，图26和图27对应的地图如图34，图35和图36（其他的对应地图就不画了）。


我还仿照图17和图18欧文构造轴对称图的办法,也构造了一个有三条均从顶点2A出发，分别经过了两个B色顶点，有一条经过了两条双环交叉链的交叉顶点8A的，且都是经过了三个围栏顶点的环形的A—B链的轴对称极大平面图构形。三条环形的A—B链把整个图分隔成了三个部分，每部分都有互不连通的C—D链。这虽是一个比较复杂的有经过了围栏顶点的环形链的颜色冲突的构形，但解决却是非常简单的。只要任意交换被环形的A—B链分隔成的某一部分内的C—D链，图就一定可以转化成无双环交叉链的可约构形了。
5、四色猜测是正确的
上面我们在构造颜色冲突构形模型时，是在原非极大的、非具体图的构形的基础上通过添加边来实现的。现在我们再用纯理论的方法构造一下最基本的颜色冲突构形模型。
敢峰（方玄初）先生是一位研究四色问题近四十年，已九十二岁高令，现在仍在研究着四色问题的老人。他在1992年时，用转型演绎的方法，用了十六步转型，在只有两条双环交叉链的构形（如图1）的基础上，构造了一个他叫做终极图的构形（如图39，图40和图41）。这个构形实际上就是1921年埃雷拉构造的埃雷拉图构形，只不过我们无从知道埃雷拉图是怎么构造出来的就是了。图39是敢峰先生所画的终极图，图40是埃雷拉，欧文，米勒和张彧典先生等人所用的待着色顶点是隐形的画法，图41是我把终极图改成了我在该文中的统一画法。

敢峰先生的终极图继续进行转型时，是一个永不休止的以二十次转型为一个周期的无穷周期循环转型的构形（这一性质欧文等早就已经认识到了），而且是逆时针或顺时针两个方向转型时，都有同样的性质。但由于该构形中不但有双环交叉链，又有经过了三个围栏顶点的环形的A—B链（还有一条不经过任何围栏顶点的环形的C—D链），所以可以交换A—B环内、外的任一条C—D链，构形都可以转化成无双环交叉链的可约构形。实际上欧文早在1935年也用同样的方法，也已经解决了这一颜色冲突问题，但其操作方法却没有我们现在论述得这样的简单明了。

敢峰先生的做法是这样的：每一步演绎都分两步（分别有两个图），前半步的图都是在前一步后半步的图的基础上，构造一个有双环交叉链的新构形；后半步的图都是对前半步的图先移去一个同色而得到的无双环交叉链的可约构形。但先生却并不急着去解决问题，而是在下一步的前半步时再进一步人为的构造一个新的有双环交叉链的构形。直到第十六步的前半步后，再进行转型演绎时，每转型一次得到的都是有双环交叉链的、且是有经过了围栏顶点的环形链的构形。敢峰先生的终极图原图是有经过了三个围栏顶点的环形链的构形，奇数次转型后，都是有经过了两个围栏顶点的环形链的构形，偶数次转型后，都是有经过了三个围栏顶点的环形链的构形。都可以用同样的方法去解决，在环形链内、外交换任一条相反链都可以使构形转化成无双环交叉链的可约构形。所以这个终极图完全能够代表任何有经过了围栏顶点的环形链的颜色冲突构形。这一转型演绎方法可见敢峰先生的《4CC和1＋1的证明》一书和敢峰先生在网上的有关研究四色问题的文章。
我曾对敢峰先生提出过，为什么在转型演绎过程第二步的前半步中不走截路而走了绕弯路的问题，可是先生的回答并没有使我感到很满意。后来我按照先生转型演绎的方法，不走弯路而走了截径，却得到了另外一种结果。在顺时针转型第九步前半步时，得到了一个有双环交叉链的无经过围栏顶点的环形链的颜色冲突构形模型（如图42）。


该构形再继续同方向转型时，并不象敢峰先生的终极图那样，永无止境的转型下去，而是在转型四次后，就转化成了一个可以连续的移去两个同色B的可约的构形（如图43——图46），再进行两次交换后，就可以连续的移去两个同色B（如图47和图48）。
然后把图46再向回转，逆时针方向转型，也是四次转型后就又得到了一个可以连续的移去两个同色的可约的构形（如图45——图42），图42就是我们转型演绎所得到的那个构形。把图42再两次交换后也可以连续的移去两个同色B给待着色顶点V（如图49和图50）。


图42——图46这五个颜色冲突的构形，无论向那个方向转型时，转型次数都是不会大于4的。这样的转型次数与我们前面研究无经过围栏顶点的环形链的颜色冲突构形的最大转型次数是相同的。所以，我构造的这个构形模型也是完全能够代表任何无经过围栏顶点的环形链的颜色冲突构形的（有关我用转型演绎法构造无经过围栏顶点的环形链的颜色冲突模型的方法，我将另外发表文章）。
在图43——图45这三个颜色冲突的构形中，都有经过了围栏顶点的环形的A—B链，也可以直接用断链交换法进行解决。对于图42来说，转型次数是奇数时，环形链A—B是经过了两个围栏顶点的，转型次数是偶数时，环形链A—B是经过了三个围栏顶点的。A—B环形链这样的转化规律与敢峰先生的终极图正好是一样的。由此还可以看出，该构形比敢峰先生的终极图更具有代表性。终极图只能代表有经过了围栏顶点的环形链（两种环形链都有）的构形，而该构形却除了能代表无经过围栏顶点的环形链的构形外，还能代表有经过了围栏顶点的环形链（两种环形链都有）的构形。从这个构形中，完全就可以看出各种有双环交叉链的颜色冲突问题应该如何去解决。

从图42——图46这五个颜色冲突的构形的转型次数都不大于4，与我们前面研究无经过围栏顶点的环形链的颜色冲突构形的最大转型次数是相同的这一现象看，决不是一个偶然的现象，而是一个必然产生的结果。这为我们彻底解决四色问题提供了帮助。任何无经过围栏顶点的环形链的颜色冲突构形都是可以在有限的4次转型之内解决的。四色猜测得到证明是正确的。即就是这个“4”不太保险，那么还有敢峰先生的终极图在作后盾。任何无经过围栏顶点的环形链的颜色冲突构形的最大转型次数一定是不会再大于20的。否则它也就成了无穷转型的构形了，但它却没有产生无穷转型的条件。终极图是有经过了围栏顶点的环形链的构形，而且还有一条不经过围栏顶点的环形链，两环形链如同两个“同心圆”一样是嵌套在一起的，而它却是无任何环形链的构形。
6、平面图画图、着色、构图与证明四色猜测的关系
四色问题研究的对象是地图，其对偶图就是极大的平面图。因此必须要掌握好地图与极大平面图的关系。极大图的各个顶点都是处在一个轮形图的中心位置，在对极大平面图着色的过程中，一定会遇到这样的顶点，与其相邻的顶点都已经着上了颜色。当与待着色的顶点相邻的顶点已占用完了四种颜色时，就是颜色冲突或染色困局。如何能通过坎泊的颜色交换技术，把有限种不可避免的颜色冲突构形的围栏顶点所占用的颜色数由4减少到3，把减下来的一种颜色给待着色顶点着上，这就是对四色猜测的证明。由于构形是一个非具体的、非极大的平面图，最后还必须能找到与之相对应的、顶点数最少的极大平面图。有了顶点数最少的极大平面图，就可以用画任意极大平面图的办法，得到任意顶点数的极大平面图的颜色冲突构形，当然也就有相对应的地图了。这才能叫对四色猜测进行了彻底的证明。也才是真正的证明了四色猜测是正确的。整个证明过程是从地图出发，最后又回到了地图。

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

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

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，