无环形链的染色困局也一定可解的机理

雷明85639720

无环形链的染色困局也一定可解的机理
雷  明
（二○一九年十月十九日）
（图发不上来，请到＜中国博士网＞中去看）

    在《有环形链的染色困局一定可解的机理》一文中我们已经分析了图1和图2中的有环形链的染色困局一定可解的原因：6C 与7D和5C与4D以及2A和8A分别是处在环形链A—B和C—D的两侧。交换了环形链内、外的任一条与环形链呈相反色链的链后，都可以使双环交叉链A—C和A—D断链，使图成为坎泊已证明过是可约的K—构形。

而图3和图4的无环形链的染色困局，就不可能做到这一点了。它只能通过转型交换，使图进行转型了。再看转型后的图是否转化成可约的坎泊构形。只要能在有限次的转型之内，解决问题即可。但这里就存在一个“有限次”的上界问题，多少次才算是有限次呢？有没有无穷的转型也不能使双环交叉链断链的图呢？有，这就是埃雷拉图（E—图），正是因为该图的无穷周期循环转型的循环周期是20，才帮了我们解决这一问题的大忙。
从转型次数是有限还是无限这一角度，把图可分成无穷周期循环转型的构形和有限转型的构形。我们现在所要解决的问题就是有限转型构形的转型有限性（上界）的问题。一个构形，只有在连续转型次数超过了两个周期后，仍是含有双环交叉链的染色困局时，才能确定其一定是无穷周期循环转型的构形；否则，在两个周期之内可以转化成能够连续的移去两个同色的双环交叉链构形时，该构形一定就是有限转型的构形。这个构形还要经过两次空出颜色的交换，一次交换后，使图成为只有一条连通链的、坎泊已证明过是可约的K—构形，二次交换即可空出颜色给待着色顶点。这就证明了任何非埃雷拉图类构形的转型次数一定是有限的。其上界限是40次转型，或者说是42次交换。
有人可能会问埃雷拉图如何解决呢？非常好解决。埃雷拉图中有一条环形的A—B链，是属于有环形链的构形，交换环形的A—B链内、外的任一条C—D链，都可以使问题得到解决。这就证明了任何非埃雷拉图类的构形都是可约的。无环形链的构形也是非埃雷拉图类构形中的一类，所以无环形链的构形也就是可约的了。现在，所有的染色困局构形都已经是可约的了，当然四色问题也就得到了证明，四色猜测是正确的。

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

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