无环形链染色困局的最大交换次数

雷明85639720

无环形链染色困局的最大交换次数
雷  明
（二○一九年七月二十五日）
（我在这里发不上图，请到《中国博士网》中去看）

所谓染色困局就是指H—构形。含有经过构形围栏顶点的环形链H—构形，我们可以通过断链交换，交换环形链内外的任一条与环形链是相反色链的链，使图转化成不存在连通且相交叉链K—构形而可约。而无环形链的H—构形就只能用转形交换法解决了。这里我所说的H—构形是指不但含有连通且相交叉的链，而且同时又是不能连续的移去两个同色B的构形，即所谓的染色困局。以下我们先从理论上给一个转型交换次数的上界，然后我们再用可以代表一般的无环形链的染色困局（构形）进行最大转型交换次数的验证。
1、理论证明最大转型交换次数的上界
我们知道，米勒图进行转型交换时，是一个以20次转型交换为周期的无穷循环转型交换的H—构形，但这个图又是一个含有环形链的构形，用断形交换的方法是可以解决的。不管这种无穷循环转型交换的构形有多少个，除此之外，剩下的有限次转型交换的构形中，除了有环形链的构形，可以用断链交换法解决外，剩下的就是我们这里所说的无环形的链H—构形了。既然不是无穷循环转型交换的构形，它们一定是要在第20次转型交换前转化成一个可以连续的移去两个同色的K—构形，再交换两次就可以空出颜色来，结束转型交换，以防产生循环。这就从理论上给出了转型交换的最大交换次数的上界是不大于22次的。
若一个构形一个方向转型交换一次后就转化成了一个可以连续的移去两个同色的K—构形，而采用相反方向的转型交换时，最大也只是在第20次转型交换后，才可转化成可以连续的移去两个同色的K—构形。可以看出，在第19次转型交换之前的各次交换所得到的图，连同原图和第19次交换所得的图，共计20个，都一定是H—构形的染色困局。还可以看出，对这20个构形中的任何一种分别进行两个方向的转型交换时，两个方向转型交换次数的总和是不会大于是24次的。其中20次是转型交换，4次是两个方向分别进行的两次空出颜色的交换。若把逆时针转型交换的次数用X表示，把顺时针转型交换的次数用Y表示，则有X≤20，Y≤20和X＋Y≤20，单方向转型交换的总次数一定是小于等于20＋2＝22的，两个方向转型交换的总次数的和也一定是小于等于20＋2＋2＝24或20＋2×2＝24的。这样，两个方向的转型交换中，总有一个单方向交换的总交换次数是小于等于12的。所以，还可以说转型交换的最大交换次数是不大于12的。
2、用一般性的无环形链构形进行转型交换次数的验证
我们可以仿照敢峰先生构造终极图的办法，先画一个非常一般的不含连通链的H—构形，然后进行转型交换，每交换一次，都要人为的在平面图范围内再构造成H—构形。直到在平面图范围内不可能再构造成H—构形，图成为可约的可以连续的移去两个同色的K—构形为止。
图1是一个无环形链的H—构形，他具有以上我说的H—构形的特点。不但含有连通且相交叉的A—C链和A—D链（如图2），而且从顶点1开始交换了B—D链后，就会生成从顶点3到顶点5的连通的B—C链（如图3），从顶点3开始交换了B—C链后，又会生成从顶点1到顶点4的连通的B—D链（如图4），不能连续的移去两个同色B。所以它是一个地地道道的H—构形。

图1中没有经过构形围栏顶点的环形链，A—C链和A—D链均是直链，且各只有一条（如图5和图6）。由于图5和图6只是左右结构上的不同，实质上是同一个（类）构形，所以我们就只研究图5就可以了。
现在我们对图1进行逆时针转型交换如下：
第一步，对图1从顶点1开始交换B—D链，得到的图7（也就是是图3）中生成了从顶点3到顶点5的连通的B—C链。图转化成一个DCD型的H—构形。这个构形已经是一个可以连续的移去两个同色的构形D的K—构形了，这一点可以从第二步转形交换得到的图8中没有形成从顶点1到顶点3的连通链可以看出。

注意：这第一步如果是把处在A—C—V环外侧的B色和D色的顶点都交换颜色，则这个交换后的图就是一个K—构形，因为交换后生不成从顶点3到顶点5的连通的B—C链。但我们这里主要是想看一看无环形链的H—构形，道底能在几次转型交换内解决问题，所以我们还是只交换了处在同一条B—D链上的顶点的颜色。
第二步，对图7从顶点5开始交换D—A链，得到的图8中没有生成从顶点1到顶点3的连通链D—B，应该项说问题已经可以解决。但在平面图范围内还可以构造从顶点1到顶点3的D—B连通链（如图9），这是一个ABA型的H—构形。

第三步，对图9从顶点2开始交换A—C链，得到的图10中也没有生成从顶点4到顶点1的连通链A—D，问题也应得到解决。同样的，在平面图范围内也还是可以构造从顶4到顶点1的连通的A—D链的（如图11），这是一个CDC型的可以连续的移去两个同色C的K—构形，而不再是H—构形了。

第四步，对图11从顶点5交换C—B链，得到的图12中虽没有生成从顶点2到顶点4的连通链C—A，但在平面图范围内再不可能构造从顶点2到顶点4的连通链C—A了，因为其前面有一条边通的相反色链B—D在阻隔着，C—A链是不可能通过的。很明显的是一个只有一条连通的B—D链的K—构形了。
第五步，对图12再从顶点2交换C—A链，就连续的移去了图10中的两个同色C，把C给待着色顶点V着上（如图13）。着色结速。

以上只进行了三次转型交换，加上最后的两次交换，共计是五次交换。这就是无环形链的H—构形的最大交换次数。以上是对图1（也就是图5）按逆时针转型交换的，若按顺时针转型交换时，也会得出同样的结论（如图14到图20）。请读者自已试一试。

顺时针转型也只进行了三次转型交换，加上最后的两次交换，共计也是五次交换。两个方向的转型交换得出相同的结果，这就说明无环形链的H—构形的最大交换次数的确是不大于5的。如果由图1的任意的图变成极大图时，则交换的次数将会更少。
3、张彧先生的最大转型交换次数是错的
张先生只从改变米勒图（即无穷循环转型交换的所谓十折对称构形）中的某一个四边形对角线得到的个别构形，就得到除了无穷循环转型交换构形外的所有Z—构形（即非十折对称构形）的最大转型交换次数是16，这是错误的，因为只从个别的图出发得到的结论是不能代表一般的。张先生并且按实际交换次数的具体数值把Z—构形分为Z1到Z15的15种类型，其规律是构形Zi中的i＋1值就是Zi构形交换的次数，这也不太合适。这就是我认为张先生不进行转型交换的实际操作，就不可能知道某一个构形是属于那一类构形的原因。
但我们在对米勒图增加边和顶点后，发现所得到的非十折对称的构形中，转型交换的次数已大大的超过了16，且达到22次以上。这是与张先生所得结论不相符合的地方。若把张先生这里的Z—构形，也认为是我这里说的无环形链的H—构形时，其最大交换次数又是小于我们这里已证明了的转型交换的最大次数是22次的正确结果。可见，从不同的两个方面都说明了张先生得出的结论是错误的。
   
雷  明
二○一九年七月二十六日于长安

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，