证明四色猜测的关键是把无穷多的图转化成有限种类型的构形（最终稿）（一）

雷明85639720

证明四色猜测的关键是把无穷多的图转化成有限种类型的构形（最终稿）（二）
雷  明
（二○一九年元月二十六日）
（图我在这里发不上来，请到＜中国博士网＞上去看）

１、把一个地理学中的问题转化成一个数学问题
在地图中，把相邻的国家（区划）都染成不同的颜色，一张地图最多四种颜色就够用了。这就是1852年英图的绘图员法朗西斯在给英国地图染色时，提出的地图四色猜测。从图论上讲，地图不仅是一个平面图，而且是一个3—正则的平面图。其每一个顶点都连着3条边界线（即边），也就是所谓的“三不管地区”。对地图中面（区划）的染色，就是对地图的对偶图——极大平面图的顶点着色。这就把一个地理学中给地图中面的染色问题转化成了一个数学中给平面图的顶点着色的问题了。只要把极大平面图的四色猜测证明是正确的了，则地图四色猜测也就是正确的了。又因为极大平面图经去顶（点）或减边运算而得到的任意平面图着色时，所用的颜色数只会比极大平面图所用的颜色数减少，而不会再增加，所以，极大平面图的四色猜测被证明是正确的了，则任意平面图的四色猜测也就是正确的了。
2、把无穷多的平面图转化成有限种类型的构形
平面图有无穷多个，就某一个图来说，其顶点数也可能是无穷多的，不可能一个图一个图的去进行着色，而且也是不可能着色完的。那么，要解决四色问题，就必须把无穷多的平面图转化成有限种类型的“构形”。所谓构形就是在一个平面图中，除了一个顶点未着色外，其他顶点均已用四种颜色着色，并且符合着色要求——相邻顶点不用同一颜色——的图。把未着色的顶点叫做“待着色顶点”，把与待着色顶点相邻的顶点叫做构形的“围栏顶点”。待着色顶点与多少个围栏顶点相邻，也即连结着多少条边，在图论中就叫做待着色顶点的“度”是多少。不同的构形，围栏顶点数也都是不同的。所以，也可以说构形的围栏顶点数也是任意的，也是有无穷多的。这该如何办呢？
坎泊早已证明了在任何地图中，总存在着一个国家与两个国家相邻，一个国家与三个国家相邻，一个国家与四个国家相邻和一个国家与五个国家相邻这四种情况中的一种或几种情况，地图中所有国家都与六个及六个以上的国家相邻的地图是没有的；而在图论中也可以证明任何平面图中总存在着一个或几个顶点的度是小于等于5的顶点，全部顶点的度都是6以上的平面图是不存在的。这样就可以做到在着色时，一定可以把待着色顶点安排在度是小于等于5的顶点上。使得构形的围栏顶点数由可以是任意多个转化成有限的5（含5种）种以内。由于极大平面图的所有面都是三角形面，所以极大图中的每一个顶点都是处在一个轮的中心顶点位置。所以，这就把无穷多的平面图转化成了围栏顶点数是小于等于5的只是有限的六种类型的轮形构形了。
3、1879年坎泊对四色猜测进行的还存在“漏洞”的证明
把由围栏顶点中的任意两个对角顶点的颜色交替着色的“顶点—边—顶点”所构成的序列叫做“色链”，简称“链”。一条链若在两个对角顶点间是从一个顶点一直连结到另一个对角顶点时，则称该链为“连通链”，否则该链就是不连通的。把交换某链中各顶点颜色的过程叫做“颜色交换”，简称“交换”。把从构形的某一个围栏顶点开始的对角链的交换，叫做“对角链交换”。可以想象出，只有不连通的对角链交换后，才可以从围栏顶点中空出开始交换的转栏顶点所用的颜色给待着色顶点。而连通的对角链交换后是不能空出颜色的。
1879年坎泊只运用了对角链的交换，证明了0—轮（即K1图）构形，1—轮（即K2图）构形，2—轮（即2—重的K3图）构形，3—轮（即K4图）构形，4—轮构形以及5—轮构形中①无连通链的构形；②有一条连通链的构形；③有两条连通链，但两链只有一个共同的起始顶点，中途并不相交叉；④或者两链虽没有共同的起始顶点，但在中途又相交叉的四种构形是可约的（即可4—着色的。构形可约也是指构形围栏顶点所占用的颜色数可以由四种减少到三种），是可以从构形的围栏顶点中空出一种颜色给待着色顶点着上的。所以对角链交换法也可叫做空出颜色的交换。而坎泊在证明中却遗漏了对两条连通链既有共同的起始顶点，且中途两链又有相交叉顶点的构形的是否可约进行证明。这一遗漏在1890年被赫渥特用其构造的赫渥特图揭示了出来。但当时坎泊和赫渥特两个人都没有能对赫渥特的这个图进行4—着色。而在整整的过去了一个世纪之后，一直到了1990年，才有我们中国的雷明和懂德周，英国的米勒等，对赫渥特图在赫渥特原着色的基础上进行了4—着色。后来又有我国的张域典，刘福，颜宪邦，许寿椿等人，也都对赫渥特图进行了4—着色。
然而赫渥特图只是一个个别的图（也可以说是一个构形，因为其中还有一个顶点未着色），并不能代表任意的平面图。所以，只对这一个图或构形进行了4—着色，还不能从根本上说明四色猜测就是正确的。而要对具有赫渥特图结构特点的一类图都证明了其是否是可4—着色时，才能得出四色猜测是否是正确的结论。所以说，目前解决四色问题的关键，就是要解决好具有赫渥特图结构特点的一类图（即H—构形）的可约性的问题。
4、构成H—构形的必要条件
上一节已经说到了坎泊在证明中遗漏了的构形——赫渥特图型的构形是否可约，是证明四色猜测是否正确的关键。现在就分析一下该项图的特点。该图中有两条连通的、既有共同起始顶点的、且中途又有交叉顶点的色链，这是两条关键性的色链。有了这两条链，图才有可能构成H—构形。比如，从构形的围栏中的任何一个同色顶点交换了与其对角顶点的颜色构成的对角链后，又会生成从围栏中的另一个同色顶点到其对角顶点的连通链，造成不能连续的移去两个同色的状况。一致用简单的对角链交换是不能从围攻栏顶点中空出任何颜色来，这是问题的关键所在。但含有这两条链的图，却不一定都是H—构形，比如四个“九点形”图构形中都有这两条链，但其中的三个“九点形”图就不是H—构形。因为这几个九点形构形，从围栏顶点的中其中一个同色顶点交换了对角链后，可以不产生从另一个同色顶点到其对角顶点的连通链，可以连续的从围栏顶点中移去两个同色。所以说，含有两条连通的、既有共同起始顶点的、且中途又有交叉顶点的色链，只能是构成H—构形的必要条件，而不是充分条件。没有它，的确不能构成H—构形，但有了它，却不一定都是H—构形。
看来，要解决H—构形的可4—着色（可约）问题，必须破坏上述两条连通的、既有共同起始顶点的、且中途又有相交叉顶点的色链，特别是两链的交叉性，使其不存在构成H—构形的必要条件。破坏这两条链的办法有两种：一是改变两链的起始顶点或交叉顶点的颜色，二是改变两链各自末端顶点的颜色。在BAB型的5—轮构形中，两链的共同起始顶点和交叉顶点都着A色，两个同色顶点着B色，两链的末端顶点分别着C色和D色。要改变两链的共同起始顶点或交叉顶点的颜色，则必须交换通过两链共同起始顶点或交叉顶点的A—B链。为不使图中的全部A色和B 色的顶点都改变颜色（因为全部的A色顶点和B色顶点的颜色都改变了是没有任何意义的，相当于没有改变任何顶点的颜色），所以必须有一条环形的C—D链将A—B链进行隔离；同样的，要改变两链各自的末端顶点的颜色，也必须交换通过各链末端顶点的C—D链，并且也要有一条环形的A—B链将C—D链进行隔离。
5、把无穷多的H—构形转化成有限种类型的不可免构形
现在仍以BAB型的5—轮构形为例来进行说明。H—构形中都有连通的、且既有同一个起始顶点，中途又有交叉顶点的A—C链和A—D链，所以该两链也都是不能进行交换的，也是空不出颜色A、C、D三色之一来给待着色顶点着上的。又因为H—构形从任何一个B色顶点交换了其对角链后，则会产生从另一个B色顶点到其对角顶点的连通链，是不可能连续的移去两个同色B的构形，所以暂时B—C链和B—D链也还是不能进行交换的。而可以交换的链现在就只有A—B链和C—D链了。又因为A—B链和C—D链是一对“相反色链”（即两链中的四种颜色都是完全不相同的色链），所以A—B链和C—D链两链也一定是不可相交叉的两种链。

