H—构形的最大交换次数是9（修改稿）

雷明85639720

H—构形的最大交换次数是9（修改稿）
雷  明
（二○一九年元月六日）
（图我在这里发不上去，请到《中国博士网中去看》）

1、第一类、第二类H—构形的交换次数
H—构形按图中有没有环形链可以分为三类：BAB型H—构形为例，第一类是有环形的A—B链（如图1），第二类是有环形的C—D链（如图2），第三类是没有任何环形链的（如图3和图4）。

第一、二类构形，都有环形链，且隔其相反色链于环形链的内、外，互不连通。所以就可以交换环形链内、外的任一条相反色链，使H—构形中连通且相交叉的A—C链和A—D链变得不连通或不相交叉，图变成K—构形而可约。最多只交换二到三次就可以从围栏顶点中空出颜色来给待着色顶点。
    2、第三类H—构形的交换次数
图3和图4只是左右结构的交换，实际上是同一类构形。只研究图3一个就可以了。图3中没有环形链，A—B链和C—D链都是直链且只有一条，所以都不可进行交换，只能进行转型交换了，先移去一个同色B，然后根据转型后的构形再决定下一步的交换步骤。
㈠　连续的逆时针方向转型交换：

第一步：对图3从顶点1开始交换B—D链，生成了从顶点3到顶点5的连通链B—C，不能移去两个同色B（如图5—1），说明了图3是一个H—构形；虽没有直接生成环形链，但图5—1却有可能生成DCD型构形的C—D环形链（如图5—2）而结束转型交换，再交换三次即可解决问题，总共是四次交换。
第二步：对图5—1从顶点4开始交换D—A链，不会直接生成从顶点1到顶点3的连通链D—B（如图6—1），说明图5—1是一个可以连续的移去两个同色D的K—构形，再交换一次即可解决问题，总共只用三次交换；图6—1还有可能生成ABA型构形的C—D环形链（如图6—2）或A—B环形链（如图6—3）而结束转型交换，但此时的构形本身就是一个只有一条连通链的K—构形（如图5—1中的粗线所示），再交换一次或两次也即可解决问题，总共是三次或四次交换；当然图6—1也还有可能生成从顶点1到顶点3的连通链D—B（如图6—4），说明图5—1也可能是一个不可连续的移去两个同色D的H—构形。

第三步：对图6—4从顶点2开始交换A—C链，不会直接生成从顶点1到顶点3的连通链D—B（如图7—1），说明图6—4也是一个可以连续的移去两个同色A的K—构形，再交换一次即可解决问题，总共只用四次交换；图7—1还有可能生成CDC型构形的A—B环形链（如图7—2）而结束转型交换，但此时的构形本身就是一个只有一条连通链D—B的K—构形（如图6—4中的粗线所示），再交换一次或两次也即可解决问题，总共只是四次或五次交换；当然图6—4也还有可能生成从顶点1到顶点3的连通链D—A（如图7—3），说明图6—4也可能是一个不可连续的移去两个同色A的H—构形。

第四步：对图7—3从顶点5开始交换C—B链，也不会直接生成从顶点2到顶点4的C—A链（如图8—1），说明图7—3也是一个可以连续的移去两个同色A的K—构形，再交换一次即可解决问题，只用了四次交换；图8—1不可能生成有环形链的构形而结束转型交换；当然图8—1也还有可能从顶点2到顶点4生成连通链C—A的可能（如图8—2），说明图7—3也可能是一个不可连续的移去两个同色C的H—构形。

第五步：对图18—2从顶点3开始交换B—D链，生成了从顶点1到顶点3再到顶点４的连通链D—A，永远也不可能有从顶点5到顶点2生成B—C链的可能性（如图9）。所以图18—2已是一个可以连续的移去两个同色B的K—构形。
第六步：对图9从顶点5开始交换B—C链，可以连续的移去图18—2中的两个B（如图10—1）；或者对图9从顶点2开始交换C—B链，则可以空出图9中的C来给待着色顶点（如图10—2）。
    总共进行了六次交换。
