5—轮构形4—着色时的最大转型次数

雷明85639720

5—轮构形4—着色时的最大转型次数
雷  明
（二○二一年十月十九日）

1、5—轮构形能否4—着色是解决四色问题的关键：
极大平面图4—着色时，剩下的最后一个顶点如果是一个5—度顶点且与其相邻的5个顶点已占用完了4种颜色时，这就是一个发生了“颜色冲突”的“5—轮构形”。在5—轮构形中的5个“围栏顶点”（即与5—轮中心顶点相邻的顶点）占用了A、B、C、D四种颜色的情况下，只可能有一种颜色是用了两次的。若把两个相同颜色的顶点中间的那个顶点叫构形的“峰点顶点”时，这样，就可以把含有从构形的峰点顶点开始的、中途又不相交叉的两条连通的对角链或者即就是该两条链在中途相交叉了、但却又能够连续的移去两个同色的构形，叫做“坎泊构形”（即K—构形，因为是坎泊在1879年已用可空出颜色的颜色交换技术已经证明了这些构形都是“可约”的，即是4—可着色的）；而把含有从构形的峰点顶点开始的、中途又有相交叉情况的两条连通的对角链（即所谓的“双环交叉链”）的、且又不能够连续的移去两个同色的构形，叫做“赫渥特构形”（即H—构形，因为这种构形是赫渥特在1890年发现的）。这种H—构形，直到现在已有130多年了，还没有被证明是否是可约的。所以说，现在证明四色问题，关键的问题就是要解决发生了颜色冲突的5—轮构形的“可约性”的问题。
2、5—轮构形4—着色时的各种方法简述：
在H—构形中，含有经过了关键顶点（即是指5—轮构形中的峰点顶点，两条双环交叉链的交叉顶点，以及两条双环交叉链的两个末端顶点，共4个）的环形链的一类构形（如图1，1和图1，2），可以用能够“隔断”双环交叉链的“断链交换法”使构形转化成K—构形而可约；而不含有经过了关键顶点的环形链的一类构形（如图1，3和图1，4），则用连续的“转型交换法”，使构形连续的进行“转型”，而转化成虽然仍含有双环交叉链，但是可以连续的移去两个同色的可约的K—构形而可约，或者直接转化成只有一条连通链的可约的K—构形而可约。


以上的证明方法也都很简单，这里就不再多说了，请参考本人的有关文章。这里主要说的是正象本文标题所示的“5—轮构形4—着色时的最大转型次数”。所谓5—轮构形的类型，是指对5—轮构形的一种表示方法，如把两个同色是B而峰点是A的5—轮构形表示成BAB型（或叫双B夹A型）等等，而“转型”则是把构形的类型转化成别的类型的过程，如把BAB型的构形转化成ABA型的构形等等。
从图1，3中还可以看出，若把图中左侧的A—B链中的一个B色顶点改成D色时，构形就直接转化成了一个含有经过了关键顶点4D和5C的环形链C—D的构形了，也就可以用断链交换法进行解决了。而从图1，4中也可以看出，若把图中右侧的C—D链中的一个C色顶点改成B色时，构形也就直接转化成了一个含有经过了两链的起始顶点A和交叉顶点A的两个关键顶点的环形链A—B的构形了，同样也可以用断链交换法进行解决了。这就为把不含有经过了关键顶点的环形链的构形直接转化成含有经过了关键顶点的环形链的构形创造了条件。这样的可以改变颜色的顶点是一定存在的，就只怕粗心者在复杂一点的图中，可能一下子还找不到。不过找不到也不要紧，还有转型交换法也是可以解决问题的。
3、5—轮构形4—着色时的最大转型次数：
转型的最大次数的确定是这样的：如果转型后得到的构形是可约的，我们就人为的在平面图范围内再构造顶点和边，使其转化成既具有双环交叉链、但却不能连续的移去两个同色的构形，再继续转型，一直到在平面图范围内不能再构造出具有双环交叉链的构形为止，这时，就可以得到连续转型的最大转型次数。
从上一节的分析中可以看出，只有不含有经过了关键顶点的环形链的构形在4—着色时才需要转型。转型分为对角链交换转型（简称对角转型）和邻角链交换转型（简称邻角转型）两种；两种转型各又分为逆时针方向转型（简称逆时针转型）和顺时针方向转型（简称顺时针转型）两种。
图1，3和图1，4的两个不含有环形链的构形实际上是相同的，只是一个顶点稍多了几个，一个顶点少了几个罢了，转型后的结果都是相同的（读者们可以自已作一作）。我们这里就只就顶点数少的图1，3进行示范操作。
3、1  对角链交换转型：
这一转型交换的方法是：从两个同色顶点中的一个顶点开始交换与其对角顶点的颜色构成的色链，看其是否新生成从另一个同色顶点到其对角顶点的连通链。若不能生成时，就在平面图范围内再构造这样的连通链，直到不能构造为止。其转型交换的次数就是最大的转型次数。图中从围栏顶点引出的加粗边是转型交换的边，虚线边是从另一个同色顶点到其对角的连通链，其中加粗的虚线边是人为增加的边。
3、1、1  逆时针对角转型：如图2。

