对张彧典先生连续颠倒法的深入研究——重读《四色问题探秘》一书的体会（一）

雷明85639720

对张彧典先生连续颠倒法的深入研究
——重读《四色问题探秘》一书的体会（一）
雷  明
（二○一八年元月九日）

我过去曾多次说过，张彧典先生的连续颠倒法也是一种好的着色方法，现在我仍然认为是这样。因为用这种方法着色时，可以不要对已着色部分的图的构形结构以及链间的相互关系进行分析。特别是在图中顶点很多、链间的相互关系难以分析清楚的情况下，我们就直接用一个方向的赫渥特颠倒，一直交换（颠倒）下去就行了。总有时候颠倒不下去了，构形也就成了可约的K—构形，问题也就解决了。待着色的顶点一定可以着上图中已用过的四种颜色之一。但重要的问题是需要证明：第一，对任何图是否都可以这样进行连续的颠倒；第二，这种连续颠倒是有限次的，还是无限次的；第三，在有限次颠倒内，最多只需要颠倒几次。这就是本文提出的研究目标。
1、英国的米勒等人首先提出了赫特颠倒这一术语
赫渥特颠倒，原是张彧典先生在他二○一○年出版的《四色问题探秘》一书中，介绍英国人米勒的文章《理应已知的赫渥特范例》（该文是米勒1990年写的，1992年在英国发表的，张先生是1999年才看到该文的）一文时，在介绍米勒用这种方法对赫渥特图在原赫渥特着色的基础上进行着色时，说是米勒提出的。这种方法实际上还是属于坎泊的颜色交换技术，也是把一条链中的各顶点已着的颜色进行交换而已。不过赫渥特颠倒这一交换方法只是单从赫渥特图中与待着色顶点相邻的两个着相同颜色B的顶点之一交换的，且每次颠倒都是一直沿一个方向不变的进行交换的。只是坎泊的颜色交换技术中的一种应用。也并不是什么稀奇的东西。因为可以同时移去两个同色B的空出颜色的交换，就是从两个同色的顶点B开始交换的。
用这种方法在赫渥特原着色基础上对赫渥特图进行了4—着色的还有我国的董德周先生，雷明先生等，时间也是在1990年前后。
从米勒的文章中可以看出，他们并没有注意到该方法的实质，只看到用该方法连颠倒两次，就可以给赫渥特图进行4—着色，就心喜若狂，这是可以理解的。因为一个多世纪一直认为不能4—着色的赫渥特图终于可以4—着色了，当然也就是一件了不起的事情。他们已经看到了解决四色问题还是大有希望的。于是米勒他们就有了用这种办法解决四色问题的企图，但当他们又构造了米勒图之后，认为该图即就是进行无穷次颠倒后，也不能使图变成坎泊的K—构形，所以就又取消了想解决四色问题的这一念头。
说来也巧得很，什么事情也都是成双出现的。米勒在1990年构造出米勒图的前后，也有我国的敢峰先生几乎是在与米勒的同时，也单独的构造出了这样的一个图，并且能够对其进行4—着色，而米勒们却不能做到这一点。也正因为是这样，我才把该图叫做敢峰—米勒图。
后来在米勒的赫渥特颠倒的基础上，我国的张彧典先生把这个赫渥特颠倒进行了发展，发展成了连续多次的颠倒（张先生把赫渥特颠倒称为H—换色程序，而把他在赫渥特颠倒基础上发展的多次连续颠倒称为Z—换色程序），构造了他的八个需要多次连续颠倒才能解决的构形（图）和一个无穷循环颠倒的无穷循环构形（图）。这就是张先生的九个构形。张先生的图从简到繁，顶点越来越多，以致到后面的图就根本看不出什么头绪来，更是难以理出构形的结构来（做为证明时的构形，应该能清楚的看出构形的结构来）。张先生只看到了他用连续颠倒的方法对他那几个图最后都能4—着色，却没有看到它的这一方法的本质内容，只看到的是表面现象。所以他就解决不了我在文章开头提出的那三个问题，且在他的《探秘》一书中根本就不提这一问题。
我的这篇文章主要是来谈张先生的连续交换法的本质问题的。只有看到了这一方法的本质问题，才能更好的利用这一方法来为着色，为研究四色问题服务。米勒就是因为没有看到他的颠倒方法的本质和米勒图的本质，才使他放弃了企图解决四色猜测的目标，太可惜了；敢峰和张先生也是没有看透颠倒法和敢峰—米勒图的本质问题，也只看到了该图每次连续颠倒后的图中都有一条环形的A—B链，所以就简单的认为只要在这个环形的A—B链内、外交换C—D链，就可以解决问题。所以，张先生就又在他的Z—换色程序的基础上，又“创造”了Z＇—换色程序。单独的把这个Z＇—换色程序用在了解决所谓连续颠倒出现无穷循环的图米勒图上，把米勒图单独列为一种构形。在米勒图的几次颠倒后的图中，都有A—B环形链，这只是一种表面现象，其实质则是在米勒图（即我的a类H—构形）与赫渥特图型的H—构形（即我的b类构形）间通过颠倒交换，发生着相互不断循环的转化。米勒图中不但有环形的A—B链，而且还有环形的C—D链，颠倒后的图中却只有环形的A—B链，而无环形的C—D链，且这时的环形链A—B只相当于赫渥特图中的C—D链，并不是颠倒前的A—B链。
2、对待任何事物，一定要看到它的本质，不要只看表面现象
以前人们研究赫渥特图时，也只是看到了赫渥特着色时的表面现象，而没有看到赫渥特着色时的本质错误，就盲目的认为赫渥特图是一个“反例图”。请问，是那方面的“反例”呢，并不明白，也没有人能说得清楚。一个多世纪以来人们只看到赫渥特从顶点1开始交换r和g，但这空不出r给v，因为与v相邻的顶点3也是着色r的。显然这可以变到一个y。“但如果我们试图这样从3开始沿r—y链交换y和r，那么6和7都变成r。这样就可能使得每次交换移动一r，但仍不能同时移去两个r。”（聂祖安翻译的《图论的例和反例》一书中的原话）。这就是一个多世纪以来人们的认识。对不对，不对，是错的。这是只看到了表面的现象，而没有真正看到其真正的本质。
本质是什么呢。本质就是坎泊的颜色交换技术，交换的链对五边形来说，应是一条不连通的对角链，然而赫渥特也正是违反了这一点。一个多世纪以来人们却一直跟着赫渥特转，这还能空出颜色给待着色顶点v吗。本来从顶点1交换了r—g链以后，图中就已经产生了从顶点3到顶点5的连通的r—y链，这时他还要硬从顶点3开始交换r—y链，这怎么能行呢。顶点6与顶点7都成了r，这只是表面现象，而其实质的原因，还是因为从顶点1交换了r—g链以后，新产生了从顶点3到顶点5的一条连通的r—y链。请看，“要看本质，不要只看表面现象”重要不重要。就这一点点地方没有弄明白，耽误的就是整整一个多世纪的时间呀。雷明，董德周在1990年前后，还有后来张彧典先生在2010年以前后，也都看到了这一实质。所以他们就能很快的分别用不同的方法对赫渥特图在赫渥特原着色的基础上进行4—着色，且方法均不止一种，均可以着成多种不同的4—着色模式。
张先生的连续颠倒法的本质是什么呢。我们通过学习，看出了他在解决各构形时，最后一次颠倒后都有这么一句话：“生成新的×—×环”，这个“环”都是经过了五边形上的三个顶点，并与待着色顶点v共同构成的环。这三个顶点中有两个顶点是两个同色的顶点，另一个是别的顶点。