根据构形的结构特点，按可以交换的链A—B链或C—D链是否是环形链，可将全部H—构形分成三类：第一类是含有构形的三个围栏顶点的A—B环形链的构形（如图1）；第二类是含有构形的两个围栏顶点的C—D环形链的构形（如图2）；第三类是不含任何环形链的构形（如图3和图4）。当然也还有既含有A—B环形链，又含有C—D环形链的一类构形，既有第一类H—构形的特征，又有第二类H—构形的特征。它们既是属于第一类H—构形，又是属于第二类H—构形，至少可以用其中某一类构形的解决办法进行解决（在后面就会看到这一情况）。也正是因为这样，所以这里就不再单独列为另一个类别了。
以上图1到图4中的构形，待着色顶点采用了隐形画法（不画出待着色顶点的画法）。图中除了构形的5个围栏顶点间及围栏顶点与待着色顶点间的边（未画出），以及顶点6和顶点7间的C—D边均是单边外，其他的边均可看成是由该边的两个端点顶点的颜色所构成的色链。因为这两个顶点间如果再有别的顶点，图就不是H—构形了。从一个同色顶点B交换了与其对角顶点的颜色构成的色链后，就不会产生从另一个同色顶点B到其对角顶点的连通链，图就成了可以连续的移去两个同色B的K—构形了。图中只画出了主要的链的关系，其他的顶点和边均未画出，所以可以认为以上的图是极大的平面图，也可以认为是任意的平面图。但未画出的顶点，根据构形的定义，都是只用了A，B，C，D四种颜色之一着色的顶点，且也是符合着色的要求——即相邻的顶点不用同一种颜色的。
这三类构形就是H—构形的“不可避免的构形”，简称“不可免构形”。由以上三类构形就构成了H—构形的“不可避免构形的集合”，简称“不可免集”。该集中的各个不可免构形，均含有两条既有共同起始顶点2的，在中途又含有相交叉顶点8的连通的A—C链和A—D链（如图中的加粗边），所不同的只是A—B链和C—D链的分布结构不同（也如图中的加粗边）。除了这三种情况以外，A—B链和C—D链就再也没有别的分布组合了，所以这个不可免集也是完备的。这就又把似乎也是无穷多的H—构形转化成了只有三个种类型的不可免的H—构形了。只要证明了这三类构形是可约的，即是可4—着色的，四色猜测也就证明是正确的了。
著名的赫渥特图中含有经过构形的两个围栏顶点的环形的C—D链，是属于第二类H—构形。而敢峰—米勒图中含有经过构形三个围栏顶点的环形的A—B链，该图中虽然也有环形的C—D链，但该链却没有经过构形的4和5两个围栏顶点，所以该图只能是属于第一类H—构形，而不能也属于第二类H—构形。张彧典先生的第八构形中不含任何的环形链，所以该图是属于第三类H—构形的。
6、各类不可避免的H—构形的可约性
6、1  第一类H—构形的可约性
图1的第一类H—构形的解决办法是交换环形的A—B链内、外的任一条C—D链，都可使图中原有的A—C链和A—D链断开，变成不连通的，图成为K—构形而可约。
6、1、1  从A—B环外的顶点4和5交换C—D链：
对图1从A—B环外的顶点4和5交换C—D链，得到图5—1。图中尽管仍含有从顶点1到顶点4的A—C连通链和从顶点3到顶点5的A—D连通链，且在中途又有着A色的共同顶点，但两链却没有实际上的“X型”相交叉。若图1本身就是一个具体的图，则图5—就已是一个可约的K—构形了，可以空出A，B，C，D四种颜色的任何一种给待着色顶点。但做为一个构形，正是因为图中的A—C链和A—D链没有实际的“X型”相交叉，在平面图范围内仍可以构造从顶点1到顶点4的B—C链和从顶点3到顶点5的B—D链，两链在中途又有着B色的相交叉的顶点，使图成为一个不能连续移去两个同色Ｂ而只能空出A，C，D三色之一的K—构形（如图5—2）。

