平面图的不可避免构形及其可约方法（修改稿）

雷明85639720

平面图的不可避免构形及其可约方法
——兼论四色猜测的证明（修改稿）
雷  明
（二○二○年六月二十七日）
（这里图又发不上去了，请到《中国博士网》上去看）

    1、目前研究四色问题应解决的主要问题
四色问题因给地图的着色而引起，所以证明四色猜测还得从研究地图而着手。地图本身就是一个无割边的3—正则的平面图（每条边都与两个面相邻，每个顶点都连有3条边），给其面上的着色就是对其对偶图——无环极大平面图（每个面都是3—边形面）——的顶点着色。这就把一个地理学问题转化成了一个数学问题了。极大图的每个顶点都是处在一个轮形图的中心位置，又因为任何平面图中都一定至少存在着一个顶点的度是小于等于5的，所以平面图的不可避免构形就只是度小于等于5的轮构形。这就又把一个研究对象是无穷多的问题也转化成了一个研究对象是有穷的问题了。
1879年，坎泊已经证明了不含双环交叉链的构形都是可约的，却没有彻底解决含有双环交叉链的构形的可约性的问题。所谓的“双环交叉链”，是指在BAB型的5—轮构形中，从2A到5C的A—C链和从2A到4D的A—D链既有共同的起始顶点2A，中途又有相交叉的交叉顶点8A，两链与待着色顶点V均构成了一个“环”，所以叫做双环交叉链。图1就是四个含有双环交叉链的构形。虽然同样都是含有双环交叉链的构形，但有的却是可以连续的移去两个同色B的可约构形（如图1，a，图1，c和图1，d三图。其图中除了构形的围栏边外，其他任何边也都可以认为是由该边两个端点顶点的颜色构成的色链）；而有的则是不可以连续的移去两个同色B的构形（如图1，b。同样的，其图中除了构形的围栏边外，其他任何边也都可以认为是由该边两个端点顶点的颜色构成的色链。除此之外，在顶点6C和7D之间也不能存在任何顶点，否则也将是一个可以连续的移去两个同色B的构形）。

因为不含双环交叉链的构形和虽含有双环交叉链但可以连续的移去两个同色B的构形都已经是可约的构形，所次就统一叫做K—构形，即坎泊构形；相应的，则把含有双环交叉链的又不可以连续的移去两个同色B的构形，叫做H—构形，即赫渥特构形。目前研究四色问题，主要的任务就是解决含有双环交叉链但又不可以连续的移去两个同色B的构形的可约性问题了。
2、H—构形的分类及相应的解决办法
只所以H—构形不可以连续的移去两个同色B，是因为从任何一个B色顶点交换了与其对角顶点的颜色构形的色链后，就会新生成从另一个B色顶点到它的对角顶点的连通链，而不能连续的移去两个同色B。既然这种情况是因具有双环交叉链而引起，那么我们就想办法把双环交叉链进行破坏，使构形转化成不含双环交叉链的可约的K—构形。
双环交叉链上有四个关键的顶点，一是两链的共同起始顶点2A，二是两链的交叉顶点8A，三是两链的末端顶点5C和4D（如图2）。只要这四个顶点的任何一个顶点的颜色进行了改变，就可以使双环交叉链的两条或一条断开，图就转化成了不含双环交叉链的可约的K—构形了。

（1）有环形链的H—构形
如何能使双环交叉链断开呢？就得在A—B链和C—D链上下功夫。因为A—B链和C—D链互为相反链，是不能相互穿过的。所以只要有一条是经过了以上四个围栏顶点之一的环形链时，其相反链一定被隔在该环形链的两侧而不连通（如图3和图4）。这时从以上四个顶点之一交换被隔在“环”内或“环”外的任一条相反链，一定可以使双环交叉的两条连通链都断开或者不存在双环交叉链了（因为4D和5C是相邻的，所以两个顶点是同时改变颜色的，两链也就同时断开了，而2A和8A本身就是两链的共同顶点，改变了任何一个顶点的颜色，两条链也就同时断开了），构形也就转化成了可约的K—构形。这就是有环形链的H—构形及其解决的方法。这一方法也可以叫做“断链交换法”。前面的图1，b就可以用这种方法进行解决。交换后图中的双“环”链中途虽仍有共用的顶点，但却没有实际意义上的“十字交叉”，所以不是H—构形，而是可以连续的移去两个同色的K—构形。

（2）无环形链的H—构形

