张彧典先生九个构形着色步骤浅析

雷明85639720

张彧典先生九个构形着色步骤浅析
雷  明
（二○一六年十一月二十一日）

    1、第一构形：
第一步：逆时针颠倒B—D，不生成连通的B—C链，构形不转化（张先生叫难点不转化），仍为BAB型；
第二步：交换B—C，空出B或C给待着色顶点V着上；
构形转化0次，逆时针颠倒一次，交换总次数两次；
顺时针颠倒与第三构形的逆时针颠倒正好相反，见后面。
2、第二构形：
第一步：逆时针颠倒B—D，生成了连通的B—C链，构形由BAB型转化为DCD型；
第二步：逆时针颠倒D—A，不生成连通的D—B链；
第三步：交换D—B，空出D或B给待着色顶点V着上；
构形转化一次，逆时针颠倒两次，交换总次数三次；
由于构形左右对称，所以顺时针颠倒与逆时针颠倒相同。也是构形转化一次，顺时针颠倒两次，交换总次数三次；
3、第三构形：
第一步：逆时针颠倒B—D，生成了连通的B—C链，构形由BAB型转化为DCD型；
第二步：逆时针颠倒D—A，生成了连通的D—B链，构形由DCD型转化为ABA型；
第三步：逆时针颠倒A—C，不生成连通的A—D链；
第四步：交换A—D，空出A或D给待着色顶点V着上；
构形转化两次，逆时针颠倒三次，交换总次数四次；
顺时针颠倒与第一构形的逆时针颠倒正好相反。也是构形转化0次，顺时针颠倒一次，交换总次数两次；
4、第四构形：
第一步：逆时针颠倒B—D，生成了连通的B—C链，构形由BAB型转化为DCD型；
第二步：逆时针颠倒D—A，生成了连通的D—B链，构形由DCD型转化为ABA型；
第三步：逆时针颠倒A—C，生成了连通的A—D链，构形由ABA型转化为CDC型；
第四步：逆时针颠倒C—B，不生成连通的C—A链；
第五步：交换C—A，空出C或A给待着色顶点V着上；
构形转化三次，逆时针颠倒四次，交换总次数五次；
顺时针颠倒与第三构形的顺时针颠倒相同。也是构形转化0次，顺时针颠倒一次，交换总次数两次；
5、第五构形：
第一步：逆时针颠倒B—D，生成了连通的B—C链，构形由BAB型转化为DCD型；
第二步：逆时针颠倒D—A，生成了连通的D—B链，构形由DCD型转化为ABA型；
第三步：逆时针颠倒A—C，生成了连通的A—D链，构形由ABA型转化为CDC型；
第四步：逆时针颠倒C—B，生成了连通的C—A链，构形由CDC型转化为BAB型；
第五步：逆时针颠倒B—D，不生成连通的B—C链；
第六步：交换B—C，空出B或C给待着色顶点V着上；
构形转化四次，逆时针颠倒五次，交换总次数六次；
顺时针颠倒与第三构形的顺时针颠倒相同。也是构形转化0次，顺时针颠倒一次，交换总次数两次；
6、第六构形：
第一步：逆时针颠倒B—D，生成了连通的B—C链，构形由BAB型转化为DCD型；
第二步：逆时针颠倒D—A，生成了连通的D—B链，构形由DCD型转化为ABA型；
第三步：逆时针颠倒A—C，生成了连通的A—D链，构形由ABA型转化为CDC型；
第四步：逆时针颠倒C—B，生成了连通的C—A链，构形由CDC型转化为型；
第五步：逆时针颠倒B—D，生成了连通的B—C链，构形由BAB型转化为DCD型；
第六步：逆时针颠倒D—A，不生成连通的D—B链；
第七步：交换D—B，空出D或B给待着色顶点V着上；
构形转化五次，逆时针颠倒六次，交换总次数七次；
顺时针颠倒与第三构形的顺时针颠倒相同。也是构形转化0次，顺时针颠倒一次，交换总次数两次；
7、第七构形：
第一步：逆时针颠倒B—D，生成了连通的B—C链，构形由BAB型转化为DCD型；
第二步：逆时针颠倒D—A，生成了连通的D—B链，构形由DCD型转化为ABA型；
第三步：逆时针颠倒A—C，生成了连通的A—D链，构形由ABA型转化为CDC型；
第四步：逆时针颠倒C—B，生成了连通的C—A链，构形由CDC型转化为型；
第五步：逆时针颠倒B—D，生成了连通的B—C链，构形由BAB型转化为DCD型；
第六步：逆时针颠倒D—A，生成了连通的D—B链，构形由DCD型转化为ABA型；
第七步：逆时针颠倒A—C，不生成连通的A—D链，构形由ABA型转化为CDC型；
第八步：交换A—D，空出A或D给待着色顶点V着上；
构形转化六次，逆时针颠倒七次，交换总次数八次；
顺时针颠倒与第三构形的顺时针颠倒相同。也是构形转化0次，顺时针颠倒一次，交换总次数两次；
8、第八构形：
第一步：逆时针颠倒B—D，生成了连通的B—C链，构形由BAB型转化为DCD型；
第二步：逆时针颠倒D—A，生成了连通的D—B链，构形由DCD型转化为ABA型；
第三步：逆时针颠倒A—C，生成了连通的A—D链，构形由ABA型转化为CDC型；
第四步：逆时针颠倒C—B，生成了连通的C—A链，构形由CDC型转化为型；
第五步：逆时针颠倒B—D，生成了连通的B—C链，构形由BAB型转化为DCD型；
第六步：逆时针颠倒D—A，生成了连通的D—B链，构形由DCD型转化为ABA型；
第七步：逆时针颠倒A—C，生成了连通的A—D链，构形由ABA型转化为CDC型；
第八步：逆时针颠倒C—B，不生成连通的C—A链，构形由CDC型转化为BAB型；
第九步：交换C—A，空出C或A给待着色顶点V着上；
构形转化七次，逆时针颠倒八次，交换总次数九次；
9、第九构形
这就敢峰—米勒图。
米勒颠倒了四次，构形转化了四次，认为出现了循环现象，没有再继续研究下去，取消了他们企图用颠倒方解决四色问题的想法；
敢峰对这种构形用了两种方法进行解决：第一，他发现A—B环形链分C—D链为互不连通的两部分，交换任一部分都不会影响另一部分，还可以使图变成坎泊构形而可约；第二，他对该构形继续进行一次“演绎”即“颠倒”，或者说“转型”，由BAB型 转化为DCD型或CDC型。发现仍有A—B环形链分C—D链为互不连通的两部分，交换任一部分都不会影响另一部分，也可以使图变成坎泊构形而可约（虽然他这时候并没有认识到演绎一次后的图，就是赫渥特图类的构形，但他的解决办法却正好是对赫渥特图类构形的解决办法）。
张彧典先生的解决方法只是敢峰方法中的一种，他只看到每次颠倒的结果中（包括自身在内）都有含有A—B环形链，交换该环外的C—D链，都可以使图变成坎泊构形而可约。张先生也没有必要把原图进行三次颠倒，最多一次就够用了。也不应把他的方法称为Z—换色程序，因为敢峰先生一九九二年已经确立了解决该类构形的方法。
雷明通过对张彧典先生的书《四色问题探秘》和敢峰的书《4CC和1＋1的证明》的学习，认识到敢峰，米勒，张先生，他们对敢峰—米勒图进行一次演绎或颠倒后，得到的就是一个赫渥特图型的构形，敢峰先生及张彧典先生对该构形的解决方法，实际上就是在解决赫渥特图型类构形的着色问题或可约问题。雷明的这一发现，说明了类赫渥特图型的构形与类敢峰—米勒图型的构形是可以相互转化的。
第九构形本来不进行颠倒和转型也是可以的，只须构形转化0次，颠倒0次，交换一次，即可使图成为坎泊构形；但在使用逆时针颠倒的情况下，第一次颠倒后，图成为一个DCD型的第二构形，用解决第二构形的方法解决也就可以了，最多也只须构形转化一次，颠倒一次，总交换两次，也可以使图变成坎泊构形。而第二次逆时针颠倒后，图再次成为ABA型的第九构形，再次颠倒完全是不必要的。
10、对各构形颠倒次数的分析
以上的各构形中，无论是逆时针颠倒还是顺时针颠倒，只看最少的交换次数、颠倒次数，转型次数时，第一、第三、第四、第五、第六、第七构形都只用了两次交换，一次颠倒，0次转型，就可以空出颜色给V着色；第二构形用了三次交换，两次颠倒，一次转型，也可空出颜色给V着色；第九构形（敢峰—米勒图）最多只用了两次交换，一次颠倒，一次转型，就可以使图变成坎泊构形而可约。而只有第八构形很特殊，转型，颠倒，交换的次数非常之多。有必要对这个构形再进一步的研究。
    我对类似于张先生的没有任何环形链的第八构形的图的研究，得出结论是：六种链中，有A—C，A—D，A—B，C—D四种链都不能进行交换，就是交换了，也起不到任何作用；还有B—C，B—D两条链不能同时交换，当然就不能同时移去两个同色B了。现在看来，只有一种可能了，那就是只交换B—C或B—D两链中的一种，先移去一个同色B，使构形由BAB型转化成DCD型或CDC型，再看转型后的图属于那种类型的构形，再有针对性的进行着色。