比如张先生对他的第一构形进行了逆时针第一次颠倒后，得到如图1，a的图，这里的“新生成的A—D环”（图中的加粗边）是经过了五边形的两个着D色的顶点和一个着A色的顶点，并与待遇着色顶点v构成了一个环。再要进行同方向的颠倒，交换D—A链时，实际上交换的是一条连通链，只是把着有A、D二色的顶点的颜色交换了一下，仍有以上的A—D环存在，只是着A色和着D色的顶点的位置发生了变化（如图1，b）。这时就可以认为不需要再继续颠倒下去了，因为图已经变成了一个K—构形了。再交换新生成的A—D环内、外的B—C链，空出B或C给待着色顶点（如图，c和图1，d。图1，d对于第一构形原图来说，就是同时移去了两个同色B）。颠倒结束。
以后，张先生对各个构形（图）的最后解决，也都是这样的在新生成了×—×环之后，再进行一次别的空出颜色的交换就可解决问题。但现在问题出来了，张先生在“生成新的×—×环”后，又都有一个括号，其内写：“生不成情形归于下一种构形”。从第一构形到第七构形的后面都有“下一种构形”的存在，但到了第八构形时，虽然同样的也说了这同样的一句话“生不成情形归于下一种构形”，但其后却没有下一个有限颠倒次数的、同样是用连续颠倒来解决的构形了，而在其后紧跟着的却是一个所谓颠倒次数无穷多的米勒图（即第九构形）。“生不成情形归于下一种构形”这句话，在张先生所研究的前八个构形中，那一个构形中还都得要说，否则就联系不上下文了；但不说还又不行，因为张先生所研究的八个构形中，的确各构形后面还有“下一种构形”存在。
虽然在第八个构形后面也说了这样的话，但其后却看不到“下一种构形”，这不能不是一个缺陷。怎么办，老是这样“下一种构形”、“下一种构形”下去，什么时候是个头呢。没办法，张先生就只有按照他“创造”Z—换色程序时提出的“四次换色小循环，八次换色大循环”的理论，也凑够了一个看不明白画图时是按照什么规律、却分别需要1到8次颠倒的图（构形）而结束，而在其后紧接着增加了一个所谓无穷次颠倒都不能解决问题的“无穷循环构形”（其实原来在张先生的构形集中，就只有八个构形，只是在1999年见到米勒图时，无法用他的Z—换色程序进行解决，所以才在原有八个构形之后，再增加了一个第九构形——米勒图）。如果说张先生认为在第八构形后，再也没有“下一种构形”了，那么就得进行证明才是，而且要证明为什么在第八构形之后，就再没有“下一种构形了”。我们在文章刚开头时提出的问题在这里又一次出现了。这也就是网友们提出张先生没有对他的不可免构形集进行是否完备的证明的实质所在。但张先生如果要是想证明，也的确有难处。证明第八个构形后面再没有别的构形了吧，的却又有一个米勒图是无穷颠倒的；说后面还有很多吧，他就又不可能得到一个有限的H—构形的不可免集。无耐，他只好在满足了“八次换色大循环”之后，也不进行任何证明，又加上了一个无穷循环的米勒图，才构成了由九个构形组成的不可免集。
3、结张先生构形的一一解说
3、1  构形1，在上面的2中已经说过了，进行一次逆时针颠倒后就变成了DCD型的构形，新生成了A—D环，颠倒结束。
3、2  构形2（如图2，a），进行一次逆时针颠倒后如图2，b，进行第二次颠倒后如图2，c，图变成了ABA型的构形，新生成了C—A环，颠倒结束，最终空出了B给v（如图2，d）。一共用了三次交换，其中两次交换是颠倒。
从图2，a中可以看出，该构形是左右对称的，所以进行逆时针方向和进行顺时针方向的颠倒，结果都是相同的。从图2，a中还可以看出，图中有一条环形的C—D链，是把A—B链分隔成不连通的两个部分的。所以就可以交换C—D环形链内、外的任一条A—B链，都可以使连通的A—C链和A—D链同时断开，使构形变成K—构形而可约（如图2，e），至少可以空出A、C、D三色之一给V（如图2，f）。这样的着色方法只用了两次交换，比张先生的方法少用了一次。赫渥特图的简化——留下主要的顶点，去掉非主要的顶点之后，就是如图2，a的九点形构形，所以赫渥特图也是可以用以上解决第二构形的两种方法进行着色的。

