证明地图四色问题的新思路（初稿）

雷明85639720

证明地图四色问题的新思路（初稿）
雷  明
（二○二○年四月三十日）

    四色问题也叫四色猜出测。既然是猜测，就得进行理论上的证明。1852年英国的绘图员法朗西斯提出的地图四色猜测是：给任何一张地图的区域染色，使得有共同边界线的区域不用同一颜色，最多四种色就够用了。
1、极大平面图生成法证明四色猜测（纯理论法证明）
1、1  把一个地理问题转化成数学问题
地图是一个多分支（有公共无限面）并含有无顶环（国中之国的边界线）的无割边的3—正则的平面图，其对偶图是一个含有割点的且含有悬挂顶点的极大平面图。给地图的面（区域）的染色就是对其对偶图——极大平面图的顶点着色。这就把一个地理学中的给地图的区域的染色问题转化成了数学中对极大平面图的顶点着色的着色问题了。只要能证明极大平面图的四色猜测是正确的，地图的四色猜测也就是正确的了。同时，由于在相同顶点数的平面图中，以极大图的边数为最多，顶点间的相邻关系也最复杂，所以任何一个极大平面图经去顶或减边后，所得到的任意平面图的色数就只会比极大图的色数减少而不会再增大，所以任意平面图的四色猜测也就是正确的了。
1、2  证明过程
面数最少的地图是海地岛那样的地图，只有海地和多米尼加两个国家和一个海洋（即无限面）。它的对偶图是顶点数最少的极大平面图——K3图。在K3图的基础上，再给图中增加顶点和边，可以得到任意的极大平面图。图1和图2分别是在着有A、B、C三种颜色的K3图的面中增加顶点（如图中加大的顶点）和边得到的极大图和在K3图的边上增加顶点（也如图中加大的顶点）和边得到的极大图，所增加的顶点在所用的四种颜色中，至少还是有一种颜色可着的。


在此基础上若再在图中的某个三角形面内或边上增加顶点时，除了在边上增加4—度顶点外，其他情况都与图1和图2是相同的，只有在边上增加4—度顶点与图2，c有所不同（如图3，a）。此时增加的4—度顶点并不是只与同一个面中的顶点相邻，而是与两个面中的顶点相邻（如图3，a中的加粗边）。如果与所增加的顶点相邻的四个顶点占用完了四种颜色时（如图3，a），似乎该顶点没颜色可着了，因而不得不用第五种颜色，但事实上并不是这样。

因4—度顶点的两组对角的颜色构成的色链是不可能相互穿过的，所以最大只可能有一种色链不经过待着色顶点（图中的加大顶点，即新增加的顶点）可以是连通的，并与待着色顶点构成了一个圈（如图3,b中的加粗边），而另一种色链则一定是不连通的。这时就可以从不连通的那一组对角的任一个顶点开始交换该两个对角的颜色所构成的色链，空出一种颜色来给待着色的新增加顶点（如图3，c）。在这里是从与待着色顶点（图中的加大顶点）相邻的D色顶点开始，交换与其对角的A色顶点构成A—D色链，把D色顶点变成了A色顶点，空出了D色给待着色顶点V的。坎泊早在1879年就已证明了4—度待着色顶点是一定可以着上图中已用过的四种颜色之一的。
就这样，在新生成的更新的极大平面图内，进一步的增加顶点和边，只要保持图仍是极大平面图的情况下，一定就可以生成任意顶点数的、各顶点的度也是任意多的各种极大平面图。所增加的顶点一定都是可以着上图中已用过的四种颜色的。这就从理论上证明了任何极大平面图也都是可4—着色的，则任意极大平面图的四色猜测就是正确的。
2、不可免构形可约法证明四色猜测（着色实践法证明）
2、1  把一个无穷问题转化成有穷问题来处理
任何一个极大平面图的着色也都是一个顶点一个顶点的着色的，最后一定都会剩下只有一个顶点还未着色的图，把这样的还有一个顶点未着色的图就叫“构形”。极大平面图有无穷多种，每个极大平面图中的顶点数也可以是有无穷多个的，每个极大平面图中的每一个顶点的度也是任意的，也可以说是有无穷多的。从极大图的个数，每个图中的顶点数，每个顶点的度数三方面看，四色问题都是一个无穷的问题。但在图论中可以证明，任何一个平面图（当然也就包括极大平面图在内）中都一定含有至少一个顶点的度是小于等于5的，这就为把无穷问题转化成有穷问题创造了条件。
在着色时，我们总可以想办法把最后一个待着色的顶点安排在度是小于等于5的顶点之上。那么只要证明顶点度小于等于5的五种构形是否可约（即是否可4—着色）就可以解决四色猜测的证明问题了。这五种构形就是极大平面图的不可避免构形，由这五种构形就构成了平面图的“不可避免构形集”，简称“不可免集”。这就可把一个无穷的问题转化成一个有穷的问题来处理了。
由于极大平面图中的任何构形的待着色顶点都是处在一个轮形图的中心顶点位置，所以这种构形也叫轮构形，并把与待着色顶点直接相邻的顶点叫做围栏顶点。轮构形中除了待着色顶点外的其他顶点都是用四种颜色已经着了色并符合着色要求的图。解决构形的可约问题就是解决如何把待着色顶点着上图中已用过的四种颜色之一的问题。
1879年坎泊已经证明了任何无双环交叉链的构形都是可约的，但却把含有双环交叉链的构形漏掉了。在1890年时，赫渥特指出了坎泊证明中的这一漏洞。所以，现在只要能证明含有双环交叉链的构形是可约的，四色问题也就解决了。人们习惯上把坎泊证明已经是可约的构形叫做K—构形，而把赫渥特发现的、具有双环交叉链的构形叫做H—构形。
2、2  含有双环交叉链的构形

