构造一个不含有经过围栏顶点的环形链的双环交叉链的颜色冲突构形

雷明85639720

构造一个不含有经过围栏顶点的环形链的双环交叉链的颜色冲突构形
雷　　明
（二○二○年十月三十日）

下面我的作图完全是仿照敢峰先生构造终极图时的演绎方法的，最后在第八步转型后得到了一个不含有经过围栏顶点的双环交叉链的颜色冲突构形。
敢峰先生的转型演绎，实质上就是连续的进行一个方向（逆时针方向或顺时针方向）的转型交换。所谓转型交换就是把123—BAB型的5—轮构形从一个同色顶点1B进行了B—D链的交换后，构形就转化成了451—DCD型的5—轮构形；而从另一个同色顶点3B进行了B—C链的交换后，构形也就转化成了345—CDC型的5—轮构形了。转型后5—轮构形的峰点（即两个相同颜色顶点所夹的顶点）的颜色和位置都发生了变化。
敢峰先生构造他的终极图时是用了顺时针方向的转型绎演，我这里也用顺时针方向进行转型绎演。所谓转型绎演实质上就是从围栏顶点中交换了一个同色B的链并移去了一个同色B后，不是再去交换另一个同色B的链，直接移去两个同色B而解决问题，而是人为的再构造从另一个同色B到其对角顶点的连通链，使得不能连续的移去两个同色B，而图仍是一个有双环交叉链的颜色冲突构形。
首先给一个最基本的含有双环交叉链的图，这是一个可以连续的移去两个同色B的构形（如图1）。
第一步，如图2。其中（a）是对图1从右B（顺时针）交换了B—C链的图，（b）是对图1从左B开始构造了B—D连通链的图，是一个顺时针转型可以连续的移去两个同色C的可约构形。





第二步，如图3。其中（a）也是对图2（b）顺时针从一个同色C开始交换了C—A链的图，（b）是对图2（b）从另一个同色C开始构造了B—D连通链的图，也是一个顺时针转型可以连续的移去两个同色A的构形。以后各步的图都是这样的。（a）是交换了一个同色的图，（b）是构造了从另一个同色到其对角的连通链的图，无特殊情况不再说明。
第三步，如图4。

第四步，如图5。

第五步，如图6。

第六步，如图7。

第七步，如图8。

第八步，如图9。这时图9（b）已是一个按同方转型已不可连续的移去两个同色B的构形了，也是一个极大的平面图了，构造目标图的任务也就完成了。



图9（b）中虽含有双环交叉的A—C链和A—D链，也含有经过了围栏顶点的环形的C—D链（如图10中的加粗边），但该环形链却没有把双环交叉链的起始顶点A和交点A（如图10中的加大顶点）分隔在环的两侧。交换了环内、外的A—B链，图将仍然是一个含有双环交叉链的颜色冲突构形。而且会象敢峰先生研究终极图时那样，使用转型交换时会产生无穷的循环现象。图9（b）的构形将永远是一个不含有经过了围栏顶点的环形链的、但又含有双环交叉链的颜色冲突构形。所以我把该构形归入到不含有经过围栏顶点的环形链的一类构形。这一类构形的解决办法，不能用断链交换法，而只能用转型交换法。
现在我们接着继续用顺时针转型交换法研究该构形的可约性。顺时针转型第一次，去掉一个B后，生成了从另一个B到其对角顶点的连通的B—D 链（如图11，b中的加粗边），但又生成了经过围栏顶点的环形的A—B链（如图11，a中的加粗边），可以使用断链交换法解决。但为了对转型交换进行研究，下一步还是进行同方向的转型交换。



以后的第二次转型（如图12），第三次转型（如图13），第四次转（如图14）型都是同样的情况。既是含有双环交叉链的构形，又是含有经过了围栏顶点的环形链的构形。但第四次转型的结果却又是一个可以移去两个同色B的可约构形，因为进行了第五次转型后，从另一个B色顶点到其对角的D色顶点是没有连通的B—D链的（如图15（a）中不连通的加粗边）。再经过两次交换就可以连续的移去两个同色B给待着色顶点着上（如图15（b））。
如果对图9（b）进行逆时针方向转型，则一次转型就可以连续的移去两个同色B（如图16）。因为逆时针方向转型时，该构形本身就是一个可以连续的移去两个同色B的可约构形。


   




对图9（b）的构形无论是进行逆时针转型还是进行顺针转形，其转型次数都是不大于4的，也正好在我们已证明过的转型交换的转型最大次数是不会大于5的结论之内的。若对图9（b）的构形进行逆时针邻角链转型时，第三次转型后就是一个只有一条连通链的可约构形（如图17（d）中的加粗边），可给待着色顶点分别着上A或D（如图17（d）和图17（e））。





若对图9（b）的构形进行顺时针邻角链转型时，第一次次转型后就是一个只有一条连通链的可约构形（如图18（b）中的加粗边），可给待着色顶点分别着上D或C（如图18（c）和图18（d））。无论是逆时针转型还是顺时针转型，转型次数都没有超过我们已经证明过的邻角链的转型交换的最大交换次数是3的值。
把第八步得到的图9（b）的构形进行一下拓扑变化，就是如下图19。





敢峰先生的转型演绎得到的是终极图，反映的是有经过了围栏顶点的环形链的颜色冲突构形问题的解决办法；而我们这里转型演绎得到的却与其不同，得到的是一个反映无经过围栏顶点的环形链的颜色冲突构形问题的解决办法。只所以有这样的不同，也是必然的。因为敢峰先生在第二步的（a）图中构造双环交叉链时，走的是双环交叉圈的外圈，即我过去说过的“绕大圈子”，转型一开始就冲出了基础图中的A—C环和A—D环之外；而我却走了载径，是直接在基础图的A—C环和A—D环之内构造双环交叉链的。结果就产生了敢峰先生演绎中所增加的顶点都是处在基础图中A—C环和A—D环的外面，而我在演绎中所增加的顶点却都是处在基础图中A—C环和A—D环的内部。这就是最大的不同之点。
从对图9（b）的转型看，第一次转型到第三次转型（图11到图13）所得到的图中都有经过了围栏顶点的环形的A—B链，也都可以直接使用断链交换的方法去进行解决。对于图9（b）的图来说，转型次数是奇数时，环形链A—B是经过了两个围栏顶点的；转型次数是偶数时，环形链A—B是经过了三个围栏顶点的。A—B环形链这样的转化规律与敢峰先生的终极图正好是一样的。由此还可以看出，该构形比敢峰先生的终极图更具有代表性。终极图只能代表含有经过了围栏顶点的环形链（两种环形链都有）的构形，而该构形却除了能代表不含经过围栏顶点的环形链的构形外，还能代表含有经过了围栏顶点的环形链（两种环形链都有）的构形。从这个构形中，完全就可以看出各种有双环交叉链的颜色冲突问题应该如何去解决。

雷  明
二○二○年十月三十日于长安

注：此文已于二○二○年十一月一日在《中国博士网》上发表过，网址是：
http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=4288。这次于二○二一年七月三十一日进行修改，并改了标题。

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，