在第5次转型后，就不可能再构造连通的B—C链了，因为有一条连通的A—D链将其阻隔了（如图2，5中上边的加粗边）。这时，图2，4的第4次对角逆转后的构形就是一个可以连续的移去两个同色的可约的K—构形了，而第5次对角逆转后的构形就是一个只有一条连通链的可约的K—构形了。这时，如果再继续进行同方向的转型，从图2，5中可以看出，交换的是一条经过了围栏两个相邻顶点连通链D—A了，交换后的图仍是一个H—构形，只是图中所有的A色顶点与所有的D色顶点互换了一下颜色而已。


3、1、2  顺时针对角转型：如图3。
顺转一次转型后，就是一个含有经过了关键顶点的环形链的构形（如图3，1中加粗的环形的A—B链），可以改用断链交换法提前结束转型。但为了寻求转型的最大次数，还是要继续的进行转型的。同样，也是在第5次转型后，就不可能再构造连通的B—D链了，因为有一条连通的A—C链将其阻隔了（如图3，5中上边的加粗边）。这时，图3，4的第四次对角逆转后的构形就是一个可以连续的移去两个同色的构形了，而第5次对角逆转后的构形就是一个只有一条连通链的可约的K—构形了。与逆时针对角转型的结果是相同的。

   

两个方向的对角链转型的结果都是相同的，都是在第4次转型时形成了BAB型的构形，构形类型返回到最初始状态。也都是第5次转型时形成了只有一条连通链的可约的K—构形，正好每个顶点分别做了一次峰点顶点。也都是在这时都不可能再继续进行转型了。
3、2  邻角链交换转型：
这一转型交换的方法是：从双环交叉链中的任一条的末端顶点开始，交换与其相邻的两个同色顶点中的一个顶点的颜色构成的色链，看其是否新生成从另一条连通链的末端顶点到其对角顶点（非峰点顶点的对角顶点）的连通链。若不能生成时，就在平面图范围内再构造这样的连通链，直到不能构造为止。其转型交换的次数就是最大的转型数。图中经过了围栏两个相邻顶点的加粗边是转型交换的链，虚线边是从另一条连通链的末端顶点到其对角顶点（非峰点顶点）的连通链，其中加粗的虚线边是人为增加的边。
邻角链转型交换的是包括围栏上两个顶点（其中一个就是两个同色的B色顶点）在内的链，两个同色B永远是处在围栏顶点上的，所以邻角转型的产物总是双B夹×的构形，两个同色顶点总是B。
3、2、1  逆时针邻角转型：如图4。
这种转型一次转型就可转化成只有一条连通链的可约的K—构形。

3、2、2  顺时针邻角转型：如图5。
在第6次转型后，就不可能再构造连通的A—D链了，因为有一条连通的B—C链将其阻隔了（如图5，6中的双线边）。这时，图5，6的第6次邻角逆转后的构形就是一个只有一条连通链的可约的K—构形了。如果再继续的转型下去，交换的也就是一条连通的链了，相当于把图中所有的B色顶点和所有的C色顶点互换了一下所着的颜色，构形的本质并没有改变。

   
由于不含有经过了关键顶点的环形链的构形，相对于含有经过了关点的环形链的构形来说是极不对称的，所以邻角链两个方向的转型的结果是大不相同的。逆时针方向转型一次就结束了，而顺时针方向却转型了6次，但二者转型的结果却都是只有一条连通链的、不能连续的移去两个同色B的构形。顺时针转型中，除了第6 次转型的结果外，其它次转型的产物也都是既含有双环交叉链，且又可以连续的移去两个同色B的可约的K—构形。


