转型交换最大转型次数的确定

雷明85639720

转型交换最大转型次数的确定
雷  明
（二○二一年元月十七日）

在有双环交叉链的构形中，有经过了关键顶点的环形链的构形的可约性问题已经用断链交换法解决了；而无经过关键顶点的环形链的构形的可约性问题虽可用转型交换法解决，但最大的转型次数是多少，一定要有一个明确的“界值”，否则也就成了无数次转型也空不出颜色的构形了。这一问题解决不了，四色猜测也就还是不能证明是正确的。
1、转型的次数一定是有限次的
埃雷拉图（E—图）进行转型交换时，是一个既以4次转型为一个小周期的构形类型的无穷循环的构形，又是一个以20次转型为一个大周期的构形着色状态的无穷循环的构形，且是由5次小循环构成了一个大循环。小循环的周期是4，说明有4种颜色，每种颜色作一次5—轮构形的峰点顶点，4次转型就是一个循环周期；大循环的周期是20，说明某种颜色作峰点时，需要每个顶点作一次这种颜色的峰点，构形各顶点才能回到转型前最初始时各顶点的着色状态。共计需要4×5＝20次转形（欧文1935年在《对已部分４染色地图的一组操作》一文中指出：1921年“Errera提出了一个地图。在这一地图上重复进行20次α操作，能使染色返回到原来的染色。在染色的每一步，地图都还是处于染色困局。”）（请注意，欧文在这里所说的“α操作”就是我这里所说的一种“转型交换”，所谓的“染色困局”就是指我们所说的“颜色冲突”）。4×5＝20，式中的4是已使用过的颜色数，5是5—轮构形的围栏顶点数，20是4和5的最小公倍数。
这样看来，E—图用转型交换是无法空出颜色给待着色顶点了。但E—图中却有经过了关键顶点的环形链，属于有经过了关键顶点的环形链的构形，可以用断型交换法进行解决。欧文在1935年就是用这种方法解决了埃雷拉E—图的4—着色问题的。
现在，在我们已知的构形中，在E—图以外，也有转型次数是以4次转型为一个小周期的构形类型的循环，但却没有出现以20次转型为一个大周期的循环现象的构形，经有限次小循环后就结束了转型。例如我和张彧典先生构造的转型次数大于20次的构形就是这样。这些构形的确是在第20次转型后，得到的图中不是所有顶点都回到转型前的初始着色状态的图，而只是围栏顶点的着色返回到了转型前的初始状态。
对于别的同类型构形，是不是都不会出现大循环，而只有有限次的大于20次的小循环呢？还是就不可能出现大循环而只有小循环的无穷循环呢？或是大循环的周期大于20，或是20的倍数呢？是不是象欧文在《对已部分4染色地图的一组操作》一文中所说的那样：“α操作的周期至少为二十，因为它可以为待染色区域的五个邻域产生二十种不同的颜色排列方式。应该注意到，在一些地图中，α操作的周期可能为四十、六十等。”我们就不得而知，也不可能再构造出各种情况下的各种构形。但我们却发现所有这些转型次数大于20次的构形中，与E—图一样，也都含有经过了关键顶点的环形链，都可以用断链交换法进行解决。
而无经过关键顶点的环形链的构形中，是否也存在有无穷循环（小循环或大循环）的构形呢？可以说，不会有的。因为这种构形中根本就不存在以上两种构形中共同都有的、可以产生无穷循环转型的条件——存在有经过了关键顶点的环形链。这就决定了这种构形的转型次数一定是“有限的”。
2、最大转型次数从理论上进行的确定
在解决构形可约性的过程中，我们发现无经过关键顶点的环形链的构形在转型的过程中，是可以转化成有经过了关键顶点的环形链的构形的，可以再改用断链交换法解决问题，提前结束转型。这也就为我们研究解决这类构形的可约性，提供了捷径。
既然这种构形的转型次数一定是有限的，既不会有周期为20的大的无穷循环，也不会有周期为4的小的无穷循环，那么它一定就要在第二个小循环周期8次转型之内解决问题，不再产生循环现象。4次转型完成一个小周期循环，再进行一次或最多三次转型后，就必须转化成一个可以连续的移去两个同色的可约构形。再交换两次就可以连续的移去两个同色，空出来给待着色顶点着上。
这也就是说最多必须在第7次转型之后，图就应是一个可以连续的移去两个同色的可约构形。再交换两次，就可以连续的移去两个同色。问题就得到了解决。即在第8次（并不大于8次）转型后，图就是只有一条连通链的可约构形形了。最大的转型次数是8次，最大的交换次数是9次。
这也就是张彧典先生认为的、在他所构造的八大构形之外，再没有别的构形的原因。然而张先生却没有看到他所构造的八个构形中，除了第二构形是一个最基本的、也是最小的、只有四条边的、经过了关键顶点的环形链的构形外，其他的构形都是无经过关键顶点的环形链的构形，而且全都是可以连续的移去两个同色B的构形，是不能代表所有的构形的，至少其中就缺少有经过了关键顶点的环形链的构形。
后来我与张先生虽在第八构形的基础上，构造出了需要大于9次交换的构形，但这些构形本身却是有经过了关键顶点的环形链的构形，与张先生的八个构形的结构是有所不同的，都是可以直接用断链交换法解决问题的。在所构造的大于9次交换的图中，虽然也有些也是无经过关键顶点的环形链的构形，但这些图在进行了有限次转型之内，都是可以转化成有经过了关键顶点的环形链的构形，也可直接改用断链交换法解决，提前结束转型。张先生的第八构形就是这样，在有限的8次转型之内已有多次转化成了有经过了关键顶点的环形链的构形。
这一类构形在转型时，一定要看交换了一个同色顶点与其对角顶点的颜色构成的色链后，会不会新生成从另一个同色顶点到其对角顶点的连通链：如果不会，则是可以连续的移去两个同色的构形，问题得到解决；否则就是不可连续的移去两个同色的构形，仍是含有双环交叉链的构形。对于这个新生成的含有双环交叉链的构形，再看是否有经过了关键顶点的环形链：如果有，则问题也就可以解决了；如果没有，就得再继续的进行同方向的连续转型，再进行同样的分析，直到能得到可连续的移去两个同色的构形，或者有经过了关键顶点的环形链的构形为止。最大的转型次数是不会大于8次的。
一个有双环交叉链的构形，看其是否是能连续的移去两个同色的构形，其判断的条件是：两个同色的顶点B中，如果有一个顶点到双环交叉链的交叉顶点A的链是一条单边链时，则从该顶点交换了与其对角顶点的颜色构成的对角链后，一定不会新生成从另一个同色顶点到其对角顶点的连通链，该构形就一定是一个可以连续的移去两个同色的构形可约构形。
3、最大转型次数的验证
为了验证这个推理是否是正确的，是否是符合逻辑的，我们进行以下的几种操作：
3、1  用非极大图的构形进行验证
作一个不能连续的移去两个同色的标准的有双环交叉链的5—轮构形，进行不同方向的连续转型交换。当不能新生成从另一个同色顶点到其对角顶点的连通链时，应该说问题就已经解决，可以连续的移去另一个同色。但我们有意的不去这样做，而是在平面图的许可范围内，增加顶点或边，人为的构造从另一个同色顶点到其对角顶点的连通链，使图仍是一个不可连续的移去两个同色的构形，再继续的进行转型交换。如果在某次转型后，再不可能人为的构造从另一个同色顶点到其对角顶点的连通链时，这时的转型次数就是最大的转型次数，看看与上面的逻辑推理所得出的结论是否一致。
图0是一个标准的无经过关键顶点的环形链的构形。以下的图1到图13，都是对图0的逆时针连续转型与人为的构造连通链，以及最后解决问题的全过程。第一次转型后的图中，因原来的构形中就已存在从另一个顶点到其对角顶点的连通链的，所以是不需要人为的再构造连通链的。图中不连通的加粗实线边是转型交换过的链；连通的加粗边是人为构造的连通链，其中虚线部分是新增加的边。














