从构形结构角度研究H—构形的 不可免集及其不可免构形的可约性

雷明85639720

从构形结构角度研究H—构形的
不可免集及其不可免构形的可约性
——还想与张彧典先生商榷
雷  明
（二○一七年元月二十四日）

目前研究四色问题，主要应是研究H—构形是否可约的就行了。研究H—构形的可约性问题，首先要知道H—构形有多少种，它的不可免集是什么。并且要知道什么是H—构形，才能构造成出不同结构的H—构形来。
H—构形的定义：H—构形应该是既含有两条相交叉的连通链（两链有共同的起始顶点），又不能同时移去两个同色的构形。
1、 H—构形的不可免集
根据H—构形的定义及其特征，我构造出了如下五种不同构结类型的H—构形（我用两种形式画图：一是米勒用的（待着色顶点是）隐形的画法，如图1；二是张彧典行先生用的（待着色顶点是）显形的画法，如图2）。
这两个H—构形的不可免集实质上是同一个集合，只是图的画法不同而已。集合中看似五个元素（构形），实际上只有三个。因为a图中有一条环形的A—B链；b图中有一条形环的C—D链；c图和d图中既没有环形的A—B 链，也没有环形的C—D链，而且两图的结构正好是左右相反的，实际上应是同一个构形；e图则是A—B环形链和C—D环形链都有的构形，这就是敢峰—米勒图。该图既有a图的特征，又有b图的特征，既可归入a图中，也可归入b图中，因此，它不是一个单独的构形。这样，集合中的构形数目，就只有a图、b图、c图的三个构形了。这就是我构造的H—构形的不可免集，其中只有三个元素，即三个构形。

2、 该H—构形不可免集完备性的证明
2、1  这三个构形从有没有环形链角度来分：a图、b图、e图皆有环形链；c图、d图皆没有环形链。从环形链的条数角度来分：c图、d图都是0条；a图、b图都是1条；e图是大于一条的代表。从环形链的种类角度来分：a图只有A—B环形链；b图只有C—D环形链；c图、d图那一种环形链都没有；e图是两种环形链都有。除了这些外，再没有别的环形链分布模式了。

   2、2  这三个图中的A—C链和A—D链是连通链，都与待着色顶点构成了一个环或圈，但不可能本身构成环形链；由于A—C链和A—D链的连通，则其相反链B—D链和B—C链就不能再是连通的了。四种颜色所能构成的六种链中，这四种已经固定，不能变动，那就只有变动另外的两种，即A—B和C—D链了。这就是我们在1中分析的内容。
2、3  这三个图中，除了从2A到4D的A—D链和从2A到5C的A—C链，以及从1B到3B的A—B链中的各条边，也可以是该边两端二色所构成的链外，除了在顶点1B与其相邻的C色顶点间还可有别的顶点外，也除了在顶点3B与其相邻的D色顶点间还可有别的顶点以外，在图中的其他的任一条边上都不能再有别的任何顶点，否则，图就变成了可以同时移去两个同色的K—构形，而再是H—构形了。关于这一点，读者可以自已画图试一试。
到此，就证明了再也没有别的构形是H—构形了，所以我们上面的图1和图2的不可免的H—构形集是完备的。

2、4  以上图1和图2中的构形，当顶点数减少到九点形图时，分别就变成了图3和图4。图1和图2中的e图则变成了图3和图4中的a和b。图3和图4中的这四个图除了b图仍是H—构形外，其他三图都已变成了可以同时移去两个同色B的K—构形了。我们可以看到，图4和图5的a图就是张先生的Z1—构形；图4和图5的b图就是张先生的Z2—构形，也即张先生的第二构形；图4和图5的c图就是张先生的第一构形（即张先生在《补充》一文中的图3—1—1）；图4和图5的d图就是张先生的第三构形（即张先生在《补充》一文中的图3—1—2）。

    3、 不可免的H—构形可约性的证明
H—构形之所以与K—构形不同，主要是由于其中有A—C和A—D两条交叉的连通链而引起的。所以解决这一类图的着色问题时，我们首先想到的就是把连通的A—C链和A—D链断开，使其变成坎泊的K—构形。只要图变成了K—构形，当然也就可约了。
3、1  对于a图的构形，由于有A—B链是环形的，它把C—D链分成了环内、环外互不连通的两部分，交换其中任一部分C—D链，都可使连通的A—C链和A—D链断开。成为坎泊的K—构形而可约（如图5）；
3、2  对于b图的构形，由于有C—D链是环形的，它把A—B链分成了环内、环外互不连通的两部分，交换其中任一部分A—B链，也都可使连通的A—C链和A—D链断开。成为坎泊的K—构形而可约（如图6）。赫渥特图就是这样解决的。具有这种特点的构形，我们它类赫渥特图型的H—构形；


