话说四色问题——研究四色问题三十年之总结（二）

雷明85639720

话说四色问题（二）
——研究四色问题三十年之总结
雷明
（二0一六年四月三十日）

（接上贴）
16、把无穷问题变成了有究问题：
用坎泊的交换方法用于证明四色猜测时，主要是交换构形的轮沿顶点间的不连通链，以达到改变轮沿顶中某一顶点的颜色，把空出来的颜色给构形的待着色顶点着上，这叫构形可约。只要不可免构形集中的各个构形都是可约的，就可以说证明了四色猜测就是正确的。这就把四色问题这个无穷的问题（平面图的顶点可以是无穷的，平面图的种类也是无穷多的）转变成了一个有穷的问题了。就不需要再对图中无穷多的顶点，无穷多的图，或无穷多的构形进行一一的研究了。用坎泊所创造的颜色交换技术在证明轮沿顶点数不大于4的轮构形时，都是可以顺利的解决问题的。

但到证明5—轮构形时，情况就比较复杂一些。5—轮构形的五个轮沿顶点占用完了四种颜色时，必有两个顶点是着了同一种颜色的（即有一种颜色是用了两次的），不同于4—轮构形的轮沿顶点占用完了四种颜色时，一个轮沿顶点用一种颜色的情况。我们用A、B、C、D代表四种颜色，设5—轮构形的5个轮沿顶点占用完了四种颜色的情况中，用了两次的颜色是B，两个B之间所夹的颜色是A，其余两顶点所着颜色分别是C和D。这样的构形张彧典先生称之为双B夹A型5—轮构形（如图5）。坎泊只证明了连通链A—C和A—D，两链有同一个起点A，但中途不再相交叉的情况，是可以同时移去两个B给待着色顶点的（如图6）；也证明了有连通链B—C和B—D，两链虽无共同起点，但中途却有交叉顶点B的情况，可以分别从A，C，D三个顶点开始进行交换，空出A，C，D三色之一给待着色顶点着上（如图7）。但坎泊并没有证明连通链A—C和A—D既有同一个起点，而中途又相交叉的这一情况（如图8），就认为他已经证明了四色猜测是正确的了。

正好，赫渥特所构造的图就是含有连通链A—C和A—D，两链既有同一个起点A，且中途又相交叉情况的图。两链的共同起点和相交叉顶点均着A 色（如图9的由赫渥特图简化而来的“九点形”图）。当年赫渥特和坎泊都是不能给该图进行4—着色的。该图的待着色顶点就是这个5—轮构形的中心顶点，该顶点如何着色，请看下面的17和18。赫渥特图的4—着色，虽然有不同的方法，但仍然用的是坎泊所创造的颜色交换技术。
17、赫渥特图的4—着色方法之一（雷明的方法）：
雷明和董德周是用“断链法”对赫渥特图着色的（雷明，1990年着色，1992年在陕西省数学会第七次代表大会暨学术年会上作学术论文报告）：赫渥特图中除了有A—C和A—D两条连通且交叉的链外，还有一条环形的C—D链，该链把A—B链分成了环内、环外两个互不连通的部分，正好两链的两个相交顶点A也分别位于C—D环的两侧，从两连通链的任一个相交顶点A起交换一部分A—B链，都不会影响到另一部分A—B链，但却都可以使原来的两条连通链A—C和A—D均从该顶点“断开”，变成一个含有两条没有共同起点的连通链B—C和B—D，但两链中途又相交叉的构形，这是一个当年坎泊已经证明过的是可约的构形（如图10）。

然后，再从A，C，D任一顶点交换，都可空出A，C，D三色之一，给待着色顶点着上。比如从顶点C交换C—A链，可空出C给待着色顶点着上。若从另一个相交顶点A起交换A—B链，图则变成如图11的双A夹B型图，则是可以移去B，C，D三色之一的，也可达到同时移去两个同色B的目的。用这一方法能给赫渥特图着色的还有刘福和郑敏等。
这一方法的实质就是：既然各链都是连通的，不能交换；即就是交换了不连通的链，也不能同时移去两个同色B；那么就只有想办法把连通链变成不连通的；再进行别的交换，空出颜色给等待着色顶点着上。所以叫做“断链法”。
18、赫渥特图的4—着色方法之二（米勒和张彧典的方法）：
张彧典和米勒是用“赫渥特颠倒法”对赫渥特图着色的（米勒，1990年着色，1992年英国牛津大学《数学季刊》第二期刊出）：从双B夹A型左边的一个B交换B—D链，构形就变成了一个双D夹C型的5—轮构形，这时图中虽仍有两条连通且相交叉的链C—A和C—B，但这时的图已是一个可以同时移去两个同色D的构形了（如图12）；