我的研究结果是：类似于张先生第八构形的图，无论是采用逆时针交换，还是采用顺时针交换，只需要颠倒（交换）一次即可。颠倒的结果也只可能得到两种结果：一种是类似于张先生第一、第三构形的可同时移去两个同色的构形；另一种是类似于张先生第二构形的赫渥特图型的构形。这两种构形都是有办法解决的，都是可约的。
对类似于张先生第八构形的图，若留下关键的顶点，简化到最后所得到的图，就是张先生第一、第三构形。这两个构形的区别只是连通链的左右分布不同，解法是完全相同的，所以我们以前曾把他们归为一类。而第一、第三构形解决时，虽说是可以同时移去两个同色，但实际上第一次交换时，仍是在进行颠倒和变型。与解决第八构形的方法是完全相同的。解法虽相同但不能化归为一类，这是因为图的结构是不同的。第一、第三构形既具有赫渥特图型构形的特征（有两条交叉的连通链），又具有坎泊构形的特征（可以同时移去两个同色）；而类似第八构形的图，只具有赫渥特图型构形的特征，而不具有坎泊构形的特征；所以不能划归为一类。
现在用我研究的结论，来验证一下张先生的第八构形：张先生的第八构形如图1所示。

首先对第八构形进行一次逆时针颠倒，得到一个DCD型的赫渥特图型的构形（如图2），图中有经过顶点4和5的环形链A—B，把C—D链分成不连通的两部分，C—A和C—B两连通链的共同起始顶点5（着C色）和交叉顶点6（也着C色）分隔在A—B环形链的内、外。可以用解决赫渥特图型构形的办法，从两链的共同顶点进行断链的办法去解决。


