H—构形的不同分类方法

雷明85639720

H—构形的不同分类方法
——回复张彧典先生之三
雷  明
（二○一六年元月十九日）

2015年8月以来，我与张彧典先生一直在讨论着我所画的一个图（如图1，a，当时我们都把它叫图3）的归类问题，但没有定论。原来是因为我们两个对H—构形分类的原则、出发点是不同的，当然也就不可能得出统一的结论。

1、我的分类原则是：不能同时移去两个同色的图就叫H—构形。相反，可以同时移去两个同色的图，则叫非H—构形。然后我再在H—构形中按解决问题的方法分为自由度是2的H—构形（如H—构形，M—构形，L—构形等）和自由度是１的Ｈ—构形（如Z—构形，Z—L构形等）。解决问题的方法多，解决问题的自由度就大。目前还没有发现不能解决的问题。每一种解决方法算一个自由度，所以最小的自由度是1。自由度的倒数就是解决问题（着色）的难度系数，则自由度越小，难度系数就越大，最大只能是1（如Z—构形，Z—L构形等），自由度是２确的图的难度系数是0.5。
2、而张先生的分类原则是：只要含有两条交叉的连通链的图统一归属H—构形。然后再用逆时针赫渥特颠倒的次数和“难点转化”的次数进行分类。所谓赫渥特颠倒就是交换关于两条同色链（B—D链和B—C链，如图2）中的一条，颠倒者交换也，颠倒的实质也就是进行交换。逆时针或顺时针“颠倒”是交换那一条关于两条同色链的问题。交换左边的B—D就是逆时针颠倒，交换右边的B—C链则是顺时针颠倒。张先生把进行一次颠倒后，仍是含有两条交叉链的情况时，就叫一次“难点转化”。看来难点转化的次数等于颠倒次数减1。

3、对于图1，a，由于分类的原则不同，当然就会得出不同的结果。该图有两条连通且相交的链A—C和A—D，有C—D环形链，虽有赫渥特图的特征，但可同时移去两个同色B。我把它归为非H—构形。而张先生把它归为H—构形。由于该图同时具有张先生的第一构形和第二构形的特征，所以张先生把它归为第一构形或第三构形。不仅如此，具有这种特征的图还有如图1，b和图1，c两种，在我看来他们是非H—构形，而在张先生看来则是H—构形。按张先生的方法它他一定也可以归属于其九构形中的某一种了。
4、对于图1，a中的图，由于分类的方法不同，也就有两种不同的解决方法。张先生用的是“赫渥特颠倒法”，而我用的是“同时移去两个同色的方法”。都能得出不同模式4—着色结果。张先生在《详图回复雷明图3归类》一文中的第一种着色方法，给待着色顶点V着B时，就是我的同时移去两个同色B的方法；当你给待着色顶点V着C时，就是因为施行一次颠倒后的图变成了一个非H—构形的图，图中只有一条C—A连通链，而没有C—B连通链与其相交，所以才能空出C（或B）给V着上（下面是张先生文中的照片，可以参考）。