继续从双D夹C型左边的一个D交换D—A链，构形又变成了一个双A夹B型的5—轮构形，这时图中就只有一条链通链B—C，是一个普通的5—轮构形的图（如图13）。图13的两个图初看上去好象不同，实际上它们是同一个图，因为图中顶点间的相邻关系是相同的。
这时，从顶点D交换D—B链，可以空出D给待着色顶点着上（如图14，说明了图12的双D夹C构形是可同时移去两个同色D的）；也可以从双A夹B型的B交换B—D链，空出B给待着色顶点着上（如图15，最终还是移去了图9中的两个同色B）。


请读者注意：张先生和米勒的这种交换方法，实质上就是：不能同时移去两个同色B，总可以先移去一个B，使构形转变类型，从双B夹A型转变成双D夹C型。再若不能同时移去两个同色D时，就再先只移去一个D，再进行转型（实际上，这里第一次转变成的双D夹C型就是一个可同时移去两个同色D的构形）。在两次“颠倒”后得到的图中，就只有一条连通链了，是一个普通的5—轮构形。
该方法前两次交换都是从双x夹y型左边的一个x进行交换的，x顶点的变化和选取，在图中是逆时针方向旋转的，所以叫做“逆时针赫渥特颠倒”，当然了，相应的也就应有“顺时针赫渥特倒”。所谓“颠倒”仍是交换的意思，颠倒者即交换也。其实质上还是坎泊的颜色交换技术。至于为什么叫“赫渥特颠倒”，大概这种方法是米勒在对赫渥特图的着色过程中总结出来的原因吧。因为该方法在别的有两条连通且交叉的链的5—轮构形的图的着色时也是可用的，所以把含有这样有A—C和A—D连通且相交叉链的这一特征的图都统一叫做赫渥特构形的图。
还要请读者注意的是：在确定了“颠倒”的旋转方向后，以后再继续“颠倒”时就不要再改变旋转方向了，否则，再进行的“颠倒”，就是上一次“颠倒”的反方向，图又会转变回去。如上面的第二次“颠倒”，若不是从左D进行交换，而是从右D进行交换，则构形又会转变成原来的双B夹A型。有关“颠倒”等这方面的问题，可见张彧典先生的《四色问题探秘》一书和他对他的“九构形”的着色。不过，张先生的第五到第八构形，实际上在进行了少量（如三次）的颠倒后，图就已经变成了普通的5—轮构形的图了，是完全可以给待着色顶点着上图中已用过的四种颜色之一了。但张先生好象是为了凑够他所说的颠倒的次数，有意的多进行了几次颠倒。
19、赫渥特为什么不能对他的图进行4—着色：
赫渥特和坎泊当年为什么就不能对赫渥特图进行4—着色呢。他俩虽然都知道交换只能交换不连通链才能空出颜色，而交换了连通链是不能空出颜色来的。但他俩却正好是违反了这样的交换原则，当然是不能空出颜色给待着色顶点的。由于A—C和A—D都是连通链，他们认为是不能空出A，C和D来的，就一心只想空出B，因为B—C和B—D链都是不连通的。但当他们从双B夹A型左边的一个B交换了B—D链后，就不假思索的又从右边的B再交换B—C链，结果得出的结论却是：即使每次交换都可移去一个B，但却不能同时行移去两个B（如图16）。从而得到赫渥特图是不可4—着色的，也就否定了坎泊的证明方法。但他们没有看到，他们在从左B进行了B—D链的交换后，便产生了从右B到C的连通链B—C，这时他们再交换B—C链不就是违反了不能交换连通链的原则了吗（也见图16）。

赫渥特的这一错误可以说一直从赫渥特与坎泊时代起，直到现在还在持续着。因为除了几个能给赫渥特图4—着色的爱好者发现了这一错误外，在数学界里是没有人发现的。现在的文献资料上还都是在介绍着“即使每次交换都可移去一个同色，但却不能同时行移去两个同色”的错误论调。许多文献资料上还把赫渥特图和赫渥特图的简化图——“九点形”图作为反例，仍认为该图是不可4—着色（不可约）的，仍在继续的贻害着读者。
唯一有赫渥特图4—着色模式的文献是中央民族大学的许寿椿教授的《图说四色问题》一书，书中有他们用计算机，用“算法”给赫渥特图着色的两个模式。但该书是一本关于四色问题的普及读物，并不涉及四色猜测的证明问题。所以也就只字未提及他们是如何对赫渥特图进行了4—着色的问题，而且也没有必要提。想提也是没有办法提的，因为是用电子计算机着的色，着色的过程是无法显示在书面上的。由于这样的原因，所以许教授的书在说明赫渥特图是可4—着色的这方面的说服力并不是很强的，或许还没有引起更多的人的注意。因为许教授也并没有明确指出，为什么赫渥特不能对他的图进行4—着色，而他们却又能对其进行4—着色的原因。许教授给赫渥特图的4—着色的两个着色模式如图17。

