四色猜测的最终证明（简短版）（一）

雷明85639720

四色猜测的最终证明（简短版）（一）
英文标题：Final Proof of Four Colour Conjecture
雷  明
（二○一九年八月十一日）

【摘  要】本文把坎泊未能解决是否可4—着色的赫渥特构形，按其中是否含有经过围栏顶点的环形链，分为不可避免的三种类型，并且一一证明了这三种类型的构形都是可4—着色的，从而证明了赫渥特构形都是可4—着色的。加上坎泊在1879年早已证明了是可4—着色的构形，平面图的所有不可避免构形就都是可4—着色的了。这就证明了四色猜测是正确的。四色猜测可以上升为四色定理了。
英文摘要：[Abstract] As for Whether the Heawood,s Configuration can be 4-Coloured,which Kemble didn,t give the answer,this essay based on whether it contains ring chain passing the top of rail,shows 3 inevitable types,and proved all 3 types of configuration can be 4-coloured.Thus it proved that Heawood,s Configuraion can be 4-coloured.Plus Kemple,s proof of Configuration of 4-colour in 1879,all inevitable configurations of planar graph can be 4-coloured.Thus it proved that 4CC is correct,and the 4CC can be upgraded to Four Colour Theorem.
【关键词】四色猜测  图  平面图  构形  不可避免构形  着色  色链  可约
英文关键词：[Key words] four colour Conjecture, graph, planar graph, configuration, unavoidable configuration, colour, colour, co;our chain, reducible

四色猜测也叫四色问题。是由英图的绘图员法朗西斯（Francis Guthrie）在绘制英国地图的实践中于1852年提出的。即对任何行政区划地图（或者说把一个平面分成若干个部分的图）中的区域染色，在相邻区域不用相同颜色的情况下，最多四种颜色就够用了的地图四色猜测。这个猜测是否正确，还得要经过证明才能得出结论。虽然法朗西斯是提出猜测的第一人，后来也成为一名数学教授，任教于开普敦的南非大学，一直到1899年去世，但他对他所提出的问题却无任何建树。
一、证明前的理论准备：
1、地理问题转化成了数学问题：
从图论上看，行政区划地图就是一个连通且无割边的3—正则平面图,即是每个顶点都连有3条边的平面图。给地图中区域的染色就相当于给地图的对偶图——极大平面图（每个面都是三边形面的平面图）的顶点着色。这就把一个地理学中的问题转化成了数学中的问题了。地图四色猜测也就变成了平面图的四色猜测。
2、极大平面图的四色问题解决了，也就解决了任意平面图的四色问题：
在顶点数相同的平面图中，以极大平面图的边数为最多，如果任意的极大平面图的四色猜测是正确的，则极大图经减边或去顶后所得到的任意平面图的色数就只会是减少，而决不会再增加。所以说证明了极大平面图的四色猜测，也就证明了任意平面图的四色猜测。
3、四色问题研究的对象是无穷多的：
平面图有无穷多个，且每一个平面图中的顶点数也可以是任意多的，每一个平面图中的每一个顶点所连的边数（即度）也可以是任意多的，所以说四色问题所研究的对象是无穷多的。四色猜测也是不可能用对一个个的图去着色进行证明的，而必须把研究对象的无穷性变成有穷的。把一个无穷的问题转化成一个有穷的问题去解决。
4、坎泊提出的“构形”概念：
为了证明四色猜测，律师出身的坎泊在1879年提出了“构形”的概念。对任何极大平面图着色时，已着过色的顶点一定是符合着色要求的（相邻顶点不用同一颜色），也总能遇到待着色顶点是处在一个已着色的轮形图的中心位置的情况。把待着色顶点与已着过色的顶点共同构成的图叫做构形，并把与待着色顶点相邻的顶点叫做围栏顶点。由于待着色顶点也可以与任意多的围栏顶点相邻，所以构形的种类也是无穷多的。
5、平面图的不可避免构形——轮构形：
图论中可以证明，任何平面图中一定存在着至少一个顶点的度是小于等于5的。也就是说，在任何平面图中，度小于等于5的顶点是不可避免的存在的。用坎泊的地图术语来说，就是在任何地图中，都至少存在着一个国家与两个国家、三个国家、四个国家、五个国家相邻这四种情况中的一种。因此，所有顶点的度都是大于等于6的平面图和所有国家的邻国数都是大于等于6的地图，都是不存在的。这就为把无穷多的构形转化成有限多的5种不可避免的构形创造了条件。在着色过程中，我们总可以把待着色的顶点放在度是小于等于5的顶点上。只要证明了这五种不可避免的构形（简称不可免构形）是可4—着色的，也就证明了四色猜测是正确的。由于不可免构形的待着色顶点都是位于一个轮的中心顶点之上，所以也叫做轮构形。这就把一个研究对象是无穷的问题转化成了一个研究对象是有限的问题了。
6、3—轮以下的不可免构形都是可约的：
不可免构形的围栏顶点所占用的颜色数不大于３时，就至少还有一种颜色可以给待着色顶点着上。很自然的，不言而喻，3—轮以下的不可免构形和围栏顶点所占用的颜色数不大于3的所有构形，包括4—轮和5—轮两个不可免构形，就都一定是可约的了，即是可4—着色的。坎泊早在1879年就证明了这一点。“可约”一词也是坎泊早期提出的一个概念。
7、坎泊创造的颜色交换技术：
把用两种颜色交替着色的、由“顶点—边—顶点”构成的序列叫做色链，简称“链”。交换链中各顶点的颜色，可以达到改变链中任何一个顶点颜色的目的。这就是坎泊在1879年为证明四色猜测所创造的颜色交换技术。
8、4—轮构形的可约性：
若4—轮构形的围栏顶点已占用完了4种颜色（一个顶点占用一种颜色）时，就得使用坎泊所创造的颜色交换技术了。由4—轮的两组对角顶点的颜色分别构成的色链，对于两组对角顶点来说均不连通时（如图1，a），则可以从任何一个围栏顶点开始，交换该顶点与其对角顶点的颜色所构成的对角链，就可以空出该围栏顶点的一种颜色来给待着色顶点着上；若有一组对角链是连通的（如图1，b），该组对角链与待着色顶点就构成了一个“环”，则另一组对角链一定就不连通，并且分布在环的内、外两侧。这是因为两条互为相反链（相反链是指两条链中两种颜色完全不同的两条色链）的两条对角链中没有相同的颜色，是不能相互穿过的。这时，就可以从另一组对角的任何一个顶点开始，交换该组对角链的两种颜色，也可以空出该围栏顶点的颜色给待着色顶点着上。可见任何4—轮构形都一定是可约的。这就是坎泊对４—轮构形可约性的证明。

