我的H—构形不可免集完备性的证明

雷明85639720

我的H—构形不可免集完备性的证明
雷  明
（二○一七年十一月二十八日）

我的H—构形不可免集中只有三个构形，它们分别是图中含有环形的A—B链的构形（a类H—构形，如图1，a），图中含有环形的C—D链的构形（b类H—构形，如图1，b），和图中不含有任何环形链的构形（即c类H—构形，如图1，c和图1，d）。

以上的链分别是对于123—BAB型的5—轮H—构形（如图1）而言的，A—B环形链是至少要连续的通过1B—2A—3B三个顶点的链，C—D链是至少要通过5C—4D和6C—7D两对顶点之中一对的链，并不都是任意的A—B链和C—D链。
在H—构形中，A—C链和A—D链都是连通的，是不可进行交换的，是不可能空也A、C、D三色之一给待着色顶点V着上的；H—构形又是不可同时移去两个同色B的，也是不可能空出B色给V着上的，也就是说B—C链和B—D链都是不能进行交换的。
由A、B、C、D四种颜色所能构成的A—B，A—C，A—D，B—C，B—D和C—D六种链，其中的A—C，A—D，B—C和B—D四种都不可能进行交换，那么可能交换的链就只有A—B和C—D两种链了。这两种链正好是一对相反链，是不能相互穿过的。所以若有了环形的A—B链通过了1B—2A—3B和8A四个顶点时，则不可能再有通过5C—4D和6C—7D四个顶点的C—D环形链；相反的，若有了通过了5C—4D和6C—7D四个顶点的C—D环形链，也则不可能再有通过1B—2A—3B和8A四个顶点的A—B环形链，二者最大只可能有其一，要么，就一条环形链也没有。再就没有别的情况了，所以我说我的这个H—构形的不可免集是完备的。至于敢峰—米勒图这一种情况，虽然A—B和C—D环形链有都，但他们没有相互穿过，也不是全部通过了1B—2A—3B和8A四个顶点的A—B链，也不是全部通过了5C—4D和6C—7D四个顶点的C—D环形链。由于敢峰—米勒图的解法只能是任意交换A—B环形链内、外的任一条C—D链，才能使图变成非H—构形的K—构形；而任意交换了C—D环形链内、外的任一条A—B链，图仍是敢峰—米勒图一类的H—构形，不能使图变成K—构形。敢峰—米勒图的解法与a类构形的解法是相同的，所以把它归入a类构形是合理的，不能把其归入b类构形（b类构形的解法是交换C—D环形链内、外的A—B链）。
对于c类构形A—B链和C—D链都是直链（一条道路）且各只是一条，A—B链和C—D链都不能交换，即就是交换了也没有什么用。但是我们不要忘了，B—C链和B—D链虽不能同时交换，但可以先交换一个，使构形由123—BAB型变成451—DCD型或345—CDC型的构形。然后再看转型后的构形是属于a，b，c三类中的哪一类，用解决该类的相应方法去进行解决。
这就是我对我的H—构形不可免集完备性的证明。请业余四色爱好者朋友们提出宝贵意见。

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

   

雷明85639720

，，，，，，，，