20、赫渥特陷入了两种构形的无限转化的循环之中了：
在赫渥特从左B交换了B—D链后，图实际上已经转变成了一个可同时移去两个同色D的又D夹C型构形了（见上面18的图12）。如果不再去从右B交换B—C，而是从新变成的双D夹C型的左D进行D—A链的交换，这时图就转变成了一个只有一条连通链B—C的双A夹B型的普通的5—轮构形的图，就非常好着色了。这就是张彧典先生和米勒的着色方法——逆时针赫渥特颠倒法。张先生和米勒给赫持图着色时，就是用的这一方法。
在第一次交换后，若不是从双D夹C型的左D交换D—A链，而是从右D交换D—B链，这实际上就是第一次交换B—D链的相反交换，得到的仍是原来的赫渥特图（如图18）。可见选择第二次交换的顶点是一个关键，选择对了，就会得解；选择错了，就会再次反回到原图，不得其解。

这样的两步交换反映了：对不可同时移去两个同色B的双B夹A型构形，从左B（或右B）交换B—D（或B—C）链后，生成了可以同时移去两个同色D（或C）的双D夹C（或双C夹D）型，这种类型的图中已不再有任何环形链了，这是与原赫渥特不同的地方；而对可同时移去两个同色D（或C）的双D夹C（或双C夹D）型构形，从右D（或左C）交换D—B（或C—B）链后，又生成了不可同时移去两个同色B的双B夹A型，重新返回到了赫渥特图（也见图18）。
可见，以上两种构形是可以相互转变的。对这两类图，必须按各自的着色方法去处理，否则就会陷入无限的循环之中。很可能赫渥特就是陷入了这个无限循环的陷阱之中了。
21、赫渥特图的可4—着色并不能代替四色猜测的证明：
现在我们对赫渥特图的4—着色已经解决，应该说已经证明了坎泊所漏掉的那部分5—轮构形也是可约的，是不是就说明了四色猜测就得到了证明是正确的呢。看来还是不能的。为什么。因为在1990年左右，米勒在企图用他总结的“赫渥特颠倒”法解决四色问题时，又构造了一个米勒图（如图19的左上第一图），认为用他的“颠倒法”却出现了“循环现象”。
他对该图颠倒了四次，所得各图他也都不能进行4—着色。第四次颠倒后，他认为图又回到了原来的双B夹A型的米勒图（如图19的右下最后一图）。其实这最后一个图并没有恢复到原来的全部面貌，也并没有出现循环现象，现在的B夹A型中，各顶点的颜色，并不是最初时的B夹A型的颜色。真正要恢复到原来的面貌，可能需要进行20次颠倒，这也就是敢峰先生所说的二十次大演绎。
米勒图中除了含有连通且交叉的A—C和A—D链外，也有环形的C—D链；但是，另外也还含有环形的A—B链，把C—D链也分成了互不连通的两部分。该图也不能同时移去两个同色B。米勒用他的“颠倒法”“颠倒”的结果，所得到的图，他认为都是不能同时移去两个同色的构形。所以又放弃了他们企图用“颠倒法”解决四色问题的想法。那么，米勒图是不是就不能4—着色呢。请看下面22和23。

22、米勒图的着色方法一（雷明的方法）：
该图的特点上面21中已经说到了，这里不再重复。2010年末，我们象对赫渥特图着色一样，企图从两连通且交叉的链A—C和A—D的相交点A交换A—B链，以待连通链“断链”时，却总不能达到目的，得到的仍是一个与米勒图有一样特点的图。既然相交点不能“断链”，那么从非相交点“断链”行不行呢。因为图中的C—D链是被环形的A—B链分隔成互不连通的两个部分的，交换一部分C—D链，也是不会影响另一部分C—D链的。这样也应该说能够使得A—C和A—D链断开的。

