雷明与张彧典两种证明四色猜测方法的比较

雷明85639720

雷明与张彧典两种证明四色猜测方法的比较
——再与张彧典先生商榷
雷  明
（二○一七年二月十四日）

1、H—构形的特征：
H—构形一定是一个5—轮构形，其中一定具有两条既有共同起始顶点，中途又相交叉的连通链（简称有两条相交叉的连通链）的构形，且该构形也一定是不能同时移去两个同色的构形。赫渥特图就有这样的特征，所以我们把具有这种特征的构形统一叫做H—构形（H—是赫渥特英文名字第一个大写的英文字母）。
一个5—轮构形的轮沿顶点（围栏顶点）占用完了四种颜色时，一定是有两个顶点是用了同一种颜色的，这就是两个同色顶点。A、B、C、D四种颜色只能形成A—B、A—C、A—D、B—C、B—D、C—D六种色链。在123—BAB 型5—轮构形中，两条连通链A—C、A—D已是固定了的，不能交换，也不能改变；而B—C链和B—D链又不能同时交换，所以也就不能同时移去两个同色B，也相当于不能改变了。那么剩下来的只能是改变A—B链和C—D链，或者对其进行交换了。
A—B链和C—D链间的相对关系可以是：①　A—B链是环形的，而C—D链非环形，被A—B环链隔成互不连通的两部分；②  C—D链是环形的，而A—B链也非环形，也被C—D环链隔成互不连通的两部分；③  A—B链和C—D链都非环形，且各只是一条；④  A—B链和C—D链都有环形部分，也有与环形部分互不连通的非环形部分。只可能有这四种情况，再不可能有别的情况了。这就是H—构形的不可免集，且是完备的。由于第④种情况兼有第①和第②两种情况的特征，归为哪一类都可以，不能单独成为一类，所以，以上的不可免完备集中实际上只有①②③三种构形。现在，我们只要能证明这三种情况的H—构形都是可约的，那么，四色猜测也就可以得到证明是正确的了。
2、九点形构形：

九点形构形只有如图1的四种，由于九点形顶点数太少，不可能存在A—B链和C—D链同时都是环形链的情况，也不存在相关链（相关链是两条链中有一种颜色是相同的链）相互穿过的情况。所以除了图1，b是一个不可同时移去两个同色B的构形外，其他三个都是可以同时移去两个同色B的构形。
    图1中的这四个构形中，都有两条相交叉的连通链。除图1，b是不能同时移去两个同色B的H—构形外，其他三个构形都是可以同时移去两个同色B的构形。但张彧典张先生却说其不能移去两个同色B。他的理由是敢峰先生说了，只要是存在有两条相交叉的连通链的构形，就不可能再同时移去两个同色B了。我认为，不管是谁说了，都得要按事实说话。首先，这三个构形，如果从一个B色顶点交换了与其对角顶点的颜色构成的色链后，不会产生从另一个B色顶点到其对角顶点的连通链，若再从这后一个B色顶点交换与其对角顶点的颜色构成的色链后，当然就可以同时移去了两个同色B。但如果是从这后一个B色顶点的对角顶点开始交换与上述相同的色链，当然就不能再移去后一个B，而是把这个本来不是B的顶点换成了B（图2），当然就不能移去两个同色B了。

我们把图1中可以同时移去两同色B的构形图1，a、图1，c和图1，d仍叫做坎泊构形（K—构形）。这三个构形，图1，a可以任意先从哪一个B交换，都可以同时移去两个同色B；而图1，c则必须先从顶点1交换，图1，d则必须先从顶点3交换，才能同时移去两个同色B；否则，是不能同时移去两个同色B的。由于图1，c和图1，d只是左右的不同，实质上是同一种构形，所以图1K中实际上只有三种构形。张先生对图1，d不是先从顶点3进行B—C链的交换，而是先从顶点1进行B—D链的交换，当然不能同时移去两个同色B；他是进行了四次交换后，才给待着色顶点着上了图中已用过的四种颜色之一的。他比先从顶点3进行B—C链的交换，多进行了两次交换。