再对第八构形进行一次顺时针颠倒，得到一个CDC型的、有选择性的交换两个关于两个同色的链的方法，可同时移去两个同色的构形（如图3）。可以先从顶点5交换C—A（如图4）后，再从顶点3交换C—B，空出B给V着上（如图5），或者再从顶点1交换B—C，空出C给V着上（如图6）。



11、5—轮构形的分类
从5—轮构形总体上看，一类构形是坎泊构形，另一类构形是赫渥特构形。介乎两类构形之间的又有类似张先生的第一、第三构形以及张先生的Z2构形。而赫渥特构形中，又可分为赫渥特图型构形（第二构形，只要有一条环形的C—D链，把两条连通且相交叉的A—C和A—D链的相交顶点A2和A8分隔在C—D环的内、外两侧），敢峰—米勒图型构形（第九构形，只要有一条环形的A—B链，使C5，D4，C6，D7被分隔在A—B环的内、外两侧，不能构成一条连通的C—D链）和类似张先生的第八构形的构形（没有任何环形链。我把这类构形叫做ZL构形，因为它是雷明（L）在张先生（Z）第八构形的基础上构造的）。有了这样的分类，对研究四色问题是会有所帮助的，至少它把错纵复杂的5—轮构形疏理顺当了，条理化了，抓住了一个提纲协领性的东西，研究起来也就能够达到水到到成的效果。

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

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