作图的结果只是在第6次转型后，图就转化成了一个可以连续的移去两个同色的构形。符合逻辑推理得出的转型次数不大于8的结论。若再对图0进行顺时针转型时，也会得到同样的结论。如下一组图。














3、2  用极大图的构形进行验证
首先我们采用敢峰先生的顺时针转型演绎法构造一个具体的无经过关键顶点的环形链的极大图5—轮构形（如图16）。构图过程图下一组图。对所构造的图16的转型交换如后另一组图。




















图16中似乎是有经过了关键顶点的环形链C—D，但该C—D环并没有把位于其相反链A—B上的关键顶点——双环交叉链A—C和A—D的共同起始顶点和交叉顶点（如图中的加大顶点）分隔在C—D环的两侧（见图17），应属于无经过关键顶点的环形链的构形。现在对图17的这个构形进行转形交换，看其最大的转型次数是几。
逆时针转型时，一次就成了只有一条连通链的可约构形（如图18），可见该构形是一个可以连续的移去两个同色B的可约构形，再交换一次即可空出B给待着色顶点（如图19）。符合逻辑推理得出的结论。






继续顺时针转型时，可以连续的转型4次（也符合逻辑推理得出的结论）就转化成了一个可以连续的移去两个同色B的可约构形（如图23），再转形一次就成了只有一条连通链的可约构形（如图24），再交换一次就空出了B给待着色顶点着上（如图25）。同时顺时针转型时，每次转型所得的图又都是有经过了关键顶点的环形链的构形（如图20、图21、图22、和图23），交换环形链内、外任一侧的与环形链呈相反链的色链，就都可以转化成无双环交叉链的可约构形（图读者可以自已来作一下）。这也就证明了前面所说的“这些图在进行了有限次转型之内，都是可以转化成有经过了关键顶点的环形链的构形，也可直接改用断链交换法解决，提前结束转型。”的结论是正确的。
因为图17虽含有双环交叉链，但其本身却是一个可以连续的移去两个同色B的可约构形，现在我们再将其中的一个B色顶点与双环交叉链的交叉顶点A间的A—B单边链变成多边的A—B链，图就变成了不可连续的移去两个同色B的有双环交叉链的构形（如图26），再看看这个构形的转型次数的多少。