产生这一情况的主要原因是因为对图1，d先从顶点1进行逆时针颠倒交换B—D后，构形由一个123—BAB型的可移去两个同色B的K—构形，转化成了一个451—DCD型的如图1，b的H—构形；再从顶点4进行一次同方向的逆时针颠倒交换D—A后，构形再次又转化成了一个123—ABA型的如图1，c的可以同时移去两个同色A的K—构形；再交换两次，才能给待着色顶点着上A或D（如图3）。这一现象同时也说明了图1，c（或图1，d）的可以同时移去两个同色B的K—构形，与图1，b的不可同时移去两个同色B的H—构形是可以相互转化的。
对图1，d，但若先从顶点3进行顺时针颠倒的交换，两次交换就可以了解决问题了。同样的，也是由于这个原因，再加之张先生《探秘》一书中的第三到第七的五个构形，图中链的分布都有着共同的特点：即都有从顶点8A到顶点3B的单边链。先从顶点3交换B—C链时，顶点3B变成了3C，单边8A—3B变成了8A—3C，阻隔了从顶点1到顶点4的连通的B—D链的形成。这样，再从顶点1交换B—D链，都是可以同时移去两个同色B的。所以我们认为这五个构形实际上是与图1，c相同的同一类K—构形。在我们的建议下，张先生将他的这五个构形与第一构形统一归为一类，这是一个非常可喜的事。从此张先生的九个构形便只剩四个了（第一、第二、第八和第九）。
这样以来，张先生的八大构形的基础便开始动摇了，很可能他的最多颠倒八次的结论也就要动摇了。他后来又把第八构形归为第二构形一类，其原因是因为第八构形在进行逆时针颠倒时，交换的次数与第二构形是一样多的，都是三次。现在看来，张先生的九大构形就只剩下三个了（第一、第二和第九三个）。而张先生的前八大构形中最多只要三次交换就都可以解决问题了。原来的第八构形最多需要交换九次，现在看来也是不可能的了。
张先生与我们对图1，b的着色方法也是不同的：张先生对图1，b用颠倒法进行了三次交换，才空出了颜色给待遇着色顶点（如图4），而我们用断链法，最多只须进行两次交换，就可空出颜色给待着色顶点（如图5）。只有对于图1，a和图1，c，张先生的颠倒法与我们的断链法的交换次数是相同的，都是进行了两交交换。


图1，a和图1，c（或图1，d）只是两种不同的K—构形，只有图1，b才是真正的H—构形（赫渥特图简化后就是该构形）。图1中，图1，a和图1，c就是张先生《探秘》一书中的第一构形（张先生的第一构形中的实线边对应的是图1，c的构形，虚线边对应的则是图1，a的构形），图1，b则对应的是张先生书中的第二构形，图1，d对应的是张先生书中的第三构形。图1，a就是张先生在《补充》一文中说的Z1构形，图1，b则是《补充》文中的Z2构形。
3、非九点形构形：
张彧典先生说，在九点形的各链中增加偶数个顶点，仍是相同的构形，解法相同。现在我们来看一看是不是这样。由于顶点数的增多，就可能产生相关链的互相穿过，使得本来在九点形中是可以同时移去两个同色B的K—构形，有可能就变成了不可同时移去两个同色B的H—构形（如图6）。
图6，a虽和图1，a相同，都有环形的A—B链，但图6，a却不能同时移去两个同色B；图6，c与图6，d虽和图1，c与图1，d图相同，都没有环形链，但图6，c与图6，d却也不能同时移去两个同色B。张先生的第八构形就是这种构形，没有任何环形链，也不能同时移去两个同色B；图6的六个构形中，唯有图6，b仍和图1，b相同，不但都有环形的C—D链，而且都不能同时移去两个同色B。赫渥特图就是具有图6，b这样结构的图；图6，e就是敢峰—米勒图，A—B链和C—D链都有环形部分，又有与环形部分不相连通的非环形部分（他右边的图是敢峰—米勒图待着色顶点为隐形的另一种画图方式）。
2、1  图6，a用断链法，交换C—D链，使构形转化成为K—构形，再通过一次交换即可空出一种颜色来；图6，b也用断链法，交换A—B链，也使构形转化成为K—构形，也再通过一次交换即可空出一种颜色来。两次交换均可解决问题。但若用张先生的颠倒法，图6，a则要交换四次，图6，b也要交换三次。