由于B—C链和B—D链与A—D 链和A—C链是两对相反的色链，所以在构造不出两条相交叉的连通链B—C链和B—D链时，在平面图范围内，也有可能构造出两条新的连通且相交叉的A—C链和A—D链（如图5—3）。图５—3又是一个只能移去一个同色B而不能连续的移去两个同色B的构形（如图5—4）。所以图5—3又是一个第一类H—构形。
而图5—3再交换了经过顶点4和5的C—D链后，又会产生新的连通且交叉的A—C链和A—D链，图仍是一个第一类的H—构形（如图5—5），也只能移去一个B而不可连续的移去两个B（如图5—6）。以至以后再交换经过顶点4和5的C—D链时，图总是的图5—3与图5—5间转化着，永远都是一个有经过三个围栏顶点1B，2A和3B的第一类H—构形，只是顶点4和顶点5的颜色相互交换了一下。
是不是图1就不可约呢，请看下面的“从A—B环内的顶点6和7交换C—D链”一节。

6、1、2  从A—B环内的顶点6和7交换C—D链：
对图1从A—B环内的顶点6和7交换C—D链，得到图6—1。若图1就是一个具体的图，则图6—1就已是一个可约的K—构形了，可以连续的移去两个同色B。图6—1虽与图5—1类似，A—C链和A—D链都没有实质性的“X型”相交叉，但图6—1却不可再能构造出从顶点1到顶点4的B—D链，也构造不出从顶点3到顶点5的B—C链。虽然如此，但还是可以再构造出两条新的连通且相交叉的A—C链和A—D链（如图6—2）。

