无环形链的H—构形一定可以转化成有环形链的H—构形的证明

雷明85639720

无环形链的H—构形一定可以转化成有环形链的H—构形的证明
雷  明
（二○一八年十月三日）
（图发不上来，请到《中国博士网》中去看）

     我们已经把H—构形按有无经过5—轮的1B，2A和3B三个轮沿顶点的环形的A—B链和有无经过5—轮的4D和5C两个轮沿顶点的环形的C—D链分成了三个类别，一类是有环形链A—B的（a）类，一类是有环形链C—D的（b）类，另一类是无任何环形链的（c）类。我们已经证明了前两类是可以通过断链交换，解决问题的。即对于（a）类构形，可以交换经过5—轮的4D和5C两个轮沿顶点的C—D链，使构形变成K—构形而可约；而对于（b）类构形，可以交换经过5—轮的1B，2A和3B三个轮沿顶点的A—B链，使构形变成K—构形而可约。

而对于（c）类构形，已经从着色实践上证明了无环形链的H—构形是可以通过“转型”交换，可以把这种构形转化成可以连续的移去两个同色C（或D）的K—构形（如图1，是施行了逆时针交换），或者转化成类似有一条经过了5—轮的4D和5C两个轮沿顶点的环形的C—D链的（b）类H—构形（如图2，是施行了顺时针交换），都可以进行4—着色。并且也从理论上给出了证明如下：

1、无环型链的（c）类H—构形可以转化成可以连续的移去两个同色的K—构形的证明

（1）  我们知道，没有环形链的九点形构形只所以可以同时移去两个同色B，是因为两个同色顶点1B和3B中至少有一个B色顶点到A—C链和A—D链两链的交叉顶点（着色为A）有一条连通的B—A边。以致从1B交换了B—D后，便生成了从两链的交叉顶点到顶点1D的A—D边，使得从3B到5C不可能再有连通的B—C 链；而从3B交换了B—C后，则生成了从两链的交叉顶点到顶点3C的A—C边，也使得从1B到4D不可能再有连通的B—D链；从而可以连续的移去两个同色B。读者可以对无环形链的九点形构形进行交换，试试看是否可以连续的移去两个同色B。
（2）  现在看看对图1，a和图2，a中施行了一次转型交换后，是不是与无环形链的九点形构形有同样的结果呢。对以上图中的构形从1B施行了一次逆时针转型交换后得到图3，a，是一个451—DCD型的5—轮构形。图3，a中C—A链和C—B链的交叉顶点是6C（即图中加大的顶点），5—轮轮沿顶点中用了两次的颜色是D，从6C到4D有一条C—D链（即图中加粗的边链）；当从顶点4交换了D—A后，生成了从2A到4A的A—C连通链（如图3，b中加粗的边链），使得从顶点1D到3B不可能再有连通的D—B链，从而可以再从1D交换D—B，连续的移去两个同色D。这就证明了无环形链的H—构形是一定可以转化成为可以连续的移去两个同色D的K—构形的。对另一种无环形链的（c）类H—构形从3B施行了一次顺时针转型交换后，得到的345—CDC型的5—轮构形，也有同样的结果，也是可以连续的移去两个同色C的K—构形。
2、无环形链的（c）类H—构形可以转化成类赫渥特图型的（b）类H—构形，再转化成坎泊的K—构形的证明
在图1，a和图2，a的（c）类H—构形中，有通过顶点2A—1B…8A—6C—2A的、且有缺口是6C的A—B圈（见图4，a中加粗的边链），当对以上两构形从顶点3交换B—C施行顺时针交换时，顶点6C变成了6B，就形成了一条完整的环形的A—B链（见图4，b中加粗的环形链），把C—D链分成了环内、环外互不连通的两部分，构形具有了（b）类H—构形的特点了。这是一个345—CDC型的类赫渥特图型的H—构形，一定是可以转化为K—构形的。对另一种无环形链的（c）类H—构形从1B施行了一次逆时针转型交换后，得到的451—DCD型的5—轮构形，也有同样的结果，也是一个类赫渥特图型的H—构形。



虽然着色实践和理论上都证明了（c）类H—构形最终是可以转化成可约的K—构形的，但却很难保证每一个（c）类H—构形在转型交换中，一定都能转化成K—构形。万一转型交换后得到的图仍是一个没有环形链的（c）类H—构形，该如何办呢？
从图5和图6中可以看出，（c）类H—构形中一定都存在着两个4—度的顶点，其相邻顶点只占用了两种颜色（如图5，a，图5，b，图6，a，和图6，b中加大的顶点），而这两个顶点又分别位于A—B链和C—D链之上。若把其中的一个4—度顶点的颜色改成另一条相反色链上的颜色（即第四种颜色）时，就会使图由无环形链的（c）类H—构形转化成有环形链的（a）类和（b）类H—构形中的一种（如图5，c和图6，c是（a）类；图5，d和图6，d是（b）类。图中带括号的字母颜色是改动后的颜色）。然后再按有环形链的相应构形的解决办法解决就可以了。

如果改动颜色的4—度顶点同时又是位于两条交叉的链上时，则图就直接变成一个可约的K—构形了（如果在图5中没有左边的8A到5C的A—C边或链和图6中没有右边的8A到4D的A—D边或链的情况，图就直接变成了K—构形）。
相应的，把有环形链的图，也可以用同样的办法使其转化成无环形链的构形。请注意，图5和图6的构形中，各还有两个着色为B的顶点是4—度的顶点，但该顶点的相邻顶点却已占用了三种颜色，该顶点的颜色B是不可再改动的。
为什么说（c）类H—构形中一定存在着两个4—度的顶点，且与其相邻的顶点只占用了两种颜色呢，这首先是因为环形的2—色链未着色之前一定是偶圈，而两个偶圈相交叉时（注意，这里说的是两个偶圈相交叉，而不是两个相反的2—色环形链相交叉），一定会有两个相交点，这两个相交点把每一个圈都分成了两部分。在对各圈的各部分进行2—着色时，在各圈中，把与两圈的相交顶点相邻的两个顶点必须着成相同的颜色，才能保证各圈中被两圈的相交顶点所分成的两部分顶点数的和是偶数，也才能保证两个圈一定都是偶圈，也才能保证两个圈着色的结果一定都是2—色圈。在这种情况下，与两圈的相交顶点相邻的顶点就只会占用两种颜色。若把这两个4—度顶点都着上同一条2—色链中的颜色时，图中就产生了环形链，另一条则被分成了两部分；又若把这两个4—度顶点分别着上相反的2—色链中的颜色时，图中则不会产生环形链。这就证明了在（c）类H—构形中，一定存在着两个4—度的顶点分别位于A—B链和C—D链上，并且与两个4—度顶点相邻的顶点只占用了两种颜色。
总之，对于图5，a和图6，a，总可以改动某一链的某一个顶点的颜色，使该链断开，而使另一条链成为经过5—轮的1B，2A和3B三个轮沿顶点的环形的A—B链（如图5，c和图6，c。图中带括号的字母颜色是改动后的颜色），或者成为经过5—轮的4D和5C两个轮沿顶点的环形的C—D链（如图5，d和图6，d。图中带括号的字母颜色也是改动后的颜色），分别成为（a）类和（b）类的H—构形，或者直接成为K—构形，再按解决（a）类、（b）类H—构形的办法和解决K—构形的办法去解决就可以了。
这就证明了任何（c）类H—构形（即Z—构形）一定都是可以转化成可约的K—构形的。

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

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