3、3  构形3（如图3，a），是一个与第一构形只是左右不同的构形，本来可以只要进行一次顺时针颠倒，就可以转变成K—构形而可约，同时移去两个同色B。但张先生却硬要进行逆时针颠倒，结果是用了三次颠倒后，图才变成了CDC型的K—构形（如图3，d），新生成了B—C环。加上一次别的空出颜色的交换，共四次交换。

从图3，b中我们还可以看到，这个图在进行了一次颠倒后，就是一个DCD型的含有A—B环形链的构形（如图3，b），与图2，a的第二构形具有完全相同的特征。在环形的A—B链内、外任意交换一条C—D链，就可以使图变成K—构形而可约（图3，f）。这说明第一构形，第三构形，都是可以转化成第二构形的；从图2中也可以看出，第二构形是可以转化成第一构形和第三构形的；可见第一构形（包括第三构形）与第二构形是可以相互转化的。
3、4  构形4、5、6、7四个构形，本来都与构形3有相同的特征，即顶点3与顶8都是直接相邻的。都可以进行一次顺时针颠倒，从顶点3开始交换B—C链，而不会再生成从顶点1到顶点4的连通的B—D链，从而可以同时移去两个同色B。但张先生却固执的还要进行逆时针颠倒，却分别进行了四次、五次、六次和七次颠倒，才分别生成了有新的D—B环、A—D环、C—A环和B—C环的、分别为BAB型、DCD型、ABA型和CDC型的K—构形，分别进行了五次、六次、七次和八次交换才空出了颜色给待着色顶点V。不知张先生为何要取少求多，舍近求远呢。
3、5  构形8与别的构形则不同，虽然与构形1和构形3有相同的特征，其中的A—B链和C—D链都是直链，但却不和这两个构形一样，通过一次颠倒，就可同时移去两个同色B。张先生用了八次颠倒，才变成了一个有新生D—B环的BAB型的K—构形，共进行了九次交换，也才空出了颜色给V。其实这个构形，从左边的B色顶点进行了第一次逆时针颠倒后，就变成了一个DCD型的有一条A—B环形链的类似构形2的构形，可以交换环形的A—B链内、外的任一条C—D链，使图变成K—构形而可约（如图4）；另外，这个构形也可以从右边的B色顶点进行一次顺时针颠倒后，变成一个CDC型的可以同时移去两个同色C的K—构形，再交换两次就可以空出B给V（如图5）。两种办法最多都是三次交换就可以解决问题了。