图6—1和图6—2都是一个可以连续的移去两个同色B的K—构形。因为从任何一个B色顶点交换了其对角链后，都不会产生另一B色顶点到其对角顶点的连通链，如图6—3、图6—4、图6—5和图6—6。图6—2中的连通的A—C链和A—D链分别各有两条，从顶点1开始的B—D链，可以首先穿过位于左侧的A—D链，但最终却不可能再穿过A—C链；而从顶点3开始的B—C链，也可以首先穿过位于右侧的A—C链，但最终却不能再穿过A—D链。所以这个图6—2也是一个可以连续的移去两个同色B的K—构形。
在6、1、1节中，尽管对图1从A—B环外的顶点4和5交换C—D链后，变成图5—3和图5—5时，产生了循环现象，但对图1（第一类H—构形）从A—B环内的顶点6和7交换C—D链仍是可以解决问题的。
敢峰—米勒图是一个第一类H—构形，其着色时交换A—B环形链内、外的任一条C—D链都是可以的。
6、1、3  如何处理6、1、1节中图5—3和图5—5的问
现在对图5—3和图5—5也象图象对待图1那样，交换经过顶点6和顶点7的C—D链，分别得到图6—7和图6—9，这两个图也仍然是不能移去两个同色B的第一类H—构形，各从任一个B色顶点交换了对角链后，又会产生了从另一个B色顶点到其对角顶点的连通链（分别如图6—8和图6—10）。
看来图5—3与图5—5，还有这里的图6—7和图6—9，似乎是再也不可能转化为K—构形而可约。但我们发现，这四个图中不但含有经过构形的三个围栏顶点1，2和3的A—B环形链，又含有经过构形的两个围栏顶点4和5的C—D环形链，既有第一类H—构形的特征，又是第二类H—构形的特征，用解决第一类H—构形的办法没有进行解决，那么用解决第二类H—构形的办法应该是能够解决的。在下面6、2节中我们就可以看到，这四个图的确也都是可约的。

6、2  第二类H—构形的可约性
图2的第二类H—构形的解决办法则是交换经过该构形三个连续相邻的围栏顶点1、2和3的A—B链（如图7—1），或者交换经过A—C和A—D两连通链的交叉顶点8的A—B链（如图7—2），都可使图中原有的A—C链和A—D链也均可变成不连通的，图也成为K—构形而可约。图7—1和图7—2都是可以空出任何一种颜色的K—构形。图7—2还可构造出连通且相交叉的B—C链和B—D链（如图中的虚线所示），成为只可能空出A，C，D三色之一的K—构形。

上面6、1节中的图5—3、图5—5、图6—7和图6—9，既然也是属于第二类H—构形，也就应该用解决第二类H—构形的方法是可以解决的。把图5—3和图6—9中的C—D环形链外的、经过顶点1、2和3的A—B链进行交换（分别如图7—3和图7—4）和把图5—5和图6—7中的C—D环形链内的A—C链与A—D链的交叉顶点（图中的加大顶点）的颜色由A改成B（如图7—5和图7—6），都可以使两图中的连通且交叉的A—C链和A—D链断开，变成不连通的，使图变成只能移去A，C，D三色之一而不能连续的移去两个同色B的K—构形。到此，也就证明了6、1节中的图5—3、图5—5、图6—7和图6—9也都是可约的。