以上3、1和3、2中的交换办法，我叫他“断链交换”，是坎泊所创造的颜色交换技术的又一种作用。
3、3  对于e图的构形，由于该图既有环形的A—B链，它把C—D链分成了环内、环外互不连通的两部分，交换其中任一部分C—D链，都可使连通的A—C和A—D链断开。成为坎泊的K—构形而可约；该图又有环形的C—D链，它又把A—B链分成了环内、环外互不连通的两部分，交换其中任一部分A—B链，也都可使连通的A—C链和A—D链断开。成为坎泊的K—构形而可约。敢峰—米勒图用这两种办法都是可以解决的；
3、4  对于c图和d图，由于其中没有环形链，而且A—B链和C—D链均是直链且只有一条，就是交换了也不起任何作用，图仍不会变成K—构形。而B—C链和B—D链又不能同时交换，不能同时移去两个同色B。没办法，我们就只好先交换一个，先移去一个B，使图由123—BAB型转化成为451—DCD型或345—CDC型。然后，再视转型后的图的类型再进行研究。
转型交换的结果，从不同的转型交换方向看，有两种结果：
一是转化成了可以同时移去两个同色的K—构形（如图7）；

另一是转化成了类似b图的有一条环形的链的类赫渥特图型的H—构形（如图8）。
转化成的两个构形都是可约的。
该构形是在张彧典先生的《四色问题探秘》一书中的第八构形的基础上完善的。由于我第一次看到具有此类结构特点的图是在张先生的书中看到的，所以我叫它“Z—构形”（Z是张先生的“张”字的第一个汉语拼音字母）。这时所说的交换，具有转换构型类型的作用，所以我叫它“转型交换”，是坎泊颜色交换技术的第三种作用。

4、 有环形链的构形一定可以断链的证明
4、1  有A—B环形链的断链证明：因为在A—C链和A—D链中，至少有两对顶点6C与7D和4D与5C是直接相邻的两个顶点，所以，无论A—B环形链是从哪个地方穿过A—C链和A—D链的，也无论是穿过一条还是两条，A—B环形链的某一侧至少是存在着这样的两对顶点之一对的。这就保证了无论从其中的哪一对顶点进行C—D链的交换时，都可以使A—C链和A—D链断开，使构形转化成K—构形。赫渥特图就是这样着色的，敢峰—米勒图也可以这样着色。
4、2  有C—D环形链的断链证明：因为在A—C链和A—D链中，至少有顶点2A和顶点8A是两条链的公共顶点，所以，无论C—D环形链是从哪个地方穿过A—C链和A—D链的，也无论是穿过一条还是两条，C—D环形链的一侧至少是存在着这样的两个公共顶点之一的。这就保证了无论从其中的哪一个公共顶点进行A—B链的交换时，也都可以使A—C链和A—D链断开，使构形转化成K—构形。敢峰—米勒图就是这样着色的。
4、3  用以上的两种断链方法对图1和图2的a图以及图1和图2的b图着色时，要注意的是两种构形断链时所用以交换的链是不同的。如在a图中有环形的A—B链时，交换的是C—D链，而在b图中有环形的C—D链时，交换的则是A—B链。赫渥特图中只有环形的C—D链，所以其只有一种断链的方法，只能任意交换环形的C—D链两侧的A—B链，使图变成K—构形；而敢峰—米勒图中既有环形的A—B链，又有环形的C—D链，所以其不但可以交换环形的A—B链两侧的C—D链，也可以交换环形的C—D链两侧的A—B 链，都可以使图变成K—构形。
5、 Z—构形一定可以转化成K—构形的证明
5、1  Z—构形可以转化成可以同时移去两个同色的证明
从图4中可以看出，只所以图4，a、图4，c和图4，d可以同时移去两个同色B，是因为两个同色顶点1B和2B中至少有一个B色顶点到A—C链和A—D链两链的交叉顶点8A有一条连通的B—A边。以致从1B交换了B—D后，生成了从顶点8到顶点1的A—D边，使得从3B到5C不可能再有连通的B—C 链；而从3B交换了B—C后，则生成了从顶点8到顶点3的A—C边，也使得从1B到4D不可能再有连通的B—D链；从而可以同时移去两个同色B。
现在看图1和图2中的Z—构形在施行了一次转型交换后，是不是与图4，a有同样的结果呢。对图2，c的构形施行一次转型交换得到图9，a，图中C—A链和C—B链的交叉顶点是6C，5—轮轮沿顶点中用了两次的颜色是D，从6C到4D有一条C—D链，当从顶点4交换了D—A后，生成了6C到4A的C—A链，使得从顶点1D到3B不可能再有连通的D—B链，从而可以移去两个同色D。从而就证明了Z—构形是一定可以转化成为可以同时移去两个同色的K—构形的。

5、2  Z—构形可以转化成图1和图2的b图的证明
在图1和图2的各构形中，都有过顶点2A—3B—8A—7D—2A（或2A—1B—8A—6C—2A）的缺口A—B圈（如图10，a），当从顶点1交换B—D（或从顶点3交换B—C）时，顶点7D变成了7B（顶点6C则变成了6B），就形成了一条环形的A—B链（如图10，b），把C—D链分成了环内、环外互不连通的两部分，构形具有了图1和图2的b图的特点了。是一个类赫渥特图型的H—构形，一定是可以转化为K—构形的。

5、3  到此，就证明了Z—构形是一定能转化成为坎泊的K—构形的。

6、四色猜测是正确的
以上的H—构形不可免集已证明是完备的，其中的各个不可免构形也证明都是可约的；那么再加上以前坎泊所证明了的结果，这就证明了四色猜测是正确的。

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

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