还有一种是没有环形链的H—构形，即通过以上四个顶点的链均不是环形链的构形（如图5）。对这种无环形链的H—构形来说，虽然不可能用断链交换法解决问题，但这种构形的解决方法却是较多的。
其一，是把图5中其中的一个加大顶点的颜色进行改变，就可以使图转化成如图３和图４一样的有经过了上述关键顶点的环形链的H—构形（如图3和图4），可以再通过断链交换方法转化成可约的K—构形。
其二，是交换一个关于两个同色B的链，使构形转型，并转化成有经过了关键顶点的环形链的H—构形，或者直接转化成可以连续的移去两个同色的可约的K—构形。图6是对图5从顶点3交换了B—C链的结果，是一个CDC型的有经过了双环交叉链末端的A—B环形链的H—构形；图7是对图5从顶点1交换了B—D链的结果，是一个DCD型的可以先从顶点4交换D—A链，再从顶点1交换D—B链，可以连续的移去两个同色D的可约的K—构形（读者可以自已做一下，看是否可以连续的移去两个同色D）。
以上两种方法并不是对于所有的无环形链的H—构形都适用。可以从图中看出，以上的图都不是极大图。而适用于所有H—构形的方法则是另外一种交换方法——连续的转型交换法。我们将作为一个专题去研究它。
3、用连续转型交换法处理无环形链的H—构形
其三，是用连续转型交换的方法解决无环形链的极大图（H—构形）的可约性问题。
以上研究的图都是非极大图型的H—构形，也都是可约的。但对于极大图来说，有环形链的H—构形也一定是可以通过“断链交换法”解决问题的；而对于无环形链的极大图构形来说，就只能通过连续的“转型交换法”解决了。
可以这样来考虑和分折问题：在对图5的非极大图的构形进行连续转型时，当遇到转型结果是可以连续的移去两上同色的构形时，可以人为的在平面图的范围内，适当的增加顶点和边，使其不能连续的移去两上同色。也就是说，当交换了一个关于两个同色的链后，就人为的在平面图范围内构造从另一个同色顶点到其对角顶点的连通的对角链，然后再继续的对其进行连续的转型。看一看转型的次数是否是有限的。如果有限，四色问题就得到了彻底解决，否则还是不能说明（证明）四色猜测就是正确的。这样连续的构造连通链，也就相当于把非极大图转化成了极大图。
现在对图5进行逆时针和顺时针两个方向的连续转型如下：

这里我们虽把图5的顶点数进行了进一步减少，但仍保持原来的含有的A—C链和A—D链“双环交叉链”，且不能连续的移去两个同色B的特征（如图8，0）。
首先，进行逆时针方向转型，在第五次转型后，图就是一个可以连续的移去两个同色的可约的K—构形了。共进行了有限的五次转型，七次交换（如图8，0到图8，7）。把第五次转型的结果图8，5适当的增加一些边后，就是极大图了。这就是前面所说的“连续的构造连通链，也就相当于把非极大图转化成了极大图”的意义。

再进行顺时针方向转型，在第四次转型后，图就成了一个可以连续的移去两个同色的可约的K—构形。共进行了有限的四次转型，六次交换（如图9，1到图9，6）。转型和交换的次数均比逆时针方向转型少了一次，这是因为图的左右不对称的原因。把这里第四次转型的结果图9，4也适当的增加一些边后，也就是极大图了。

两个方向转型次数最大的是逆时针方向转型时，在第五次转型后才转化成了可以连续的移去两个同色的可约的K—构形。但这却是一个这是一个必然的结果。因为每转型交换一次，构形峰点的位置和颜色即发生一次变化。逆时针转型时峰点和两个同色的变化规律是：BAB（123）—DCD（451）—ABA（234）—CDC（512）—BAB（345）；顺时针转型时峰点和两个同色的变化规律是：BAB（123）—CDC（345）—ABA（512）—DCD（234）—BAB（451）。都是每转型四次一个周期，图必须在一个周期以内完成从H—构形向K—构形转化的过渡。否则，当第五次转型再不转化成K—构形时，图的峰点位置和颜色将会出现周期性的循环，就不可能再空出颜色来了。只所以无环形链的H—构形，不可能发生周期性的循环现象，主要是因为它不存在象E—图（即埃雷拉图）那样的既含有经过了围栏顶点、但又未经过双环交叉链的交叉顶点的环形链这一基本条件。请注意，没有这个条件不可能成为E—图类构形，但有了这个条件却不一定都是E—图类构形。所以这只是一个基本条件，或者说是必要条件，而不是充分条件。
4、无环形链的H—构形的最大转型次数
现在来回答最大的转型次数道底是多少的问题。
图8，0两个方向转型的结果，最后得到的都就一个K—构形。再对这个构形进行“逆向”连续转型，在适当的次数（原逆时针方向转形的“逆向”转形仍是五次，原顺时针方向转形的“逆向”转形仍是四次）后，一定会转化成（即返回到）转型最初始状态的BAB（123）型的构形（如图10，0和图11，0）。图10，0和图11，0这两个图分别进行五次逆时针转型和四次顺时针转型后，都可以转化成可以移去两个同色的K—构形，这是不言而喻的（就不再画图了）。但对这两个图再都继续进行一次“逆向”转型后，都就可以转化成可以连续的移去两个同色的K—构形（如图10和图11）。