㈡  顺时针方向转型交换：
以上是对图3进行逆时针方向的转型交换，若按顺时针方向转型时，则是：
第一步：对图3从顶点3开始交换B—C链，除了生成从顶点1到顶点4的连通的B—D链（图11中未用粗线标出）外，还是一个DCD型的第二类构形，有一条经过顶点1和顶点2的环形的A—B链（如图11）。

第二步：对图11在A—B环形链内交换C—D链，使得连通且相交叉的A—C链和A—D链断开，图变成了不能移去两个C的K—构形（如图12）。
第三步：对图12从顶点2交换A—D链，可以空出A来（如图13）；从顶点1交换B—D链，可以空出B来（如图14）；从顶点3分别交换D—A链或D—B链，均可空出D来（如图15和图16）。

总共只用了三次交换，就从围栏顶点中空出了颜色。
㈢  连续的顺时针方向转型交换：

现在若不管形成不形成第二类构形，一直用顺时针方向转型下去，看一下是什么结果。
第一步：对图3从顶点3开始交换B—C链，生成了从顶点1到顶点4的连通链B—D，不能移去两个同色B（如图17），说明了图3是一个H—构形。同时图17也是一个含有A—B环形链的第二类H—构形（图中未用粗线标出，这在上面已进行了祥细的分折）。

第二步：对图17从顶点5开始交换C—A链，也不能直接生成从顶点3到顶点1的C—B链（如图18—1），说明图17也是一个可以连续的移去两个同色C的K—构形，再交换一次即可解决问题，只用三次交换；图18—1还有可能生成ABA型构形的C—D环形链（如图18—2）或A—B环形链（如图18—3）而结束转型交换，但此时的构形本身也是一个只有一条连通链B—D的K—构形（如图17—3中的粗线所示），再交换一次或两次也即可解决问题，总共只是三次或四次交换；当然图18—1也还有可能生成从顶点1到顶点3的连通链C—B（如图18—4），说明图17也可能是一个不可连续的移去两个同色C的H—构形。

第三步：对图18—4从顶点2开始交换A—D链，也不能直接生成从顶点5到顶点3的A—C链（如图19—1），说明图18—4也是一个可以连续的移去两个同色A的K—构形，再交换一次即可解决问题，只用了四次交换：图19—1还有可能生成DCD型构形的A—B环形链（如图19—2）而结束转型交换，但此时的构形本身也只是一个无通链的K—构形最多再用一次或两次交换，就可解决问题，总共也只有四次或五次交换；当然图19—1也还有可能生成从顶点5到顶点3的连通链A—C（如图19—3），说明图18—4也可能是一个不可连续的移去两个同色A的H—构形。
第四步：对图19—3从顶点4开始交换D—B链，也不能直接生成从顶点2到顶点5的D—A链（如图20—1），说明图19—3也是一个可以连续的移去两个同色A的K—构形，再交换一次即可解决问题，只用了四次交换；图20—1不可能生成有环形链的构形而结束转型交换；当然图20—1也还有可能从顶点2到顶点5生成连通链D—A的可能（如图20—2），说明图19—3也可能是一个不可连续的移去两个同色C的H—构形。

第五步：对图20—2从顶点1开始交换B—C链，生成了从顶点3到顶点１再到顶点５的连通链D—A，永远也不可能有从顶点4到顶点2生成B—D链的可能性（如图21）。所以图20—2已是一个可以连续的移去两个同色B的K—构形。
第六步：对图21从顶点4开始交换B—D链，可以连续的移去图20—2中的两个B（如图22—1）；或者对图21从顶点2开始交换D—B链，则可以空出图21中的D来给待着色顶点（如图22—2）。

从以上的研究中也可以看出，第二类H—构形也是可以用连续的转型交换（四次交换）解决问题的。
㈣  轴对称的第三类H—构形的转型交换：
1935年美国人Iirving Kittell构造的有对称轴的图（如图23），也属于第三类构形，由于其左右的是轴对称的，所以其转型只需要进行一个方向的交换即可。转型交换如下：
第一步：对图23从顶点1开始交换B—D链，得到图24。