9、坎泊早已证明了无交叉链的5—轮构形都是可约的：
当5—轮构形的围栏顶点已占用完了4种颜色的情况下，至少有一种颜色在围栏顶点中是用了两次的。把由两个相同颜色的顶点所夹的顶点叫做构形的峰点，则双B夹A型的构形就用BAB表示，峰点着A色。坎泊在1879年早就用他所创造的颜色交换技术，证明了除图2,b的一种含有相交叉的A—C链和A—D链的5—轮构形外，其他不含相交叉链的5—轮构形都是可约的（以后人们就把坎泊已证明了是可约的构形叫做K—构形），就宣布他证明了四色猜测是正确的。但他却遗漏掉了含有相交叉链的这一种情况。

10、赫渥特构造了含有A—C链和A—D链相交叉的构形：

1890年，即在坎泊宣布他证明了四色猜测的11年之后，英图的赫渥特（Percy John Heawood）构造了一个其中含有A—C链和A—D链相交叉的图——赫渥特图（如图3，图中的b，r，y，g分别相当于这里所说的A，B，C，D四种颜色），指出了坎泊的证明有漏洞。但当时赫渥特和坎泊却都不能对他的图进行4—着色。后来在长达整整一个世纪的时间里，也一直没有人能对赫渥特图进行4—着色。四色猜测的证明一直处在停滞不前的状态。
11、赫渥特图是可以4—着色的：
赫渥特的图真是不可以4—着色吗，不是的。一个世纪后的1990年前后，就有我国的雷明，懂德周，英国的米勒等人仍然都还是用了坎泊的颜色交换技术，对该图在赫渥特原着色的基础上进行了4—着色，对坎泊证明中的漏洞进行了弥补。
12、对赫渥特图的分析：
赫渥特图中连通的A—C链和A—D链都是不能交换的，即就是交换了，也是空不出A，C，D三种颜色之一的。而B—C链和B—D链虽然不连通，但交换了其一B—C（或B—D）链，移去一个同色B后，又会生成连通的另一条B—D（或B—C）链，而不可能连续的移去两个同色B。既然是连通链，就不能进行交换，交换了也是空不出第二个同色B的。赫渥特图不能直接空出任何一种颜色这种情况的产生，则完全是由于A—C链和A—D链的相交叉所引起，所以该两链的相交叉就至少是构成H—构形的必要条件。把具有与赫渥特图这种相同结构和性质的构形，人们就叫做H—构形。又由于H—构形不能直接使用坎泊已用过的交换方法空出任何一种颜色给待着色顶点，所以人们也把这种构形也叫做“染色困局”。在H—构形中，以上的A—C，A—D，B—C和B—D四种链均不能交换，也空不出任何一种颜色来。那么，现在就只能再看一看A—B链和C—D链是否可以交换了。
二、H—构形可约性的证明：
1、H—构形的不可免集：
A—B和C—D两种链在图中的存在形式，只能有以下三种不可避免的形式：即A—B链是环形的且经过了B，A，B三个围栏顶点（如图4，a，图中加粗的线为环形链，其中的曲线是链而非单边，而直线是单边而非链。如果非围栏顶点的两顶点C、D间还有别的顶点时，图就成了可以连续的移去两个同色B的K—构形而非H—构形了。），或C—D链是环形的且经过了C，D两个围栏顶点（如图4，b，加粗线同上），或者经过围栏顶点的A—B链和C—D链都不是环形的，各是一棵树或一条直链（如图4，c，加粗线也同上）。虽然两种链都是环形链的构形也是存在的（如图5，加粗线也是环形链），但却分别属于含有A—B环形链一类或含有C—D环形链一类的构形，可以不再作为单独的一类处理。