著名的赫渥特图是属于第二类H—构形，其解决时，只要交换环形的C—D链内、外的A—B链就可以使图变成可约的K—构形。
由于解决第一类和第二类H—构形的方法，都是首先使连通且既有共同起始顶点的、中途又有交叉顶点的两条链A—C和A—D断开，破坏了形成H—构形的必要条件，因此，该方法也可以叫做“断链法”。由于断链法交换的是由构形的围栏顶点的邻角顶点颜色构成的链，所以也可以叫断链法为“邻角链法”，以区别于坎泊证明四色猜测时所交换的都是对角链的“对角链法”。由于断链法交换是不能直接空出颜色的，所以最后还是得要用可空出颜色的对角链法交换解决问题。
6、3  第三类H—构形的可约性
图3的第三类H—构形的解决，就不能象图1和图2那样的进行交换了，因为其中的A—B链和C—D链都不是环形链而是直链不能交换。现在就只能交换B—C链和B—D链之一，使构形转型，并使图直接变成K—构形或者先变成上面的第一类、第二类H—构形，再进行解决。否则，若不能变成这三种构形时，就只能再继续进行同方向的转型交换了，直到能够转化成以上三种构形，能够空出颜色为止。图3与图4是实际上是同一类构形，只是左右不同罢了，所以只研究图3一个就可以了。
6、3、1  逆时针方向转型
对图3从顶点1交换B—D链时（一次转型交换），产生了从顶点3到顶点5的连通链B—C（如图8），虽不能连续的移去两个B，但图8却是一个DCD型的可以连续的移去两个同色D的K—构形。当对图8从顶点4交换D—A链时（二次转型交换），不能生成从顶点1到顶点3的连通链D—B（如图9），这就可以再从顶点1交换D—B链，连续的移去两个同色D，或者从顶点2交换B—D链，空出B来（图请读者画）。

图9虽然没有从顶点1到顶点3的连通链D—B，但在平面图范围内，却有生成该链的可能（如图10—1），这样就成了一个ABA型的不可能连续的移去两个同色D的H—构形了，只有再继续进行转型。对图10—1从顶点2交换A—C链时（三次转型交换），同样的也有从顶点4到顶点1生成连通的A—D链的可能（如图10—2）。
对图10—2从顶点5交换C—B链时（四次转型交换），也还有可能有再从顶点2到顶点4生成连通的C—A链（如图10—3）。

但到第五次转型交换时，从图10—3的顶点3交换B—D时，就永远不可能再产生从另一个同色顶点5B到其对角顶点2C的连通链B—C了（如图10—4），说明这时的图10—3已经变成了一个可以连续的移去两个同色B的构形了。再进行一次交换就可以空出颜色来。总共是六次交换。请读者自已试试，完成作图。
6、3、2  顺时针方向转型
若对图3从顶点3交换B—C链时（一次转型交换），产生了从顶点1到顶点4的连通链B—D（如图11），虽不能连续的移去两个B，但图11却是一个CDC型的第二类H—构形了，图中含有经过构形两个围栏顶点的A—B环形链，已是可约的了（如图2，图7—1和图7—2那样）。当对图11再从顶点5交换C—A链时（二次转型交换），也有可能生成从顶点3到顶点1的连通的C—B链（如图12—1）。

继续转型下去，第三次转型交换后，第四次转型交换后，结果都有可能从另一个同色顶点到其对角顶点的连通链（分别如图12—2和图12—3）,图仍是H—构形。
同样的,也是在五次转型交换时，对图12—3从顶点1交换B—C时，就永远不可能再产生从另一个同色顶点4B到其对角顶点2D的连通链B—D了（如图12—4），也说明这时的图12—3已经变成了一个可以连续的移去两个同色B的构形了。再进行第六次交换后就空出了颜色（如图12—5）。

张彧典先生的第八构形就是一个第三类H—构形，逆时针转型交换一次，图就变成了一个可以连续的移去两个同色D的K—构形而可约；顺时针转型交换一次，图就转化成了一个第二类H—构形而可约了。
6、3、3  有对称轴的第三类构形的交换
第三类构形在连续转型交换的中途可直接转化为K—构形，或者可以转化成第一类和第二类构形。若改用断链法时，仍可以在六次交换内空出颜色。
但对于轴对称的第三类构形（如图13）来说，在第三次转型交换后，就可得到一个既是第一类，又是第二类的构形（如图14），改用断链法后，虽然也可以在六次交换内空出颜色。但在连续转型交换时，两个方向的转型交换，却都必须要进行六次交换才能空出颜色。

6、3、4  可用连续转型交换解决的部分第一类H—构形和第二类H—构形的交换
上面我们已经说了，第一类H—构形和第二类H—构形用各自的交换邻角链的断链法解决，最大3次交换就可以解决问题；而第三类H—构形用转型交换法，从两个方向交换，均只要进行6次交换就可以了。我们还对部分可以用连续转型交换法解决问题的第一类H—构形和第二类H—构形进行了交换。对于这两类H—构形来说，无论是逆时针转型还是顺时针转型，都是最多6次交换就可以空出颜色来。这里就不再画图了，请读者自已动手画一画。
（未完，接下贴）

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，

雷明85639720

，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，