第二步：对图24从顶点4开始交换D—A链，得到图25。
第三步；对图25从顶点2开始交换A—C链，得到图26。这是一个既含有A—B环形链，又含有C—D环形链的的构形，即是第一类H—构形，又是第二类H—构形。用解决那一类的方法都可以。

第四步：对图26交换C—D环形链内的A—B链，得到一个只有一条连通链D—A的K—构形（如图27）。或者对图26交换A—B环形链内的C—D链，也得到只有一条连通链D—A的K—构形（如图29）

第五步：对图27从顶点3开始交换B—D链，空出了B来（如图28）。或者对图29也从顶点3开始交换B—D链。也能空出B来（如图30）。
也是总共进行了五次交换。
现在再连续的转型如下：

第一步：对图23从顶点1开始交换B—D链，生成了从顶点3到顶点5的连通链B—C，不能移去两个同色B（如图31），说明了图23是一个H—构形。
第二步：对图31从顶点4开始交换D—A链，生成了从顶点1到顶点3的连通链B—D，也不能移去两个同色D（如图32），说明了图31也是一个H—构形。

第三步：对图32从顶点2开始交换A—C链，生成了从顶点4到顶点1的连通链A—D，也不能移去两个同色A（如图33），说明了图32也是一个H—构形。图33就是上面说的既是第一类的H—构形，又是第二类的H—构形。

第四步：对图33从顶点5开始交换C—B链，生成了从顶点2到顶点4的连通链C—A，也不能移去两个同色C（如图34），说明了图33也是一个H—构形。
第五步：对图34从顶点3开始交换B—D链，生成了从顶点1到顶点4C以及从顶点1到顶点3的连通链D—A，使得从顶点5到顶点2不可能生成连通的B—D链（如图35），说明了图34已经是一个可以连续的移去两个同色B的K—构形了。

第六步：对图35从顶点5开始交换B—C链，就连续的移去了图34中的两个同色B（如图36—1）。当然也可以对图35从顶点2开始交换C—B链，空出图35中的C来（如图36—2），围栏顶点中仍含有一个B。总共进行了六次交换。
从这里也可以看出，第二类H—构形也是可以用连续的转型交换（三次交换）解决问题的。
4、既是第一类构形又是第二类构形的连续转型交换
这一类构形具有两种构形的特征（如图37），既有环形的A—B链，又有环形的C—D链，但并不是一种单独的构形，可以用解决每一种构形的解决办法去解决。这里主要是想用连续转型交换的方法进行解决。
第一步：对图37从顶点1开始交换B—D链，产生了从顶点3到顶点5的连通链B—C（如图38）。

第二步：对图38从顶点4开始交换D—A链，产生了从顶点1到顶点3的连通链D—B（如图39）。
第三步：对图39从顶点2开始交换A—C链，产生了从顶点2到顶点5的C—B链，并不产生从顶点4到顶点1的A—D链（如图40），说明图39已是一个可以连续的移去两个同色A的K—构形了。
第四步：对图40分别从顶点4和顶点1开始交换A—D链和D—A链，就可分别空出A和D来（如图41和图42）。