图4和图5分别是含有双环交叉链A—C和A—D的H—构形，因为A—C链和A—D链分别与待着色顶点V都成了一个圈（环），并且A—C链和A—D链不但有共同的起始顶点1A，中途又有相交叉的顶点8A，所以叫做“双环交叉链”。
具有双环交叉链的构形只可能出现在5—轮构形中，其他的轮构形中是不可能出现双环交叉链的，所以说，4—轮以下的构形，坎泊早已证明了都是可约的。具有双环交叉链的构形的共同特点是，A—C链和A—D链都是连通的，不能交换，也都空不出A、C、D三色之一给待着色顶点。但图4，a，图4，c图4，d三图却都可以从围栏顶点中连续的移去两个同色B，给待着色顶点着上，而图4，b和图5的4个图却都不能移去B。看来含有双环交叉链只是构成H—构形的必要条件而不是充分条件。没有它，不能构成H—构形，但有了它，却未必都是H—构形。

为什么同样都含有双环交叉链，有的能连续的移去两个同色B，而有的却不能呢？关键的是任意从一个B色的围栏顶点交换了与其对角顶点的颜色构成的色链后，是不是都能从另一个B色的围栏顶点新生成到其对角顶点的连通的对角链。只要有一个不能生成者，就是可以连续的移去两个同色B的可约的K—构形，否则就是H—构形。图4，a，图4，c图4，d三图都具有这种性质，所以是K—构形；而其他图都没有这种性质，所以是H—构形。
BAB型的H—构形一定是含有双环交叉链A—C和A—D的，其交叉顶点也一定是着A色的。那么两链的交叉顶点（A色）的前后一定都是C色和D色的顶点（如图4和图5中与顶点8A所相邻的顶点），与顶点8A相关联的面至少是有两个共用了一个顶点8A的、由A、C、D三色构成的对顶的三角形面。这样，8A、6C和7D三顶点间的边则一定都是单边，如果在那一条边上（特别是在6C—7D边上）再增加顶点，图就不再是H—构形了。
既然顶点8A、6C和7D构成的是一个面，那么在图的外部无限面中再增加任何顶点都一定是可以着上图中已用过的四种颜色之一的。加上图3和图4中的各图都是极大平面图，在其中的任何一个内部面内增加顶点，也都是可以着上图中已用过的四种颜色之一的，绝不会影响到图中其他顶点的颜色。所以只要以上图中的构形都是可约的，其他任何构形中只要含有以上的图作为分子图或分子构形，也一定都是可约的。这可能就是张彧典先生所说的“解法相同”、“构形最小”的原理吧。
2、3  证明
既然双环交叉链是构成H—构形的必要条件，那么只要想办法破坏了双环交叉链，图就应是可约的K—构形了。从图中可以看出，双环交叉链的关键顶点是1A、8A和4D、5C，只要这四个顶点的颜色发生了改变，双环交叉链也就不存在了，图也就转化成了无双环交叉链的可约的K—构形了。所以无论是从顶点1A或8A交换A—B链，或是从4D或5C交换C—D链，都可以使双环交叉的A—C链和A—D链中的两条或一条断开，图中也就不存在双环交叉链了。这样的交换方法叫做“断链交换法”。

