无经过围栏顶点环形链的构形的最大转型次数的再研究

雷明85639720

无经过围栏顶点环形链的构形的最大转型次数的再研究
雷  明
（二○二○年十一月二十一日）

1、敢峰先生的终极图与我的基本模型的比较的补充
一个构形能不能使用断链交换，主要看关键顶点是否是被环形链分隔在环的两侧。
敢峰的终极图及其各次转型后的图中，关键顶点都是被环形链分隔在环的两侧的（如图1到图6），都是属于有经过围栏顶点的环形链的构形，所以都是都可以用断链交换法的。尽管以后的转型是无穷循环的，但因终极图本身就是属于有经过了围栏顶点的环形链的构形，所以终极图也是可约的。对终极图进行逆向转型也有同样的结果。


而我的基本模型本身就是无经过围栏顶点的环形链的构形，本身的关键顶点就是相连通的，尽管有一条经过了两个围栏顶点的环形链C—D，只是属于局部环形链（后面还要专门进行介定），而且就是使用了断链交换法，也解决不了问题（如图7）。但经三次连续转型后的图各个图都是有经过了围栏顶点的A—B环形链的构形，且把关键顶点都隔在了环形链的两侧（如图8到图10），都可以使用断链交换法解决。




第四次转型后的图中虽有经过了两个围栏顶点的A—B环形链，但其并没有把关键顶点分隔为不连通的两部分，而是在一条链上（如图11），构形属于无经过围栏顶点的环形链的一类。所以，不能使用断链交换法，而只能使用转型交换法了。进行第五次转型的结果却是转化成了只有一条连通链的可约构形（如图12）。对基本模型进行逆向转型时，一次转型就可以转化成只有一条连通链的可约构形（如图13）。






四次转型后的图，虽是无经过围栏顶点的环形链的构形，但又是一个有局部环形链A—B的构形，在环内交换C—D链，就转化成为只有一条连通链的可约构形（如图14）。
图7到图11的5个有双环交叉链的构形中，任何一个构形，无论向那个方向进行转型交换，一定都是在5次（包括5次）交换之内解决问题的，最后都可得到图12和图13的结果。




2、无经过围栏顶点的环形链的构形最大转型次数的研究
在研究四色问题中，无双环交叉链的构形，有双环交叉链又能移去两个同色的构形，有双环交叉链不能移去两个同色的、但又有经过了围栏顶点的环形链的构形，都可以用坎泊的颜色交换技术进行解决。唯有双环交叉链不能移去两个同色、又无经过围栏顶点的环形链的构形，虽也可以用仍属于坎泊的颜色交换技术的转形交换法解决，但转型的次数最大是多少若不能解决，还等于四色问题未能得到解决。
对于无经过围栏顶点的环形链的构形来说，解决的方法虽然很多，但都是有一定条件的，唯有A—B链和C—D链各都只是一条、且不能移去两个同色B的构形，才是一个标准的这一类构形，是一个代表。这类构形虽然以不同的方向进行一次转型后，都可得到一个有经过了围栏顶点的环形链的构形，或者得到一个可以连续的移去两个同色的可约构形，但为了寻找该类构形的最大转型次数，我们还是放弃直接用断链交换的办法，或连续的移去两个同色的办法进行解决，而是继续进行同方向的转型，以探求最大的转型次数。其方法是：
在某次转形后，即就是得到了可以解决的构形，也要再人为的构造具有双环交叉链的构形，直到在平面图范围内再不能构造双环交叉链的构形为止。看其最大的转型次数是多少。


转型最开始的起始图，是一个移去了任何一个同色B后，又会再生成从另一个同色B到其对角线的连通链的构形（如图15，0）。对该图进行顺时针转型交换的结果如图15，1到图15，7；进行逆时针转型交换的结果如图16，1到图16，7。均在第六次转型后，就可转化为一个只有一条连通链的可约构形了（也就是说五次交换的结果也就是一个可以连续的移去两个同色的构形），总共需要7次交换就可以解决问题（图中从构形的峰点开始引出的加粗虚线边是人为构造的连通链中的边；另一条加粗虚线边是已经交换过的链）。