连续转型交换结束，总共用了四次交换。
5、H—构形的最大交换次数是9
通过以上的研究可以看出，第一类和第二类的H—构形，无论是用属于该类构形单独的解决办法，还是用连续转型交换的方法，最大的交换次数均是不会大于5的；对于第三类的H—构形，用连续转型交换的方法，交换的次数最大都是6；图37的那种既是第一类又是第二类的构形，其连续转型交换的次数也只是4，仍是小于6的。这是否可以说，任何H—构形解决时，交换的次数都是不会大于6的呢。不，还不能这么简单的下结论。
因为我们对第三类构形所进行的交换都是从两个方向进行的连续转型交换，两个方向均在第四次交换后，图都已经不再是H—构形了；第四次交换后的图是可以连续的移去两个同色的K—构形，第五次交换后的图则是一个更普通的K—构形，第六次交换后的图就已经空出了颜色给待着色顶点，着色结束。而第三次、第二次、第一次交换后的图以及原图——图3，则都是第三类H—构形，共七种。可见，这七种第三类H—构形中的任何一种，无论是向那个方向的转型交换，最大的交换次数一定都是不大于9的。其中最后三次交换对于任何一种第三类H—构形来说，都是必须的。而其中倒数第三次交换是把H—构形变成可以连续的移去两个同色的K—构形的转型交换，而倒数第二次、第一次交换都是属于空出颜色的坎泊交换，并且都是在K—构形间进行的；而前面的一次到六次的交换则都是在第三类H—构形间进行的峰点位置发生变化的转型交换，但构形仍属于第三类H—构形，但这一次到六次的交换，对于每一种第三类H—构形来说，交换的次数则是不同的。
下面用图来解释一下（如图43）：

