我对“九点形”构形的研究

雷明85639720

我对“九点形”构形的研究
雷  明
（二○一六年三月十日）

1、由赫渥特图简化而来的“九点形”构形（H—构形）
赫渥特图的简化图1的“九点形”构形，也即张彧典先生的第二构形，我们叫它H—构形。实际的赫渥特图中顶点1B到7D间是一条B—D多边链，4D到6C间是一条C—D多边链，其他各顶间都是如图1中一样，是一条单边链。该图不能同时移去两个同色B，关键的地方在于6C到7D间是一条单边，这就造成交换了1B—7D的B—D链时，便产生了3B到5C的连通链B—C；而交换了3B—6C的B—C链时，便产生了1B到4D的连通链B—D。该构形总不能同时移去两个同色B。而只能从2A到4D和2A到5C的A—D和A—C两链的交叉顶点8A处交换A—B链，使得A—D和A—C链同时“断开”，均变成不连通链，使构形变成坎泊的K—构形而得解。这就是H—构形的求解方法。“九点形”构形和赫渥特图都是可以这样求解的。

仔细观察，可以发现“九点形”构形只所以不能同时移去两个同色主要是因为6C和7D间是一条单边的原因。如果这两顶点间不是单边，则一定是可以同时移去两个同色B的。这一点非常重要，可以看到，赫渥特图中的顶点6和7，张彧典先生书中的所有图中的D2和C2（张先生书中的D2和C2相当于我们这里的6D和7C），包括米勒图中的这两点间，都是一条单边。若该两顶点间不是单边，就不是H—构形。
2、有A—B环形链的“九点形”构形（非H—构形和L—构形）

图2的“九点形”是可以同时移去两个同色B的，是一个K—构形，我们叫它非H—构形。张彧典先生的构形中没有该种构形，他是把这种构形划归到他的第一构形中去了。该构形可以同时移去两个同色的原因是因为在1B和8A间以及3B和8A间都是单边链，交换了1B和7D（或3B和6C）后，不可能产生3B到5C（或1B到4D）的连通链，当然也就可以再断续交换3B和6C（或1B和7D）了，也就可以同时移去两个同色B。如果1B和8A间（或3B和8A间）是一条A—B多边链，则交换了1B和7D（或3B和6C）后，就可能产生3B到5C（或1B到4D）的连通链，如图5和图6。这是因为交换了1B—7D（或3B—6C）后，7B（或6B）会与原1B—8A（或3B—8A）旁的C（或D）相邻，接续上了3B—6C（或1B—7D）的B—C链（或B—D链）；另一方面B—D链（或B—C链）和A—B链中都有B，两链均是可以相互穿过的。因此在这种情况下，就必须仔观察好，看1B和8A间以及3B和8A间那一条是单边链：若1B和8A间是单边链，而3B和8A间是多边链，则先交换1B和7D，后交换3B和6C；若3B和8A间是单边链，而1B和8A间是多边链，则先交换3B和6C，后交换1B和7D；二者都是可同时移去两个同色B的，如图7和图8。

若图2中1B和8A间以及3B和8A间都是多边链（如图9），则是不能同时移去两个同色B的。这时就得用张彧典先生的“颠倒法”进行构形转型了，逆时针颠倒后构形由BAB型转为DCD型，图10和图11。图11是一个H—构形，图中有环形的A—B链，把C—D链分隔成互不相通的两部分，交换任一部分都可使构形转化为K—构形，如图12。象图9这样的图，在以前的研究中还是没有出现过的，张先生的构形中也没有这种构形，它具有一定的代表性。我们叫它雷氏构形或L—构形。该构形含有通过顶点4D和5C的环形的A—B链，但又不能象图2那样的构形可以同时移去两个同色B，而必须使用颠倒法进行解决。这就是该构形的特点。
3、无A—B环形链的“九点形”构形（半H—构形）
图3和图4的“九点形”，我们叫它半H—构形，也是能同时移去两个同色的，也都是K—构形。图3先交换1B和7D，后交换3B和6C，而图4则先交换3B和6C，后交换1D和7D，都是可以同时移去两个同色B的。
图3和图4中的5C和7D间，4D和6C间，1B和7D间，3B和6C间都是单边，但也可以不是单边，而是多边链。如赫渥特图中的顶点4和6间，顶点1和7间，都不是单边，如图13和图14。在这种情况下，在交换了3B—6C（或1B—7D）后，也可以产生1B—4D（或3B到5C）的B—D链（或B—C链），如图15和图16。这是因为B—C链与C—D链中都有C，交换了3B—6C（或1B—7D）的B—D链（或B—C链）后，也能使C—D链中的C变成B（当然也能使C—D两旁的A—B链中的B变成C）。

