张彧典先生九个构形的4—着色

雷明85639720

张彧典先生九个构形的4—着色
雷  明
（二○一六年二月份二十四日）

张彧典先生在其《四色问题探秘》一书中的九个构形，也就是九个具体的图，现地我们对其简单着色如下，与张先生的着色方法比较，看是否能简单一些。
1、图1的非H—构形，无论先交换那一个关于两个同色B的链，只用两次交换就可以同时移去两个同色B而得解；若用张先生的颠倒法着色时，二者交换的次数是相同的（张先生的九构形图中没有画这个构形）。

2、图7•3—2的构形二（如图2的H—构形），无论先交换那一个关于两个同色B的链，都不可以移去两个同色B，但图中有一条环形的C—D链，把A—B分成了不相通的两部分，交换任一部分A—B链，都可以使构形变成K—构形，再进行一次交换就可以得解，也只用了两次交换；而张先生用颠倒法却交换了三次。
3、图7•3—1的构形一（如图3的半H—构形），必须先交换1B—7D，后交换3B—6C，才能同时移去两个同色B，用了两次交换；与张先生用颠倒法的交换次数相同。
4、图7•3—3的构形三（如图4的半H—构形），必须先交换3B—6C，后交换1B—7D，也才能同时移去两个同色B，也是用了两次交换；比张先生用逆时针颠倒法少用了两次交换。

从交换中还可以看出，图2的H—构形，在只交换了关于两个同色B的链后（不管是交换一次，还是交换两次），得到的都是一个半H—构形的图；而半H—构形在交换时的先后顺序搞错了时，也会得到一个H—构形的图。这说明了H—构形与半H—构形是可以相互转化的（图读者可以自已画一画）。
5、图7•3—4到图7•3—7的四个图都是属于与图7•3—3类似的图，只是顶点数一个比一个多了一些。他们都可以先交换3B—6C，后交换1B—7D，就可同时移去两个同色B，也是用了两次交换；比张先生用逆时针颠倒法分别少用了三次，四次，五次和六次交换。
由于对这些图施行逆时针颠倒，相当于对两条关于两个同色B的链的交换次序搞反了，所得到的都是一个DCD型的H—构形，图中都有含有2A—3B的环形的A—B链，分C—D链为互不相通的两部分，交换任一部分C—D链都可以使构形变成K—构形，最多只用三次交换就可得解。
这里要注意的是，当构形发生了转化时，一定要及时的求解，否则将会增加颠倒或交换的次数。
6、图7•3—8构形八（我叫它Z—构形），它不同于图7•3—4到图7•3—7的四个图，不可同时移去两个同色B。也只能施行颠倒了。当施行了逆时针颠倒后，也得到了一个DCD型的H—构形，图中都有含有2A—3B的环形的A—B链，分C—D链为互不相通的两部分，交换任一部分C—D链都可以使构形变成K—构形，最多只用三次交换就可得解；比张先生用颠倒法减少了六次交换。
这个图在施行了一次顺时针颠倒后，也可得到一个CDC型的半H—构形，是可以同时移去两个同色C 的。也只用了三次交换。
7、图7•3—9构形九（即M—构形），图中有通过1B—2A—3B的A—B链，把C—D链分成了互不相通的两部分，但却不能同时移去两个同色B，只能交换任一部分C—D链，使构形转化成无交叉链的K—构形，最多也只用三次交换，与张先生的Z—换色程序是同方法同解的。
总之，我这里用的着色方法，比张先生在《探秘》一书中用的逆时针颠倒法所交换的次数是要少得多的。
从这里也可以看出，H—构形的不可免集中的构形可以是：{ 可以同时移去两个同色B的构形，H—构形，M—构形，Z—构形 }或{ 非H—构形，半H—构形，H—构形，M—构形，Z—构形 }。

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

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