我们从图1，a和图1，b，以及图3，a和图3，b都可以看出，第一构形和第三构形也分别从一个B色顶点进行了颠倒后，变成可以同时移去两个同色B的K—构形；而从另一个B色顶点进行了相反方向的颠倒后，却变成了类似于第二构形的构形。所以说，第一构形和第三构形都是属于第八构形一类的构形。
    4、连续颠倒着色法本质的进一步深入研究
以前我们曾多次说过，张先生的连续颠倒法是一种着色的好方法，而且在本文的开头也再次重复过了。在图中关系很复杂时，可以不要去分析图中链的结构，直接的进行连续颠倒就行了。但在图的顶点很多时，一下子又不可能直接看出是否新生成了经过五边形三个顶点的×—×链时，该怎么办呢。这的确是一个问题。现在我们再看，最开始的构形若是BAB型时，在颠倒的过程中只能生成DCD型、ABA型、CDC型和BAB型四种构形，当出现了有经过五边形三个顶点的×—×链时，如果再向下继续颠倒，则一定会出现以上四个类型以外的构形类型，这时我们就可以认为颠倒已经结束，可以最后解决问题了。这时构形的峰点颜色及位置都没有改变，而只是改变了峰点两侧顶点的颜色。这实际上相当于把图中的某两种颜色的顶点颜色对调了一下，构形还是没有任何变化的。
比如第八构形顺时针第二次颠倒后的图5—b，就有一条经过了五边形三个顶点的D—A链，构形类型是ABA型，峰点是B色。继续再进行顺时针颠倒后，得到图6。可见图6的构形类型是DBD型，不同于以上的四种类型的任一种，峰点仍是B色，峰点位置也没有变化。因为这一构形类型的变化，是表现在五边形的顶点上的，是容易看出的，所以，这时也就可以认为颠倒结束了。

一个问题解决了，下一个问题又来了。接下来该交换哪种链才能空出颜色呢，这的却又是一个新问题。但我们还是有办法解决它。图6中已进行过的颠倒也不要再返回去了，原来是有经过五边形三个顶点的D—A链，现在同样是有经过了五边形那三个顶点的A—D链，在这三个顶点之外的两个顶点上，随便的进行交换，都可以使构形变成K—构形而可约。如图7和图8。