转型开始时是非极大图，到最后问题得到解决时也是非极大图。把最后的结果连同增加的顶点所着的颜色，变成转型开始时的图（仍是非极大图）时，同方向的转型最后仍得到同样的结果；但逆向转型时，在第二次转型后就得到了只有一条连通链的可约构形。再增加边变成极大图后，同方向的转型最后也得到同样的对果；逆向转型时，也是在第二次转型后就得到了只有一条连通链的可约构形。若把两种方向进行连续转型交换中增加的顶点（包括颜色）和边分别都增加到原始图中去，并在图中再增加边，使图变成极大图后，再分别施行两个方向的转型交换时，无论是那个方向的转型，则最多转型两次，就转化成了只有一条连通链的可约构形了。这些现象都说明，极大图的转型交换次数一定是比非极大图的转型交换次数要少的。
以上是从一个具体的、非极大图的且不能移去两个同色B的图进行转型交换，并在转型过程中人为的构造双环交叉链，到最后解决了问题后所得出的结论；现在，再看一下从一个可以移去两个同色的、只有双环交叉链的最简单的构形进行转型交换，也在转型过程中人为的构造双环交叉链，到最后解决了问题后所得的结论是什么。
我们仿照敢峰先生的转型演绎的方法，从一个只有双环交叉链、但可以连续的移去两个同色的最简单的构形出发，在移去了一个同色B后，再构造从另一个同色B到其对角的连通链，最后得到了前面图7的无经过围栏顶点的环形链的构形。该构形是一个具体的极大平面图，再进行五次转型后就得到了一个只有一条连通链的可约构形（如图7到图12），从图7到图11的这五个构形，都是具有双环交叉链的构形（中间三个还都是具有经过了围栏顶点的环形链的构形），任何一个构形分别向两个方向转型，都不会超过5次都会转化成图12和图13的只有一条连通链的可约构形。
从以上两种人为构造双环交叉链的结果中，也可以看出极大图的转型次数是比非极大图的转型次数是要少的。可以得出，极大图的最大转型交数是不大于5的，刚好在要出现循环转型时，转型就结束了；而非极大图的最大转型次数是不大于6的，在第5次转型后，也说明刚好在要出现循环转型时，图也就转化成了可以连续的移去两个同色的可约构形。
3、为什么要构造极大图的颜色冲突模型
敢峰先生人为的构造了一个是极大图的、反映了有经过了围栏顶点的环形链的终极左图，我也仿敢峰先生的办法构造了一个是极大图的、反映了无经过围栏顶点的环形链的基本模型。为什么还要这么做呢？因为在证明各种不可免构形的可约性时，用的都是非极大图的、非具体图的构形。在极大图中是否存在着与证明各种不可免构形时的那些种不可免的构形相对应的极大图的基本模形呢？就得要在极大图中找到它。因为有了这些对应的极大图的基本模型，就可以在其基础上构造出任意顶点数的极大图模型。基本模型是可约的，当然在其基础上构造的任意顶点数的极大图模型也一定就是可约的了。
构造的原理是这样的：把基本模型中的基本链加长时，因为与该链上的顶点相邻的顶点一定都是其相反链上的顶点，所以在这条链的某两个顶点间增加两个同链颜色的顶点时，链两侧可与其相邻的顶点仍是其相反链上的顶点，可以用边相连，得出的图仍是极大图；在非基本链以外的任一个三边形面中，增加一个顶点，一定是还有一种颜色可着的；在非基本链以外的边上增加一个顶点和两条边，得到一个4度的顶点，根据相反链互相不能穿过的理论，该顶点也一定是有颜色可着的；这样就可得到任意顶点数的极大图模型了，基本模型是可约的，那么任意顶点数的极大图模型也就是可约的了。
任意顶点数的极大图模型是可约的了，极大平面图的四色猜测也就是正确的了。同样的地图四色猜测也就是正确的了。由极大平面图经去顶或减边所得到的任意平面图的四色猜测也就是正确的了。四色猜测是正确的。四色足矣！
4、有环形链和无环形链的构形的介定
其原理仍是相反链互相不能穿过的理论。先看几个有双环交叉链的图并且不能连续的移去两个同色的构形（如图17到图20），这些构形中都有双环交叉链A—C和A—D，但A—B链和C—D链的分布却不相同，就构成了不同类型的有双环交叉链的构形。可以看出，图中的关链顶点是1B—2A—3B，8A和4D—5C，6C—7D八个顶点。这八个关键顶点中有六个顶点是围栏顶点和双环交叉链的交叉顶点，只有顶点6C—7D，既非围栏顶点又交叉顶点，而是双环交叉链上两链唯一直接相邻的两个顶点（若顶点6C和7D不直接相邻，图将成为可以连续的移去两个同色B的可约构形，读者可自已画一画）。还可以看出，八个关键顶点中，只要有一个顶点的颜色发生了变化，构形就转化成了无双环交叉链的构形。