2、2  图6，c和图6，d是同一类构形，只研究其中之一就可以了。由于图中没有环形链，A—B链和C—D链都不可能进行交换，所以也就不可能用断链的方法解决问题。那么，也就只能先交换其中一个关于B的链，先移去其中的一个B，使构形转型，然后再按转型后的构形进行研究。
图6，c从顶点1交换了B—D链后，转化成451—DCD型的可以同时移去两个同色D的K—构形（如图7），再进行两次交换，即可空出D或B，共进行了三次交换；图6，c从顶点3交换了B—C链后，转化成345—CDC型的有环形链A—B的H—构形（如图8），再进行两次交换就可空出颜色来，也是共进行三次交换。图6，d也有同样的情形。


对图6，c和图6，d按张先生的颠倒法着色时，无论是逆时针颠倒，还是顺时针颠倒，同样也都至少需要进行三次交换的。
2、3  图6，e的敢峰—米勒图，也就是张先生《补充》一文中的Z4构形。其中既有环形的A—B链，又有环形的C—D链，A—B链和C—D链分别都是分成互不连通的两部分。总是可以交换不连通的某一种链的一部分，使构形变成K—构形。对于敢峰—米勒图来说，我们选择A—B环链内、外的任一条C—D链进行交换，分别都可使构形变成为非H—构形的K—构形，再交换两次，即可空出颜色来。都只是用了三次交换（如图9，按习惯，我们把敢峰—米勒图仍用隐形方式表示），与张先生的方法是相同的，都是只用了三交交换。

    敢峰—米勒图还有一种着色方法：即先从顶点1（或顶点3）进行B—D 链（或B—C链）的交换，使构形转化成451—DCD型（或者345—CDC型）的如图6，b的具有A—B环形链的形如赫渥特图的H—构形，再按图6，b的着色方法，进行两次交换，也即可空出颜色来。由此可以看出，敢峰—米勒图是可以通过转型交换，与赫渥特图相互转化的。
2、4  对于张先生的第八构形（如图10），按我们的转型加断链（或转型加空出颜色）的方法，无论是从顶点1进行交换得到一个有A—B环形链的H—构形（如图11），还是从顶点3进行交换得到一个可以同时移去两个同色C的K—构形（如图12），都是只需要三次交换就可以解决问题。



张先生的第八构形，按张先生的颠倒法着色时，顺时针颠倒也只需要三次交换，但逆时针颠倒时，则需要九次交换。
2、5  张先生的第八构形的扩大图（如图13），这本来就是一个如图1，d的可以同时移去两个同色B的可约的K—构形，可以先从顶点3交换B—C链，移去一个B（如图14），再从顶点1交换B—D链，移去另一个B（如图15）。


同时，张先生第八构形的扩大图还具有敢峰—米勒图的特点，其中的A—B链和C—D链分别都有环形链部分与直链部分，且两部分均被其相反链（两链中颜色完全不同的链就是相反链）分隔成互不连通的两部分。交换任一种链的任一部分都可以使两条连通链中的一条断开，使构形成为只有一条连通链的K—构形而可约（如图16和图17）。



但用张先生的颠倒法对第八构形的扩大图着色时，顺时针只要两次交换，但逆时针却也需要九次交换。
2、6  张先生第九构形（即敢峰—米勒图）的扩大图，张先生也不能用颠倒法着色，而用了与前面八个构形不同的“Z—换色程序”。我们直接用断链法，或者转型加断链法，或者转型加空出颜色法，也都可以对其进行进行4—着色。
2、7  张先生《补充》一文中的Z3构形，应属于只含有A—B环形链的一类构形，应用断链法进行着色，交换A—B环形链内、外的任一部分C—D链，都可以使构形变成可以同时移去两个同色B的K—构形，再需要两次交换就可空出两个同色B来，共用了三次交换。而张先生用他的颠倒法却需要进行四次交换，比我的断链法多了一次交换。
4、两种证明方法的比较：
把以上的着色方法总结后，列出比较表如下表一：
从表一中可以看出，无论对哪一个构形着色，张先生的交换次数总是大于等于雷明的交换次数的，应该得出结论：雷明的方法比较简单，而张先生的方法则比较麻烦。

  在这些构形中，张先生的分类是这样的：构形1（包括Z1），3，4，5，6，7为一类；构形2（包括Z2），8，“8扩”为一类；构形9（即Z4），“8扩”为一类；Z3他没有明确应属哪能类；总之，不是四类就是三类。而雷明的分类则是：图6，a为一类，包括张先生的Z1，Z3和Z4和“9扩”；图6，b为一类，包括张先生的Z2；图6，c与图6，d为一类，包括张先生的第1，第3～第8构形和“8扩”；总共三类。