果然这样交换后，原来的连通链A—C和A—D的确“断开”了，虽又重新产生了两条连通的A—C和A—D链，但这两条连通链虽有共同的起点，但中途却不相交叉（如图20的左图）。这是一个普通的5—轮构形的图，是可以同时移去两个同色B的（如图20的右图）。我把上面对米勒图的这种着色法也叫“断链法”。
米勒之所以认为该图不可4—着色，就是因为他对该图从左B进行了B—D链的颠倒后，图变成的是一个双D夹C型的赫渥特图，图中也只有一条环形的A—B链（见图19的右上图）。当他再对这个双D夹C型的赫渥特图从左D颠倒D—A后，图又变成了一个双A夹B型的米勒图了，完全具有米勒图的特征（如图21）。以后再继续按原颠倒方向颠倒下去时，图均只是在赫渥特图和米勒图这两种构形间进行着循环的变化。米勒可能也是陷入了这样一个无穷循环的陷阱中了（见前面图19）。

23、米勒图的着色方法二（张彧典的方法）：
张彧典在他2010年10月出版的书《四色问题探秘》中说，他发现米勒对其图进行了三次逆时针颠倒所得的三个图，加上原的米勒图共四个图中，都共同有A—B环形链，于是就交换各图中A—B环外的C—D链，使构形成为普通的5—轮构形。张先生把这一方法叫“Z＇—换色程序”。
这一方法实际上就是上面22中的“断链法”。对于原双B夹A型的米勒图交换C—D就是从两连通链的非交叉顶点的“断链”，断链后虽又重新产生了两条连通的A—C和A—D链，但这两条连通链虽有共同的起点，但中途却不相交叉，这是一个普通的5—轮构形的图，是可以同时移去两个同色B的（见前面图22中的图20）；
在上面的22中已经说了，对米勒图进行一次颠倒后得到的图是一个双D夹C型的赫渥特图（如图22的左图），对这个图交换C—D链实际上就是对双D夹C的赫渥特图从两连通链C—A和C—B的共同起始顶点C进行的“断链”，断链后生成了有两条连通的C—A和C—B，但无共同起点，而是中途却相交叉的构形（如图22的右图），这也是一个普通的5—轮构形，是可以移去A，B，D三色之一的；

对米勒图进行了第二次颠倒后得到的图（见图19的中左图）交换C—D链的实质是与原米勒图交换C—D链的实质是一样的；对米勒图进行了第三次颠倒后得到的图（见图19的中右图）交换C—D链的实质是与对米勒图进行了一次颠倒后得到的图交换C—D链的实质也是一样的。张先生用这种“Z＇—换色程序”方法对米勒图进行着色，所得的到着色模式正好比雷明用“断链法”所得的着色模式少了一半。
24、另两种类型的5—轮构形：
以上我们主要讲了赫渥特图（已简化为“九点形”）和米勒图的着色。这两个图中除了含有连通又相交叉的A—C和A—D外，赫渥特图中还含有环形的C—D链，但不含环形的A—B链；米勒图中不但含有环形的C—D链，而且也含有环形的A—B链。那么在“九点形”图中，如果含有环形的A—B链时，也是一种类型的5—轮构形，该构形是一个普通型的5—轮构形，是可以同时移去两个同色B的，交换的先后次序也是没有要求的（读者可自已画图）。
还有一种5—轮构形，即在“九点形”图中，两种环形链A—B和C—D都不存在，这两种链都是直链，即都是一条道路。这就是我们在18中采用“颠倒法”对赫渥特“九点形”着色中进行了一次颠倒后得到的“九点形”图（见前面18中的图12），这种类型的5—轮构形中是没有环形链的。该图的着色，既不能交换A—B，也不能交换C—D，也只采用“颠倒法”了。但这个图的颠倒是不能随便进行的，这就是我们前面20中说的，如何选择好第一次颠倒的顶点，“是一个关键”问题。这个图，先从双D夹C型的左D交换D—A，再从右D交换D—B，就可以同时移去两个同色D给待着色顶点着上。我们把这种类型的5—轮构形叫半赫渥特构形。如果交换的次序错了，则图就会变成一个双B夹A型的赫渥特“九点形”图。而该双B夹A的“九点形”赫渥特图无论从那一个B交换，且无论是交换一次还是两次，图都会变成一个半赫渥特类型的图。可见赫渥特型的构形与半赫渥特型的构形正如上面20中说的，二者是可以相互转化的。因此，对半赫渥特构形着色时，选择先从那一个同色顶点进行交换，是关键的一步。
5—轮构形还有没有别的类型，目前看，各种情况都分析到了，好象是不会再有了。但也不能说绝对就没有了。因此也就有了下面25中的想法。
（转下贴）

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，，

雷明85639720

,,,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,,,

雷明85639720

,,,,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，