鉴于以上原因，当只有经过顶点1B—2A—3B……8A……1B的A—B链呈环形时（如图17），才有可能把4D—5C和6C—7D分隔成不连通的两部分，也才有可改变4D—5C或者6C—7D的颜色，使双环交叉的两链均变得不连通，构形转化为无双环交叉链的构形；同样的，也只有经过顶点5C—4D……6C—7D……5C的C—D链呈环形时（如图18），也才有可能把1B—2A—3B和8A分隔成不连通的两部分，也才有可能改变1B—2A—3B或8A的颜色，使双环交叉的两链也就变得不连通，构形转化为无双环交叉链的构形。以上的两种情况就是有经过了围栏顶点的环形链的构形。若以上的两种情况均不存在时（如图19和图20），则就是无经过围栏顶点的环形链的构形。可见。属于有以过了围栏顶点的环形链的构形有两个必要的条件：一是要有经过围栏顶点的环形链，二是该环形链把属于其相反链的关键顶点分隔在环的两侧，互不连通。
敢峰先生的终极图（见图1）经过了围栏顶点的环形链A—B，该链把属于其相反链C—D的关键顶点4D—5C和6C—7D分隔在了环的两侧，互不连通，符合条件，是有经过了围栏顶点的环形链的构形，可以用断链交换法解决问题。终极图的各次转型所得结果中，也有这样的特征，所以都是属于有经过了围栏顶点的环形链的构形，也都可以用断链交换法解决问题。虽然终极图中也含有环形的C—D链，也把属于其相反链A—B的关键顶点1B—2A—3B和8A分隔在了环的两侧，互不连通，但该链却不经过围栏顶点，所以不能认为有环形的C—D链，就说终极图是有C—D环形链的构形。的确，在环形的C—D环内、外交换A—B链是不起作用的，虽然原有的双环交叉链没有了，但又产生了新的双环交叉链。
而我的基本模型（见图7）和基本模型经四次转型后得到的图（见图11），虽有经过了围栏顶点的环形链，但都没有把属于其相反链的关键顶点分隔在环的两侧，互不连通，而不能算作有经过了围栏顶点的环形链的构形。有确，图7在C—D环内、外交换了A—B链后，仍是一个有双环交叉链的构形；而图11却因为又是属于有局部环形链的构形，所以在A—B环的内、外进行了其相反链C—D链的交换后，只能使一条双环交叉链断开，成为一个仍有一条环形链的可约构形。张彧典先生的第八构形就属于有局部环形链的构形，也可以这样解决问题。而我的基本模型一到三次转型交换所得到的各图中，均有经过了围栏顶点、且把其相反链的关键顶点分隔在了环的两侧，所以是有经过了围栏顶点的环形链的构形，可以也用断链交换法进行解决。

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

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

雷明85639720

请给出图来！

雷明85639720

请你给出图来！你要我着色，却不把具体图给出来，怎么着呢？

雷明85639720

你给不出来图，把你证明“3个相邻的区域被n个区域包围的图”的方法拿出来也可以呀。

雷明85639720

D中的n个区域分中间三个区域的相邻关系你也没有说明呀？就是因为这个我才一次次的问你的。

雷明85639720

“如果说明了，D区不能函盖n个区域了”，这句话不明白是什么意思？你要我着色，不给具体的有相邻关系的图我怎么着呢？我提一个与你的问题相同的问题，你是否也可以给我证明一下n个区域包围两个区域的着法呢？你能证明这个，我看明白了你的意思后，我也就一定能给你提出的问题有一个让你满意的回答。

朱明君

雷明85639720 发表于 2020-11-22 10:26
请给出图来！

只需两种着法，就涵盖了D区n个区域

雷明85639720

n虽有奇偶之分，但不能确定中间三个区域分别与这n个区域的相邻关系，也不能确这这n个区域之间的相邻关系呀？都弄不明白各区域的相邻关系，不是具体的图，怎么着色呢？请你着一下吧！

朱明君

雷老师只能一张一张着色，不知归纳着色

雷明85639720

请你给出你的归纳着色方法，把你的图着一下色！