除此三种情况外，再就没有别的类型了。这三类不可免的构形就构成了H—构形的不可免集，并且是非常完备的。这里请注意，以上所说的链都是指经过了围栏顶点的邻角链，以后再提到链时，也都是指这样的链。
2、不可免的H—构形的解法：
①　含有经过B，A，B三个围栏顶点的A—B环形链的构形（如图6，a）：构形中A—C链和A—D链两链的末端顶点C和D一定同是分布在A—B环形链的同一侧，交换经过这两个顶点的C—D链，就一定可以使A—C链和A—D链断链，图成为K—构形而可约。

②　含有经过了C，D两个围栏顶点的C—D环形链的构形（如图6，b）：构形中A—C链和A—D链的共同起始顶点A也一定是分布在C—D环形链的一侧，交换经过这个顶点的A—B链，也一定可以使A—C链和A—D链断链，图成为K—构形而可约。
以上两种有环形链的构形的解决办法，不仅适用于H—构形，而且也适用于K—构形。只要是含有环形链的构形，可以不去管它是否是H—构形，都可以用同样的方法进行解决。
③　无任何环形链的构形（如图6，c）：构形中A—B链和C—D链均不能交换，现在也就只能先交换一条关于B的链，先移去一个B，使构形转型了。对于BAB型的构形，从左B交换了B—D链后，成为DCD型；从右B交换了B—C链后，成为CDC型。然后再看转型后的构形，是否已成为可以连续的移去两个同色D（或C）的K—构形，或者成为以上两种有环形链的可约的H—构形。若仍不可约时，就继续进行同方向的转型，一定是可以在有限次的交换内，空出颜色给待着色顶点的。这种“转型交换”的交换次数为什么是“有限的”，我们将在后面给以证明。
3、5—轮构形转型交换的周期是20：
5—轮构形有5个围栏顶点，围栏顶点共占用了4种颜色。进行连续的转型交换，使得构形又转型成为BAB型，峰点A又回到原来的5—轮最上方一个顶点时，需要的交换次数是4和5的最小公倍数20次。这时，围栏各顶点的颜色均与最初转型前的颜色完全相同。再继续进行转型交换时，构形将以每20次交换为一个周期，无穷的转型下去，永远也不能空出颜色来。无论是进行逆时针方向转型，还是进行顺时针方向转型，都有同样的特点。
4、敢峰—米勒图类构形虽是无穷转型也空不出颜色的图，但却是可4—着色的：

有没有无穷次转型交换也空不出颜色来的构形呢？有。这就是敢峰—米勒图类的构形（如图7和图8。两图是同一个图，只是两种不同的画法。）。该类构形的确是无穷次的转型交换也空不出颜色的，两个方向的转型均是如此。许多学者的研究都说明了该图的转型过程的确是无穷循环的，循环的周期是20。但由于该类构形中有一条经过了围栏顶点的环形的A—B链（见图8中的外圈加粗边），可以交换A—B环形链内、外的任一条C—D链，使图变成K—构形而可约。该构形虽是无穷转型的，但却是可以4—着色的。


（未完接下一贴）

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，