现在我们已经把连续颠倒着色的方法和分析都说清楚了。就剩下最后一个问题还需要进一步解决。这就是颠倒到什么时候才是头呢，有没有永远也颠倒不完的图呢。下面我们来接着继续分析。
5、任何H—构形都可约的证明
现在，张先生的“构形最小”理论排上用场了。所谓的“构形最小”就是能够用最少的顶点来描绘某种构形的结构特征的图。比如本文前面的图2，a就是一个代表了类似赫渥特图的一类图的一个总的代表图，它就是在证明过程中要使用的“构形”。图的顶点数再多，再复杂，只要有了图2，a的特征，就都是同一种类型的图（构形），都可以用图2，a来代表。还要进一步明白这“证明”与“着色”可是不同的两回事。“着色”是对一个个的“具体”的图进行的着色。但由于图中的顶点多，关系复杂，是很难分辨出各链间的关系的，也是很难确定一个图是属于某类型构形的。所以我们才认为连续颠倒的着色法比较实用，不用分析图的结构和明确构形的类型，就可以使用的着色方法。但“证明”可就不一样了，证明时，是要明确各类型构形的结构特征的，只有这样才能找出对应的解决办法的。这就是“解法不同”。所以在证明时，就得用顶点数最少，但又能反映出某种构形的结构特征的图。即要使用能够看明白构形中链与链之间的相互关系的图。这就是最小构形的图，即“构形最小”。九点形就是H—构形的“最小构形”。

只所以H—构形不能通过一次或两次交换，空出颜色给待着色顶点V，就要是因为图中含有中途又相交叉的A—C和A—B连通链。于是我们首先想到的就是破坏这两条链的连通性，即断链。使其变成不连通的。对于任何H—构形，其中A—C链，A—D链都是不可交换的，因为它们都是连通链，交换了也空不出颜色来，所以不可能空出A、C、D三种颜色中的任何一种来。B—C链和B—D链又不能同时交换，也不可能空出颜色B来。那么可交换的链就只有A—B链和C—D链了。但这两种链正好是一对相反链，所以两链又是不会相交叉的。如果有了经过五边形1B、2A、3B三个顶点和顶点8A的A—B环形链，就不会再有经过五边形5C和4D两个顶点和顶点6C和7D的C—D环形链。反之亦然（如图9）。这两种环形链，只要有了一种，就绝对不会再有另一种。因此这两种链在构形中的相互关系只能是：有A—B环形链的构形；有C—D环形链的构形；和无任何环形链的构形三种。
6、1  当构形中有经过五边形1B、2A、3B三个顶点的环形的A—B链时，不管这条环形链是从什么地方穿过连通的A—C链和A—D链的，该A—B链环的外侧总是存在着一条经过五边形4D和5C两个顶点的C—D链（如图10，a），交换这条C—D链，一定是可以同时使连通的A—C链和A—D链断开的（如图10，b），因为这两条链的末位顶点的颜色均已改变了。这一种类的构形我叫他a类H—构形。

a类构形中还有一种形如上面图9，a的特殊构形，这种构形却是一种可以同时移去两个同色B的构形。无论先从那一个B色顶点交换B—C或 B—D，都可以同时移去两个同色B。他不象张先生的构形1和构形3那样，先交换的B色顶点一定要选择好，否则，交换错了，就不可能同时移去两个同色B，或者转变成下面的b类构形。但a类构形可不一定都是可以同时移去两个同色B的构形，因为图10的图中，从任一个B色顶点交换B—C（或B—D）后，并不能堵绝可能从另一个B色顶点到其对角顶点生成新的B—D（或B—C）连通链的可能性。
6、2  当构形中有经过五边形4D和5C两个顶点的环形的C—D链时，不管这条环形链是从什么地方穿过连通的A—C链和A—D链的，该C—D链环的内侧总是存在着一条经过五边形1B、2A、3B三个顶点的A—B链（如图11，a），交换这条A—B链，也一定可以同时使连通的A—C和A—D链断开的（如图11，b），也是因为这两条链的首位顶点的颜色均已改变了。这一种类构形我叫他b类H—构形。