图43中，字母表示构形的类型，数字是交换的次数，箭头是转型交换的方向。H0第三类Ｈ—构形的标准图——图3或图4的原图，H1、H2、H3分别是H0向两个方向转型交换1、2、3次后,所得到的第三类H—构形， K4是可以连续的移去两个同色的K—构形，K5是只有一条连通链的普通的K—构形，K6是已着色完成的图。图中共有七种第三类的H—构形，一个H0，两个H1，两个H2和两个H3。向右是逆时针方向，向左是顺时针方向。
我已经把那个轴对称的第三类构形——图23，在逆时针转型交换的第三次交换所得的构形——图33，进行了顺时针方向的转型交换，的确是需要9次交换才能空出颜色来。
这一结果是不是与我以前构造的交换次数是10，16，17，22，甚至更大，以至无穷的构形产生了矛盾呢。我认为也并不矛盾。因为我构造那些构形的目的，并不是为了找到最大的交换次数，而都是为了否定张先生提出的最大交换次数是8（最先的）和16（后来的）而构造的，并且都是在张域典行生主张的连续转型交换的前提下进行的。并在转型交换的过程中，就是在中途遇到了可以改换成用我解决第一类，第二类H—构形的处理办法（也就是张域典先生的Z—换色程序）处理时，也不去处理，仍然坚持连续的转型交换下去。所以交换的次数就一定大于9了，以至于我还构造了一个与敢峰—米勒图一样的构形，是一个无穷连续转型交换也不可能空出颜色的构形。如果我在连续转型交换的过程中，及时的改换处理方法，那么总的交换次数一定是不会大于9的。
6、再评张域典先生的H—构形的不可免集
张域典先生把H—构形按转型交换次数的无穷性与与有穷性，分成了十折对称构形与非十折对称的构形两大类。在这里的所谓十折对称构形就是敢峰—米勒图。对于十折对称构形，张先生是用他的Z—换色程序解决的，是没有错的。这种解法就是我们上面说的解决第一类和第二类H—构形的方法。但在非十折对称的构形中，同样也存在着可以用Z—换色程序可以解决的大量构形。这种构形的特征与敢峰—米勒图是相同的，都是含有环形的A—B链或环形的C—D链的。可张先生却把这些构形与没有任何环形链的，属于我的第三类H—构形的构形，统一都用连续的转型交换方法（张先生叫它连续的赫渥特颠倒法）进行处理。张先生只是从对敢峰—米勒图中的某些四色四边形的对角线的改变得到了所谓的15种Z—构形，并分别命名为Z1，Z2，……，Z15，转型交换的次数分别是2到16（可以说是他的Z—构形名称的下角数加1就是该构形的交换次数），这是不合适的，不能体现一般性的原则。
张先生还在《H—M族构形的放大》一文中，用在敢峰—米勒图内增加某些四色部件的方法，想回答在万春如先生翻译的《一种试探式的平面图四染色》一文中需要解决的两个问题。张先生虽没有明确的表达，他是否回答了这两个问题，但我却用张先生所给出的在敢峰—米勒图中增加了四色构件的图，得到了在敢峰—米勒图之外，还存在着无穷次转型交换也空不出颜色给待着色顶点的图（见我的《再给出几个类似米勒图的构形》一文）。其转型交换过程中，中间结果也是在我的第一类构形与第二类构形之间不断的转化的，且每一个是间结果也都是可以用解决第一类和第二类的方法直接解决的。这说明转型交换次数是无穷性的图并不是只有敢峰—米勒图一个。但我所得到的这个图的却又不是张先生所说的“十折对称”的，所以说，张先生的两大类，就该叫做“转型交换次数是无穷次的构形”和“转型交换次数是有穷次的构形”两大类，面不应再叫做“十折对称的构形”和“非十折对称的构形”了。正因为如此，所以我说张先生的这些Z—构形是根本就没有脱离敢峰—米勒图的束缚的，也不能体现一般性的原则。
因为敢峰—米勒图是一个无穷次连续转型也不能空出颜色的构形，且转型过程中，图总是在我的条一类构形和第二类构形间不停的转化着，所以张先生才对该构形采用了Z—换色程序进行解决，这也是正确的。但张先生的Z—构形均是把敢峰—米勒图中的某些四色四边形的对角线进行了改变，所以就使得连续的转型交换就在某一些改变了四色四边形的对角线的地方，不能再连续转型下去而结束了转型。这就是张先生得到了十五个Z—构形的来历。这也不算错。问题是在对这些Z—构形的连续转型过程中，同样的是与敢峰—米勒图一样，图也总是在我的第一类构形和第二类构形之间不停的转化着，任何一个中间结果都是可以用Z—换色程序解决问题的。但张先生却没有这样做，而且张先生也不主张这样做。这就把一个可以只需要很少次交换可以解决的问题，就可能变成了必须经过多次（2到16次）的交换才可以解决的问题。实在是少慢差费。这还不算大问题，最大的问题是还有一部分不含任何环形链的属于我的第三类H—构形的构形，还没有包含在张先生的Z—构形之内。这样张先生的H—构形的不可免集就不完备了。
由于转型交换次数是无穷次的构形，在整个交换的过程中，是以每20次交换为一个周期进行循环的，所以转型交换次数是无穷次的构形一定要在第20次交换时，使得图变成一个可以连续的移去两个同色的K—构形，否则图就是一个转型交换次数是无穷次的构形。而这个K—构形还是再需要两次交换，才能空出颜色来给待着色顶点的。这样加上已进行了的20次交换，共计是22次。这就应该是转型交换次数是有穷次的构形的最大交换次数。从这个意义上来说，张先生的两大类H—构形也可以说是完备的。解决“转型交换次数是无穷次的构形”时，用Z—换色程序；解决“转型交换次数是有穷次的构形”时，用连续的转型交交法，一定可以在有限的交换次数（9次或22次）之内使问题得到解决，空出颜色。不必要再分有多少个Z—构形的次类了。


雷  明
二○一九年元月六日于金堆城

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

波斯猫猫

这就是在搞科研吗？在解决难题吗？这五个厕所里拉的这些点点是屎吗？浪费资源。
难道那篇报告文学启发了拉屎不成？即使拉屎也得有个次数，不能到处乱拉。

雷明85639720

你真是个混账！你指出的具体问题有什么地方呢？要讨论具体问题，要讲道理，漫骂是无能的表现！
你看没有看我的文章呢？

波斯猫猫

看：还有一些屎被系统自动隐埋，点此展开

雷明85639720

你害怕了吗，我把我的贴子向上提有什么不可以的。这是系统”自动隐埋“了的吗，你懂不懂嘛！我为了把我的贴子提上来，我可以只打几个点，不采具体内容，我的贴子就上到前面了，因为我没有打内容，当然系统就不再显示出来了。这一点你也不晓得，你还上什么网呢。