5、张先生在《详图回复雷明图3归类》一文中的第二种着色方法，当你“在左边大的红色A—C环内交换B—D链的染色，使得左边两个A—C环内的孤点色D也变成B色，见蓝色字母”（张先生的话见附录中，以下同）的这两句话应是并列的两步操作，后一句并不是前一句的结果。所以我一直说你这句话说得很不明白，一下子还是难以看懂的。
以上的两步操作完成后，“这时生成蓝色的B—C环，在B—C环外交换A—D链的染色，见红色字母，就会生成新的绿色A—C环了。”因为你画了图，这句话我现在才看明白了，也理解了，的确是生成了一条A—C环。我以前只所以叫认为只是生成了一条A—C链，而不是A—C环，是因为我只看到了在5—轮上A、C两点间的对角链A—C是不连通的，而没有考虑到你所说的是在5—轮上的两个A、A对角间真有一条连通链A—C，该链与待着色顶点V一起真是构成了一个A—C环。再向下，你的解法都是对的。
你的这第二种解法也属于“颠倒法”一类。你在“在B—C环外交换A—D链的染色，见红色字母，就会生成新的绿色A—C环了”后，得到的也是一个非H—构形，图中只有B—C连通链，而没有B—D连通链，所以可以空出B（或D）给V着上。
6、由于我们两个对H—图的分类原则不同，所以各都认为各的交换有规律，对方没有规律。但的确你交换的次数比我交换的次数要多。你对图1，a的第二种方法用了四次交换（包括你说的“使得左边两个A—C环内的孤点色D也变成B色”这一交换），而我只用了两次交换，就可同时移去了两个同色B，交换的次数比你的少了一半，也达到了对其4—着色的目的。
我画的图1，a中有一条C—D链，所以它又是一个H—构形，也可以用“断链法”进行解决；若图中无C—D环，而是A—B环（如图1，b），仍是一个非H—构形，也是可以同时移去两个同色B的；若图中既无C—D环链，又无A—B环链（如图1，c），还是一个非H—构形，仍是可以同时移去两个同色B的。
由于我们对于H—构形的分类原则的不同，就产生了对某些图的分类不同，这当然也是允许的，也是能理解的。
7、虽然我们都能用各自的分类方法，对各类H—构形都能有效的进行4—着色，但我们之间还是有一定分岐的。主要的分岐在于我认为用着色的方法解决不了四色猜测的证明问题，要走“不画图，不着色”的道路；而你则认为你的九大构形能包括所有的H—构形，四色猜测已被证明。如果你一定是这样认为，你就得要狠下功夫，证明不可能再有别的构形出现了。不要别人的构形一出现，你就一个个的往你的九构形中去套，这是不符合证明原则的。而要从根本上证明，不可能再会出现别的构形了。目前你的那个证明我认为是不能令人信服的。
8、按我的分类法：所有构形分为K—构形，即坎泊已经证明过的所有构形，张先生可能也是这样认为的；可以同时移去两个同色的构形就是非H—构形；不能同时移去两个同色的构形就是H—构形：H—构形中，又分为自由度是2，难度系数是0.5的H—构形，这种构形，既可以用“颠倒法”解决，又可以用“断链法”解决，如H—构形，M—构形，L—构形，其中H—构用交换A—B链，M—构形用交换C—D链，两种L—构形，一个用交换A—B链，另一个用交换C—D链，最终都使A—C和A—D链达到断链的目的。还有一种H—构形的自由度是1，难度系数也是1的Z—构形（即张先生第八个构形的简化图）和Z—L构形，这样的构形只能用“颠倒法“解决”。使图变成非H—构形或别的H—构形的图，再进行最后解决问题。一次颠倒不行，可以进行多次颠倒，直到达到目的为止。但要注意，颠倒的逆时针、顺时针方向确定好后，就不要再变。因为后一个逆时针方向就是前一个顺时针方向的逆方向，而后一个顺时针方向就是前一个逆时针方向的逆方向。要防止陷入无限循环的陷阱。对于M—构形，无论怎么颠倒后都得到一个H—构形，这时就得赶快用解决H—构形的方法去解决。否则再进行了颠倒后，图就又变成了M—构形，这样循环下去就会陷入陷阱中不能出来。
9、若按张先生的分类法，则把所有构形分成了K—构形和H—构形两大类。而在H—构形中又按颠倒的次数分为九种，这就是张先生的九构形。我过去建议你把第一，第三到第七构形的六种构形归为一类，是出自于我的分类方法的，因为它们都是可以同时移去两个同色的。而现在张先生是按逆时针颠倒次数的多少分类的，那么我认为你就不要再把九种变为3种了，因为这六个构形的图颠倒的次数的确是不同的。他们进行了几次颠倒就是第几构形吧。另外你这只是逆时针颠倒，你那几个图若按顺时针方向颠倒，是不是也要得出不同的构形来呢。或者那几个图的左右方向颠倒后，又将会得到什么样的分类呢。
10、总算我们之间的分岐找到了产生的根源，并都是有各自的道理的。既然是这样，那么我们就各自用自已的分类方法，研究自已对各种H—构形的着色方法吧。

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

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

附：张先生的回复：
详图回复雷明图3归类
张彧典
我在去年给你的图3的回复中曾经这样叙述过，你还是不明白，所以现在结合详图再次回复如下：
您的第一步交换B-D链的染色实际上是在左边小的红色A-C环内进行的，如图解法1，见蓝色字母，这样一来，就生成新的绿色A-D环，再在这个新A-D的环内（外）交换B-C链的染色，从而空出了B(C)色。这样的解法属于我的图3-1的解法。所以可以归纳为我的图3-1 。
退一步，即便不管其是否最简构形， 就按照您给出的大环考虑，如图解法2，当在左边大的红色A-C环内交换B-D链的染色，使得左边两个A-C环内的孤点色D也变成B色，见蓝色字母，这时生成蓝色的B-C环，在B-C环外交换A-D链的染色，见红色字母，就会生成新的绿色A-C环了。再在新的A-C环内交换B-D链（其实只要把V的5个相邻点中的孤点B改染色D就可以了）的染色，可以空出B色。这样的解法如同我的第二个构形的解法，即Heawood反例的解法，所以可以归纳为我的图3-2。
以上解法都是遵循H-染色程序进行的，而你的断链法当然没有错误，但是没有规律。
详图如下：