以上6、1和6、2中所用的交换都是为了以断开连通的A—C链和A—D链为目的的，而不是为了空出颜色，所以我们叫他“断链交换”。这种交换是可以不从五边形的任何顶点开始的交换。这是坎泊的颜色交换技术的第二种作用。

6、3  当构形中没有任何环形链时，这就是张先生第八构形的代表。有如图12的两种情况，但这两种情况也只是左右的不同，实际上还是同一类构形。这种情况前面已经说了，既不能交换A—C和A—D，也不能交换A—B和C—D，只能进行颠倒（转型交换）了。无论是从那个方向进行转型交换（颠倒），都可以变成可同时移去两个同色B的K—构形，或者是变成类似于第二构形的构形（即图11中的构形，也即上面的b类构形），都是可约的。这一种类构形我叫他c类H—构形。这里的交换，目的只是为了使构形转型，所以我们叫他“转型交换”。这一交换必须是从五边形的任一个B色顶点开始的。这是坎泊的颜色交换技术的第三种作用。
现在各种情况已经全分析完了，也就证明了由以上a、b、c三类构形构成的H—构形的不可免构形集是完备的。他们也都是可约的，所以也就证明了四色猜测是正确的。现在就可以来回答我们在上面“4、连续颠倒着色本质的进一步深入研究”中最后提出的“颠倒到什么时候才是头”的问题了。
6、不存在无穷颠倒的图
虽然在5中证明了“任何H—构形都是可约的”，那么就可以说明完全没有无穷颠倒的图存在。虽然在5中我们已经证明了a、b、c三类构形中，每一种构形最多只要通过三次交换就可以从五边形中空出一种颜色给待着色顶点。但是我们在用颠倒法给一个复杂的图着色时，会不会产生无穷颠倒的情况呢。我们说，不会的。现分析如下：
第一，如果有无穷颠倒，那么这个图必然就不能进行4—着色，可这是不可能的，我们已经证明了任何构形的图都是可约的，都是可以4—着色的。这种矛盾现象是不会发生的。
第二，从循环上看，有构形类型的循环，有构形峰点位置的循环，不能笼统的只提出循环二字。构形类型的循环，逆时针颠倒时，是以BAB型、DCD型、ABA型、CDC型和BAB型为序进行循环的；而顺时针颠倒时，则是以BAB型、CDC型、ABA型、DCD型和BAB型为序进行循环的；都需要四次颠倒才能做到一次循环。所以构形类型的循环周期是4次颠倒。而构形峰点位置的循环则是进行了一次构形类型的周期循环后，BAB型构形的峰点A才从顶点2转到了顶点5，BAB型构形的峰点A再经过一次构形类型的周期循环后，才能到达顶点3，再经过第三次构形类型的周期循环后，到达顶点1，第四次构形类型的周期循环后，到达顶点4，最后第五次构形类型的周期循环后，BAB型构形的峰点A到达最开始的顶点2。这时图中所有顶点的着色也都与最开始时成为相同的了。每一次构形类型的周期循环都是4次颠倒，构形峰点位置的一次循环，需要五次构形类型的循环，那么一个构形峰点位置的循环周期就是4×5＝20次颠倒（4和5的最小公倍数是20）。但颠倒到二十次时，图又回到了原来开始时的状态，等于这二十次颠倒如同没有进行一样。所以说，采用颠倒法着色时，最多的颠倒次数一定是会小于二十次的。如果说正好是第二十次交换空出了颜色来，那么最多就只颠倒了十九次，因为最后一次交换是空出颜色的交换，并不是真正意义上的颠倒，所以实际上只有十九次颠倒。20次颠倒还可以这样理解：图中共用了四种颜色，构形峰点把每种颜色都用一次，需要四次颠倒；待着色顶点有五个相邻顶点，构形峰点在着某种颜色时，把待着色顶点的每个相邻顶点都走遍一次，也就得需要4×5＝20次颠倒。但实际上任何图，从开始颠倒起到空出了颜色给待着色顶点着上止，颠倒的次数是远小于20次的。
这就说明了根本不存在无穷颠倒的图。

（未完，接下贴）

雷明85639720

，，，，，，，，，

雷明85639720

你跑到这里来干什么呢？

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

快滚开点。