把图10，0和图11，0再都适当的增加一些边，也都可以变成极大图（如图12，0和图13，0）。由于图8，0在进行转型时，逆时针和顺时针两个方向转型次数是不同的，所以从逆时针转型得到的极大图（图12，0）和从顺时针转型得到的极大图（图13，0），在进行转型时，两个方向的转型次数也是不同的。图12，0的两种转型都是在进行一次转型后，就得到了可以连续的移去两个同色的K—构形（如图12）；而图13，0的两种转型却都是在进行两次转型后，才得到可以连续的移去两个同色的K—构形（如图13）。

可以看出，极大图的转型次数比非极大图的转型次数是要少的，这一情况产生的原因是因为把非极大图通过增加边变成极大图后，改变了图中顶点间的相邻关系，从而也就改变了图中原有链间的关系的原因所致。
在对无环形链的极大图（H—构形）作连续的转型交换时，还经常会遇到在转型中途图就已转化成了有环形链的H—构形的情况，这时，就应尽早的用断链交换法进行解决。
总之，可以看出，对于任何一个无环形链的H—构形，无论是极大图还是非极大图，一定都是可以在五次转型之内使构形转化成可以连续的移去两个同色的K—构形的。转型的次数都是有限次的，总的交换次数也都等于转型次数加2（2即空出颜色的交换次数），最大的交换次数只是有限的7次。这就为彻底解决四色问题创造了条件。
我这里所说的最大转型次数与张彧典先生所说的最大“颠倒次数”是有区别的。我这里的结论只是适用于无环形链的H—构形，并不是象张先生那样，还包括含有环形链的构形在内的所有非埃雷拉图的构形。
5、对张彧典先生15个Z—构形的分析
张彧典先生所谓的由改变E—图构形中的“四色四边形”对角线的方法所得到的15个Z—构形中：
Z1和Z15都是可以直接的连续移去两个同色B的K—构形。Z2到Z5四个构形无论进行那个方向的转型，都不会超过四次转型，图就会转化成可以连续的移去两个同色的K—构形，或者转化成有环形链的H—构形。这四个构形到达空出色给待着色顶点时，最大也只是交换7次。
Z6到Z10五个构形本身就是具有环形链的H—构形，最大交换3次就可以解决问题。
Z11到Z14四个构形与Z2到Z5四个构形同样也是无论进行那个方向的转型，也都不会超过四次转型，图也就会转化成可以连续的移去两个同色的K—构形，或者转化成有环形链的H—构形，最多交换7次就可空出颜色来给待着色顶点。
不知张先生为什么要对某些Z—构形单方向转型时要达到16次之多的交换呢？
从张先生和我共同构造的仅有的单方向转型次数大于16次的个别构形看，它们都是含有环形链的H—构形，都是可以直接用断链交换法进行解决的。所以我认为张先把H—构形分为E—图类构形和非E—图类构形，用Z—换色程序解决E—图类H—构形，用H—换色程序解决非E—图类H—构形，都是不科学的。因为张先生并不能证明单方向转形的最大转型次数和最大交换次数是多少。
6、四色猜测是正确的
现在，含有双环交叉链，又但不可以连续的移去两个同色B的构形的可约性问题已经解决了，则平面图的所有不可避免构形就都已经是可约的了，那么四色猜测也就得到证明是正确的了。
7、几个著名有关图（构形）的着色方法
1890年赫渥特构造的H—图含有经过了顶点4和5两个围栏顶点的C—D环形链，从该“环”内、外的顶点2或顶点8交换A—B链，就可以转化成K—构形。
1921年埃雷拉构造的E—图含有经过了顶点1，2和3三个围栏顶点的A—B环形链，从该“环”内、外的顶点4和5或顶点6和7交换C—D链，也可以转化成K—构形。
1935年IRVING Kittell（欧文•基特尔）构造两个左右对称的图：一个是无环形链的H—构形，从两个方向进行转型时，都是四次转型后，就转化成了可以连续的移去两个同色的K—构形；另一个则是有C—D环形链的H—构形，在C—D链中有两个“环”，且两“环”是连通的，连通部分经过了围栏的4和5两个顶点，交换任一个C—D“环”中的A—B链，都可以使双环交叉链A—C和A—D中的一条断开，成为不连通链，图也就转化成了只含有一条连通链的K—构形。
2010年张彧典先生所构造的八大构形中的第八构形，则是一个不对称的无环形链的H—构形，逆时针转型一次就转化成一个有环形链的H—构形了，顺时针转型一次就是一个可以连续的移去两个同色的K—构形了。这八大构形中，实际上只有第二构形和第八构形两个构形是H—构形，而其他的第一构形，第三构形，第四构形，第五构形，第六构形和第七构形等六个构形都是可以连续的移去两个同色B的K—构形。

附：平面图的不可避免构形图表（见下页的图表）

雷  明
二○二○年六月二十七日于长安

注：此文已于二○二○年六月二十八日在《中国博士网》上发表过，网址是：
   
        此修改稿也于二○二○年七月六日在《中国博士网》上发表过，网址是：