从以上着色实践上看，5—轮构形的最大转型次数最大是6次（其中邻角逆转1次比较特殊外，对角转型两个方向均为5次，邻角顺转6次），就可以转化成只有一条连通链的可约的K—构形，并且在结束转型前，每一个围栏顶点都做了一次峰点顶点。
4、 5—轮构形最大转型次数有限性的理论证明：
4、1  5—轮构形的转型是周期性的：
发生周期性变化的是构形的类型和构形峰点的位置，以及构形的类型和峰点位置同时发生变化的大周期。
4、1、1  对角转型的循环周期：
对角逆转型时，构形类型是在BAB—DCD—ABA—CDC—BAB四种类型之间按顺序进行循环，周期是4；构形峰点位置是在图1，3中顶点2—5—3—1—4—2五个顶点间按顺序进行循环，周期是5。构形的类型及峰点位置同时都返回到初始位置时，需要进行4×5＝20次转型。
对角顺转型时，构形类型是在BAB—CDC—ABA—DCD—BAB四种类型之间按顺序进行循环，周期也是4；构形峰点位置是在图1，3中顶点2—4—1—3—5—2五个顶点间按顺序进行循环，周期也是5。构形的类型及峰点位置同时都返回到初始位置时，也需要进行4×5＝20次转型。
三种循环周期，即所谓的小、中、大三个循环，周而复始，总不会停止，无穷的进行下去。
4、1、2  邻角转型的循环周期：
邻角逆转型时，构形类型是在BAB—BCB—BDB—BAB（—BCB—BDB—BAB）三种类型之间按顺序进行循环，周期是3；构形峰点位置是在图1，3中顶点2—5—3—1—4—2五个顶点间按顺序进行循环，周期是5。构形的类型及峰点位置同时都返回到初始位置时，需要进行3×5＝15次转型。
邻角顺转型时，构形类型是在BAB—BDB—BCB—BAB（—BDB—BCB—BAB四种类型之间按顺序进行循环，周期也是4；构形峰点位置是在图1，3中顶点2—4—1—3—5—2五个顶点间按顺序进行循环，周期也是5。构形的类型及峰点位置同时都返回到初始位置时，也需要进行3×5＝15次转型。
三种循环周期，也即所谓的小、中、大三个循环，周而复始，总不会停止，无穷的进行下去。
4、2  5—轮构形的转型次数是有限的：

1921年埃雷拉所构造的埃雷拉E—图（如图6）的转型交换次数是无穷的，永远也停止不了。有人可能会问，不含有经过了关键顶点的环形链的构形在转型交换时，会不会产生象埃雷拉E—图那样的无限循环转型呢？我的回答是“不会的”！
我们看一看，我们这里研究的不含有经过了关键顶点的环形链的构形，是一个极不对称的构形；而埃雷拉E—图却是一个对称性非常强的，含有经过了关键顶点的环形的A—B链的构形。我们这里的构形根本就没有产生无穷循环周期转型的条件。并且，在上面一节中我们已经从着色实践中证明了这类构形的确是不会产生循环转型的，其最大的转型交换次数是6，而不会再大。此时，构形已经转化成了一个只有一条连通链的可约的K—构形了。
这个6次转型，既保证了对角转型时，构形类型转化完成了一个周期4次交换，也保证了构形峰点位置转化完成了一个周期5次交换；也既保存证了邻角转型时，构形类型转化完成了两个周期2×3＝6次交换，也保证了构形峰点位置转化完成了一个周期5 次交换。
5、  四色猜测是正确的：
从坎泊至今，经过了漫长的142年，终于证明了平面图的所有不可避免的构形都是可约的，这就意味着任意的平面图一定都是可4—着色的了。那么四色猜测也就是正确的了。四色猜测的提出者——法朗西斯的在天之灵，也会得到安慰了。

雷  明
二○二一年十月十九日于长安

雷明85639720

，，，，，，，，