两人尽管分法不同，但以上所研究过的那些构形用二人的两种方法都能进行4—着色，说明了这些构形都是可约的。
雷明的分类原则是根据构形结构的不同（当然其解决的办法也是不同的）划分的。如果在其所列的不可免的H—构形集之外，再没有别的不同结构类型的构形，并且也能证明该集中这些构形都是可约的时，就应说明四色猜测是正确的了。雷明的这一分类方法，是能够证明再也没有别的结构的构形了存在了（这一点已在前面的“1、H—构形的特征：”中已经进行了说明）。
而张先生的分类原则则是“构形最小，解法相同”，这个提法本身就很难理解，也是不科学的。什么是“构形最小”，什么是“解法相同”，都很不明确。最开始张先生并没有证明在他的八大构形之后，就再也没有别的构形了，虽然他讲了一番“色链的不同数量组合及不同位置组合”，但看不明白他道底是在说什么。虽然他也把第八构形进行了扩大，这只能说明这个构形“8扩”与第八构形在用逆时针方向颠倒时，都用了相同的交换次数（都是九次。当用顺时针颠倒时，交换的次数则是不同的：第八构形顺时针颠倒要交换三次，而第八构形的扩大顺时针交换时，却只要两次交换），但这并不能说明其后就再也没有需要交次数更多的构形了。关于这一点，在一些专（业数学）家和四色爱好者给他提出了他并没有证明以后就不会再有别的构形这一问题之后，他才在《归纳法》一文中补充了一个所谓的“证明”。但这个“证明”是不能含人满意的。按他那样的“证明”办法，第八构形后就不可能再有第九构形了，我们也可以仿其“证明”方法，证明在第七、第六构形后也再也没有第八、第七构形了，一直到得出没有任何构形存在为止。
当张先生发现敢峰—米勒的图（Z4构形）用颠倒法着色，出现了无限循环，不能用颠倒法进行着色时，就又增加了一个第九构形，其解决的方法又是截然的与前面八个构形的解决办法大不相同。这能叫“构形最简，解法相同”吗。当在出现了解决不了的构形时，就又再增加一个构形，这能说明你这个构形集是完备的吗。这是什么分类原则嘛。如果以后再遇到了别的构形用颠倒法再不可4—着色时，你是不是还要继续把你的构形集增大呢。你敢断定以后就再也没有别的构形出现了吗，颠倒的次数就不会再增加了吗。其实你的构形集里已经出现这样的问题了：第九构形的出现，就是你自已对你自已前面的“颠倒次数不会再增加”了的一个否定。
在张先生的构形集中，说是“构形最简，解法相同”，其实解法并不是相同的，前八个构形用的是“颠倒法”，而第九个构形用的则是所谓的“Z—换色程序”，这能叫“解法相同”吗。如果张先生能把他的第九构形（Z4构形）归为有环形链A—B的Z1（即我这里的图1，a和图6，a）类构形；或者把Z4归为有环形链C—D的Z2（即我这里的图1，b和6，b）类构形；把第八构形与第一构形，第三到第七构形划归为一类；再把“构形最简，解法相同”的分类原则改成“结构不同，解法不一”，或者就直接是根据构形“结构不同”的原则对构形分类，则就能够证明在这些构形以外，再也没有别的构形了。这样，这个不可免的H—构形集中，就只能有形如图6，a，图6，b和图6，c三种H—构形了。再加上上面我们已经证明了它们都是可约的，也就可以说明四色猜测是正确的了。这就与我们在前面“1、H—构形的特征：”中提出的“只要能证明这三种情况的H—构形都是可约的，那么，四色猜测也就可以得到证明是正确的了。”的假设是相符的了。
雷  明
二○一七年二月十四日于长安

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

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，