就平面图的构形问题还想再说几句

雷明85639720

就平面图的构形问题还想再说几句
雷  明
（二○一四年四月十二日）
（图见上面的DOC文件)
1、简单构形
平面图着色中的不同构形，各有其不同的特点，应从图上让人直观的就可以看出是哪一种。比如最基本的极小九点形5—轮构形（如图1，5个轮沿顶点的着色分别是1A、2B、3C、4D、5B、6C、7D和8A）中，如果存在环形的A—B链(图中的虚线)，就是非H—构形，如果存在环形的C—D链（图中的实线），则是H—构形，若A—B链和C—D链皆是直链则是半H—构形，当然也是属于非H—构形之列。换句话说，只要可以同时移去两个同色B的构形就是非H—构形，否则就是H—构形。这几种简单构形中，九个关键的顶点间均是一条边，比较容易看出图是属于那种构形的。

2、较复杂的构形
而顶点数多于九点形时，各顶点间的相邻关系不象九点形那么简单，虽然图中的链也有以上的特点，但一下子却不容易用看出。若图中存在两条连通且相交叉的1A到3C的A—C链和1A到4D的A—D链，又不能同时移去两个同色B的情况下：
① 图中若有通过3C—4D的C—D环形链时，通过5B—1A—2B的A—B链和通过两连通链A—C和A—D的交叉顶点8A的A—B链一定是被环形的C—D链分成环内和环外两个不连通的部分的，这一定是H—构形的图（如图2，b）。交换两支A—B链的任何一支，都可使A—C和A—D同时断链，使图成为一个非H—构形。如张彧典先生《探秘》一书中的图3.1、图5.1、图5.5、图5.7、图7.3—2、图7.3—9（2）、图7.3—9（4）和图8.3都是H—构形的图。

②图中若有通过5B—1A—2B和8A顶点的A—B环形链时，则C—D链一定是被其分隔成环内环外两个不连通的部分的，这一定是非H—构形（如图2，a）。这种图是比较容易着色的。
③ 图中若既有通过5B—1A—2B的A—B环形链，又有通过8A顶点的A—B直链，也有C—D环形链，还有通过3C—4D的C—D直链，这就是M—构形（如图2，d）。如张彧典先生《探秘》一书中的图5.4、图5.6、图7.3—9、图7.3—9（1）、图7.3—9（3）和图8.2都是M—构形的图。这种构形只要交换任一支C—D链，都可以使A—C和A—D同时断链，使图成为一个非H—构形。
④若图中的A—B链和C—D链各只有一条，且均是直链时，这就是Z—构形。如张彧典先生《探秘》一书中的图7.3—8和图8.1都是Z—构形的图（如图2，c）。这种构形只能从一个同色顶点2B（或5B）进行B—D（或B—C）链的交换，使图转化成M—构形或非H—构形，再进行着色。
④若图中的A—B和C—D链看似单条，但另有单独顶点的色链，如单A色顶点的A—B链，单C色或单D色顶点的C—D链，这些单独顶点的色链又处在连通的A—C和A—D链上时，可以直接改变这些单独顶点的颜色，如A改B、C改D、D改C，都可以使一条或两条连通的A—C和A—D链断链，使图变成非H—构形的图。如张彧典先生《探秘》一书中的图3.1、图7.8—2、7.3—4、7.3—5、图8.1中都有这样的单独顶点链。
3、张彧典先生的九构形
张先生的九构形中，构形1，构形3—7，实际上同一个构形，他们都是可以同时移去两个同色B的，都是非H—构形；构形2是一个H—构形；构形8是一个Z—构形；构形9是一个M—构形。
雷  明
二○一四年四月十二日于长安

任在深

休息一下吧！？
累不累？？