平面图各种构形的相互转化——兼论四色猜测的证明

雷明85639720

平面图各种构形的相互转化
——兼论四色猜测的证明
雷  明
（二○一八年九月四日）
（我把图发不到这里来，请读者到《中国博士网》中去看吧，由于这里又不许别的网址发上来，所以就有读者自已到《中国博士网》中去找了）

1、平面图的构形可分为两个大类四个亚类
现以BAB型的5—轮构形进行说明：
简单的通过一次或两次“换色交换”就可从5—轮构形的围栏顶点中空出一种颜色给待着色顶点着上的构形就是K—构形。K—构形1879年坎泊已经证明了都是可约的；反之，不能简单的通过一次或两次“换色交换”从5—轮构的形围栏顶点中空出任何一种颜色给待着色顶点着上的构形就是H—构形。H—构形又可根据图中是否含有经过5—轮的4D和5C两个轮沿顶点的、环形的C—D链，和是否含有经过5—轮的1B，2A，3B三个轮沿顶点的、环形的A—B链，而又可分为A，B，C三类。只含有经过5—轮的4D和5C两个轮沿顶点的、环形的C—D链的构形为A类H—构形；只含有经过5—轮的1B，2A，3B三个轮沿顶点的、环形的A—B链的构形为B类H—构形；既不含有经过5—轮的4D和5C两个轮沿顶点的、环形的C—D链，又不含有经过5—轮的1B，2A，3B三个轮沿顶点的、环形的A—B链的构形为C类H—构形。总之，平面图的构形共计分为两个大类，四个亚类。两个大类是K—构形和H—构形；四个亚类是K—构形中的K亚类，H—构形中的A亚类，B亚类和C亚类。本文主要就是研究各个亚类之间的相互转化关系的。由于K—构形坎泊在1879年已经证明了都是可约的，所以，现在只要证明H—构形中的各个亚类都可转化成K—构形中的K亚类，也就可以证明四色猜测是正确的。
构形间的相互转化是靠“转型交换”来实现的，具体的说就是交换一个关于两个同色B的链，就可以达到使构形转化的目的。比如对BAB型5—轮构形，从5—轮的轮沿顶点1B交换了B—D链后，构形就可转化成DCD型的5—轮构形。转型交换有两种，一种是从5—轮的轮沿顶点1B交换B—D链，使构形转化成DCD型的构形，叫逆时针转型交换；另一种是从5—轮的轮沿顶点3B交换B—C链，使构形转化成CDC型的构形。而且这两种转型交换是可逆的。对BAB型的5—轮构形从5—轮的轮沿顶点1B交换B—D链的逆时针转型后，再对所得到的DCD型的5—轮构形，从5—轮的轮沿顶点1B交换D—B链的顺时针转型后，又会得到原来的BAB型的5—轮构形。
2、A类H—构形向其他构形的转化
2、1  A类向B类的转化：如图1,图2和图3。图1是一个非十折对称的图，图2和图3是两个十折对称的图。各图中间的的图都是A类构形，其逆时针和顺时针转型都得到的是B类构形。

2、2  A类向C类的转化：至今还没有发现A类构形转化为C类构形的实例，但是我们却看到了由C类构形转化为A类构形的实例（见后面“4、1  C类向A类的转化”中的图15）。由于转型交换是可逆的，所以也一定会存在由A类构形向C类构形转化的实例的。

2、3  A类向K类的转化：如图4，图5和图6。

这种转化当然也是可逆的，不过，由H—构形转化成为了K—构形后，就是我们要达到的目的，所以，就是没有必要再把K—构形转化为H—构形的。图4和图5得到的K—构形都是可以连续的移去两个同色D或C的构形，还需要经过两次简单的换色交换，才能空出两个同色给待着色顶点着上。1992年，米勒就是用这种方法在《理应已知的赫伍德范例》一文中对赫渥特图在赫渥特原着色的基础上进行了4—着色的。

对于A类H—构形，我们还可以用另外一种办法，直接使H—构形中连通且相交叉的A—C链和A—D链变成不连通的，使构形变成一个更一般的K—构形（如图6），只再进行一次换色交换就可以空出颜色给待着色顶点着上。从图6中可以看出，A类构形中有一条经过5—轮的4D和5C两个轮沿顶点的、环形的C—D链，把A—B链分隔成环内、环外互不连通的两部分。交换C—D环外经过5—轮的1B，2A和3B三个轮沿顶点的A—B链，或者C—D环内的其他A—B链，都可以使图中连通且相交叉的A—C链和A—D链变得不连通，从而变成K—构形。图6左图从1B—2A—3交换了A—B链后，所得到的中图中，1A—3B是连通的，2B—5C也是连通的，唯2B到4D是不连通的,从2A或4D交换B—D链就可空出B或D来给待着色顶点着上。这就是“断链交换”法。把图4，图5用与图6相同的方法交换时，也能得到相同的结果，也能对其进行4—着色。1992年3月8日，雷明先生就是用这样的方法，应邀在陕西省数学会第七次代表大会暨学术交流会上，作《赫渥特图的—4着色》的学术论文报告时，对赫渥特图在赫渥特原着色基础上进行了4—着色的。
现在我们经过谈到了坎泊的颜色交换技术不同的三种交换方式，对应着有三种不同的用途。一是坎泊已经用过的，直接交换5—轮轮沿对角顶点的颜色所构成的对角链的、可以直接从5—轮轮沿顶点中空出颜色给待着色顶点着上的“换色交换”；二是转变5—轮构形类型的，只能交换5—轮轮沿顶点1B和4D的B—D对角链，或是交换5—轮轮沿顶点3B和5C的B—C对角链的“转型交换”，第三就是上面所说到的，目的在于断开5—轮构形中连通且相交叉的A—C链和A—D链的，交换5—轮轮沿邻角顶点的颜色所构成的邻角链的“断链交换”。