这种情况的解决办法是：对图13来说，先交换1B—7D，再交换3B—6C，而对于图14来说，则要先交换3B—6C，后交换1B—7D，都是可以同时移去两个同色B的（读者自已画图）。上面还提到了赫渥特图中顶点1和7之间可以是多边链的问题，同样顶点3和6之间也可以是多边链，不过这里的链不管是单边还是多边，都不会影响能否同时移去两个同色B的问题。由于顶点1B和7D（或3B和6C）间可以是多边链，那么也就产生了在顶点2A和7D（或6B）间也可以是多条边构成的道路（不一定是链）。张彧典先生的第四构形到第七构形都是属于这样一类问题的构形。
4、同时含有A—B环形链和C—D环形链的构形（M—构形）
图1的H—构形中含有通过4D和5C以及7D和6C的环形链C—D，而图2的非H—构形中含通过1B、2A和3B以及8A的环形链A—B，都只有一种环形链。在M—构形中这两种环形链均有，但环形的C—D链却不通过4D和5C，环形的A—B链却不通过8A，如图17，这就是张彧典先生的第九构形。从图17中还可以看出，以上我们所研究的构形，包括M—构形在内，都是在2A与7D、2A与6B、6B与7D、6C与8A、7D与8A、8A与4D、8A与5C间是单边链。而M—构形在8A与4D、8A与5C间却是多边链，这是M—构形与前面的构形不同的地方。M—构形是不能同时移去两个同色的，也不能通过交换A—B链而使构形转型。由于图中的C—D链被环形的A—B链分隔成了环内外互不相通的两部分，所以交换任一部分C—D链都可以使构形发生转化，使之转型成可同时移去两个同色的K—构形而得解。

5、不含任何环形链的“九点形”构形（Z—构形）
不含任何环形链的“九点形”构形如图18和图19。这也就是张彧典先生的第八构形。从上面的图9、图13和图14知道，这种情况的构形是不能同时移去两个同色的，解决的办法也只能是用颠倒法，使构形转型。

图18和图19进行逆时针颠倒后分别得到图20（或图22）和图21（或图23），由BAB型转化成了DCD型。图20（或图22）是一个半H—构形，可以先交换4D—8A，再交换1D—7B，空出D给V着上，如图24；图21（或图23）是一个Ｈ—构形，有一条过5—轮的顶点2A和3B的环形A—B链，把C—D链分隔成了互不相通的两部分。从顶点7C交换C—D链，即可使构形转化成Ｋ—构形，得解，如图25。

6、小结
从以上的分析看，不能把有没有连通、且交叉的两条相邻链（有共同的一种颜色的两种链叫相邻链）作为判断是否是H—构形的标准，而要把是否能够同时移去两个同色作为标准。这样图2、图3、图4就都是非H的K—构形了；而在H—构形中，除了赫渥特的H—构形外，还有虽含有环形的A—B链，但又不能同时移去两个同色的L—构形，也还有既含有环形的A—B链，又含有环形的C—D链的M—构形，又有既不含有环形的A—B链，又不含有环形的C—D链的Z—构形。共计H—构形有：H、L、M、Z四种构形。是否完了，我还无法断定。但从我们所进行的分析上看，各种情况是乎都已分析完了，不存在漏洞了。
从以前我们的研究看，也认为已经考虑了各种情况，但实际上并没有考虑完全。本文中又出现了一个图9的L—构形，以后还会不会再出现别的构形，也就很难回答是有，还是没有。所以我还是主张从“不画图，不着色”的方向上去研究四色问题。
7、对张彧典先生的颠倒着色法的评价
张彧典先生的颠倒法是一个普适的着色方法，无论是能否同时移去两个同色，只要图中含有两条既连通又相互交叉的相邻链，都可以使用这种着色方法。但一定要注意，不一定要完成多少次颠倒，只要构形已经转化成了坎泊的K—构形，就要及时的把问题解决。否则不但会耽误时间，而且还会增加出错的机会。另一个要注意的是，颠倒一定要把同一个方向进行下去，中途不能改变。

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

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