为了防止交换A—B链（或C—D链）时，图中的所有着A色和B色的顶点（或着C色和D色的顶点）的颜色都发生改变，使交换变得没有意义或无效，必须在有环形的A—B链时，才可交换C—D链，在有环形的C—D链时，才可交换A—B链。为此，又可把含有双环交叉链的构形分为有环形链的构形（如图4，b、图5，a、图5，b）和无环形链的构形（如图5，c和图5，d）。有环形链的构形用断链交换法解决，即可转化成无双环交叉链的构形（如图6。图６，b中似乎仍有双环交叉链，但这时的A—C和A—D两链却并没有真正的“十”字交叉，不属于双环交叉链），而无环形链的构形需要再转化成有环形链的构形后再进行解决。
图6，a中含有经过了三个围栏顶点的环形的A—B链，交换该环内、外的任一条C—D链，都可以解决问题。1921年埃雷拉构造的E—图就可以这样来解决；图6，c中含有经过了两个围栏顶点的环形的C—D链，交换该环内、外的任一条A—B链，也都可以解决问题。1890年赫渥特构造的H—图就可以这样来解决。

图5中的c和d两个构形只是左右分布的不同，实际上都是无环形链的构形，所以只研究图5，c的可约性就可以了。
（1）把图5，c中的顶点9A改成9D时，图就转化成了有环形链C—D的构形了（如图7，b）；把图5，c中的顶点10C改成10A时，就转化成了有环形链A—B的构形了（如图7，d）。但构形峰点的位置和颜色都没有发生变化。
（2）在图5，c中从顶点3B开始交换B—C链，图就转化成了有经过了两个围栏顶点的A—B环形链的构形了。但这时构形峰点的位置和颜色却都发生了变化，由BAB型的构形转化成了CDC型的构形了（如图８）。

（3）在图5，c中从顶点1B开始交换B—D链，图就转化成DCD型的、可以连续的移去两个同色D的可约的K—构形了。再进行两次坎泊的空出颜色的交换，即可空出D给待着色顶点V着上（如图9）。
把以上的各种方法用在张彧典先生2010年构造的第八构形（一个无环形链的构形）上进行验证，也都是正确的。
（4）以上的构形都是A—B链和C—D链均是只有一条的情况，如果两链均不只是一条，而是有互不连通的多条情况时，将怎么办呢？张彧典先生的第八构形的放大图就是这种情况的反映。同一种链只要是有几条互不连通的几部分时，图中一定是含有与其呈相反色链的环形链部分存在，交换该环形部分内、外的任一条相反的色链，都可使双环交叉链的一条或两条遭到破坏，使构形转化成可约的K—构形。

从张先生的第八构形的放大图的解决中，可以看出，这里的交换任一部分的A—B链或C—D链，实际上也是在进行着切断双环交叉链的断链交换。所以说，经过了构形围栏顶点的环形链，并不一定都是要环形部分经过围栏顶点的，而只要是与环形部分相连通的相同色链的直线部分经过了围栏顶点，都可以认为是含有经过了围栏顶点的环形链的构形。这就使我们在处理H—构形时的方法更加灵活。可以看出，环形链并不是一定要使环形部分通过围栏顶点，而只要是与环形链连通的直链部分通过了围栏顶点，都可以视为是含有经过了围栏顶点的环形链的构形，都可以使用断链交换法解决问题。
（5）到此就证明了所有的无环形链的H—构形一定都是可以转化成有环形链的构形的。我们已经证明了有环形链的H—构形用断链交换的方法是可以解决问题的，所以任何H—构形就都是可约的了。也就不需要专门对无环形链的H—构形的最大转型交换次数是多少进行证明了。
3、四色猜测是正确的
现在我们已经用不同的两种方法——极大平面图生成的纯理论方法和平面图不可免构形的可约法对极大平面图的四色猜测进行了证明，都得到了四色猜测是正确的的结论，所以地图的四色猜出测和平面图的四色猜测也都是正确的。

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

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，