一次逆时针转型后就是一个可以连续的移去两个同色的可约构形（如图27），再进行一次转型后就是只有一条连通链的可约构形了（如图28），再交换一次即可移去两个同色，把空出了的两个同色的颜色给待着色顶点着上即可（如图29）。逆时针转型的转型次数也是符合逻辑推理所得出的结论的。






顺时针转型时，4次转型后得图33，是一个可以连续的移去两个同色B的可约构形，再经一次转型后就是只有一条连通链的可约构形（如图34），再交换一次，就可以移去两个同色B给待着色顶点着上（如图35）。而且四次转型中，每次转型后的图中都含有经过了关键顶点的环形链，可以改用断链交换法，提前结束转型。顺时针转型的转型次数也是符合逻辑推理得出的结论的。且在四次转型中，每次转型后的图中都含有经过了关键顶点的环形链，可以改用断链交换法，提前结束转型，也就再一次证明了我们前面所说的结论是正确的。
以上用敢峰先生的转型演绎法构造的无经过关键顶点的环形链的极大图构形是用顺时针方向转型而得到的，同样的采用逆时针方向转型也能得到一个与该图是左右轴对称的另一个无经过关键顶点的环形链的极大图构形。其解决的方法和过程也与上图是相同的，最大的转型次数也是相同的。
3、3  用具体的着色实例进行验证
①  1935年欧文给出的那个无经过关键顶点的环形链的构形，由于其中的A—B链和C—D都是对于构形的峰点A与两个底角顶点C和D（即两条双环交叉链的末端顶点）的中点的连线呈对称状态的，所以无论从那个方向转型时，都是4次转形就可以得到可以连续的移去两个同色的可约构形，再一次转形就是一个只有一条连通链的可约构形，再交换一次就可空出颜色来。同时无论那个方向的转型，第3次转型后都是有经过了关键顶点的环形链的构形，也都可以用断链交换法提前结束转型。转型的次数也都是符合逻辑推理所得出的结论的。
②  张彧典先生的Z—构形中，Z1到Z5的五种构形是属于无经过关键顶点的环形链的构形，逆时针转型时，转型次数都是可以在小于等于4次转型时，就可以得到可以连续的移去两个同色的可约构形，再经一次转型就是一个只有一条连通链的可约构形，再交换一次就可空出颜色来；而在顺时针转型时，转型次数都是可以在小于等于6次转型时，就可以得到有经过了关键顶点的环形链的构形，可改用断链交换法，提前结束转型。Z6到Z10的五种构形则是属于有经过了关键顶点的环形链的构形，可以用断链交换法解决。Z11到Z15的五种构形也是属于无经过关键顶点的环形链的构形，但与Z1到Z5的五种构形转型时的结果却相反，逆时针转型时，转型次数也都是可以在小于等于6次转型时，就可以得到有经过了关键顶点的环形链的构形，可改用断链交换法，提前结束转型；而在顺时针转型时，转型次数也都是可以在小于等于4次转型时，就可以得到可以连续的移去两个同色的可约构形，再经一次转型就是一个只有一条连通链的可约构形，再交换一次就可空出颜色来。以上的构形的转型次数也都是符合逻辑推理的结论的，转型次数都不大于8。
③  张先生的第八构形的放大图的解决也是符合我们用逻辑推理所得到的结论的。由于该构形中还含有局部的环形链，环绕着双环交叉链的某些单独顶点，所以这一类构形还可以在局部的环形链之内进行与其相反的色链的交换，也至少能断开一条连通链，变成无双环交叉链的可约构形。如一条环型的A—B链构成的4—圈，其中心顶点是双环交叉链A—C或A—D两链中的一个C或D，把该C色顶点变成D色，或者把D色顶点变成C色，就可以使A—C链或者A—D链断开，把图由有双环交叉链的构形转化成无双环交叉链的可约构形。
④  前面的图0是标准的无经过关键顶点的环形链的构形，A—B链和C—D各都只有一条，且不分叉的单一道路，各条链中相同颜色的首、尾顶点间，只隔着一个与其呈相反色链的链中的顶点，改变该顶点的颜色为其相反色链中的颜色时，图就转化成了有经过了关键顶点的环形链的构形，可以直接使用断链交换法了。如把图0围栏中的C色顶点左侧的B色顶点，改成D色时，图就转化成了有经过了关键顶点——两双环交叉链的末端顶点C和D——的C—D环形链的构形了；把图0围栏中的D色顶点右侧的C色顶点，改成B色时，图就转化成了有经过了关键顶点——两双环交叉链的共同起始顶点（图中构形的峰点顶点A）和交叉顶点（图中最下边的顶点A）——的A—B环形链的构形了。如果无经过关键顶点的环形链的构形中的A—B链和C—D链都呈树状分布，当然也有可能直接转化成有经过了关键顶点的环形链的构形。由此可以看出，无经过关键顶点的环形链的构形也是可以直接转化成有经过了关键顶点的环形链的构形的，但这是个别的现象还是普遍的规律，我们现在还不知道。如果是普遍规律，解决无经过关键顶点的环形链的构形就简单得多了。虽然如此，但还是可以用转型交换法解决这类构形的可约性问题的，这也就已经够用了。
4、补充：还是把有双环交换链的构形分为有经过了关键顶点的环形链的构形和无经过关键顶点的环形链的构形两大类好一些
在文中第2个问题中，有这样的段话：“这也就是张彧典先生认为的、在他所构造的八大构形之外，再没有别的构形的原因。然而张先生却没有看到他所构造的八个构形中，除了第二构形是最基本的、也是最小的、只有四条边的、有经过了关键顶点的环形链的构形外，其他的构形都是无经过关键顶点的环形链的构形，而且全都是可以连续的移去两个同色B的构形，是不能代表所有的构形的，至少其中就缺少有经过了关键顶点的环形链的构形。”
现在我们看，第二构形既是有经过了关键顶点的环形链的构形，当然是可以用断链交换法进行解决的。的确，第二构形就是最小的一个最基本的有经过了关键顶点的环形链的构形，是可以用断链交换法进行解决的。张先生的八个构形集，连同E—图，共九个构形。把这九个构形按有、无经过了关键顶点的环形链分为两组时，第二构形与第九个E—图构形就是一类，是有经过了关键顶点的环形链的构形，都可以用断链交换法进行解决；而除了第二构形外的前七个构形则是另一类，都是无经过关键顶点的环形链的构形，都可以用转形交换法进行解决。
转型有两种不同方向的转型方法，张先生用的是逆时针方向转型的方法，前八个构形，分别是用了二到九次交换，其中分别只有一到八次是转型交换。这个数字再减去1，就是张先生说的各个构形的“难点转化”次数。也就是说，转形次数等于“难点转化”次数时，就是一个可以连续的移去两个同色的可约构形。对于第一构形来说，难点转化次数是0，就是张先生对第一构形所说的“这类构形难点不转化”。的确，第一构形用逆时针转型时，就是一个可以连续的移去两个同色B的可约构形。
如果对张先生的前八个构形按顺时针方向转型时，除了第二构形外，其他七个构形都的难点转化次数都是0次，即是不用转形就都可以连续的移去两个同色B的可约构形。这一点我早已给张先生就指出过了，张先生也看到和认识到了这一点。
这样一来，就整个有双环交叉链的构形来说，也就只可以分成两大类——即有经过了关键顶点的环形链的构形和无经过关键顶点的环形链的构形。前一类有经过了关键顶点的环形链的构形用断链交换法进行解决；后一类无经过关键顶点的环形链的构形用转型交换法解决，最大的交换次数是不会大于9次就一定可以得到解决。这样证明了任何极大平面图的不可避免构形都是可约的。四色猜测也就证明是正确的了，四色问题就得到了解决。

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

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

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，

雷明85639720

，，，，，，，，