3、B类H—构形向其他构形的转化
3、1  B类向A类的转化：如图7，图8，图9，图10和图11。图7和图11是两个非十折对称的图，图8和图9是两个十折对称的图，图10也是一个对称的图，但非十折对称。与前相同，各图中间的图也都是B类构形，其逆时针和顺时针转型都得到的是A类构形。

3、2  B类向C类的转化：如图12。

3、3  B类向K类的转化：如图13和图14。因为对B类构形进行转型交换只能转化成A类构形（如图10），而不可能转化成K类构形。所以，只能用“断链交换”法进行转型了。从图13中可以看出，B类构形中有一条经过5—轮的1B，2A和3B三个轮沿顶点的、环形的A—B链，把C—D链分隔成环内、环外互不连通的两部分。交换A—B环外经过5—轮的4D和5C两个轮沿顶点的C—D链，或者A—B环内的其他C—D链，都可以使图中连通且相交叉的A—C链和A—D链变得不连通，从而变成K—构形。图13左图从4D—5C交换了A—B链后，所得到的中图中，虽仍含有连通的A—C链和A—D链，但却不是原来的A—C链和A—D链，该两链虽然中途还有共同的顶点（着A色），但已不存在实际意义上的“十”字相交叉了，而只是两链共用了（相切于）一个顶点而已。所以是可以连续的移去两个同色B的（如右图）。

图14就是敢峰的终极图（也即是米勒图）用“断链交换”法的着色结果。图14右图中虽仍有连通的A—C链和A—D链，但却不是原来的两条链，且两链中途并没有共用的顶点，更没有“十”字相交叉，是完全可以连续的移去两个同色B的K—构形。1992年，敢峰就是这样在他的《证明四色定理的新数学——图论中的锁阵运筹》一书中，对他的终极图进行了4—着色的。但米勒却对他的这个图束手无策，而放弃了他们企图用连续转型的方法解决四色问题的想法。
4、C类H—构形向其他构形的转化
4、1  C类向A类的转化：如图15。

如前述所说，还没有看到A类构形向C类构形转化的实例，但这里却看到了C类构形向A类构形转化的实例。有这样的由C向A的转化，也就应有由A 向C的转化，因为转型交换是可逆的。

4、2  C类向B类的转化：如图16。
4、3  C类向C类的转化：如图17，图18和图19。

4、4  C类向K类的转化：如图20。
5、K—构形向其他H—类构形的转化
上面已经研究了各种H—构形都是可以转化成K—构形的，加上转型交换是可逆的，所以任何一个K—构形也都一定是可以转化成H构形的，这一点是无凝的。但我们的目的是要把任何H—构形转化成K—构形，而没有必要把一个K—构形，而没有必要再把一个K—构形转化成H—构形。所以这里也就不再研究这方面的转化了。

6、四色猜测是正确的
把以上的研究进行统计如下表（一）
                     A类H构形              B类H构形           C类H构形             K—构形
A类H构形                                      √（转型）          √（无实例）        √（转型和断链）
B类H构形           √（转型）                                  √（转型）        √（断链）
C类H构形           √（无实例）              √（转型）          √（转型）        √（转型）
K—构形        √（转型和断链）     √（断链）          √（转型）       
   
把表（一）中的数据画出图如下图21。

图21 正好是一个带有环的多重K4完全图。也真凑巧，任何平面图的最小完全同态也是一个顶点数不大于4的Kn完全图，按哈拉里的观点，平面图的最小完全同态的顶点数就是该平面图的色数，那么平面图的色数最大就决不会超过4了。这就是四色猜测。
在BAB型的H—构形中，A—C和A—D链均是连通的，不能不能进行交换，根本不可能从5—轮轮沿顶点中移去A、C、D三色之一；而B—C链和B—D链也只能交换其中之一，也不可能连续的移去两个同色B。四种颜色都不可能移去，怎么办？现在，由四种颜色所能构成的六种色链中，已有四种不能交换了，但还有A—B和C—D两种是可以交换的。而这两种链又是相反的色链（两链中的两种颜色均不相同），而相反链又是不能相交叉的。所以，在图中经过5—轮1B、2A和3B三个轮沿顶点的、环形的A—B链和经过5—轮4D和5C两个轮沿顶点的、环形的C—D链的关系是：要么只有一条C—D环形链，是A类；要么只有一条A—B环形链，是B类；要么两条都没有，是C类；或者两条都有，是D类。再无别的情况存在。而两条都有的D类又分别具有A类或B类的特征，归于A类或B类哪一类也都是可以的。所以H—构形实际上只有A、B、C三种类型。这就证明了H—构形由A、B、C三类不可免的构形构成的H—构形的不可免集是完备的。即该A、B、C三类构形是能代表所有的H—构形的。
上面我们已经证明了A、B、C三类中的任何一类H—构形都是可以转化成可约的K—构形的，所以说这也就等到于证明了四色猜测是正确的。

雷  明
二○一八年九月四日于长安

注：此文已于二○一八年九月八日在《中国博士见外 发表过，网址是：

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

wangyangke

雷明85639720说得对：wangyangke ，你真无耻！