再谈平面图的不可免构形

雷明85639720

再谈平面图的不可免构形
雷  明
（二○一四年四月九日）
（图请看上面的DOC文件）
在四色猜测的证明中，现在只有5—轮构形还没有被彻底证明是否可约，那么我们就专谈5—轮构形的问题。
    1、5—轮构形最小的极大图构形
一个含有一个5—度顶点未着色的5—轮构形，图中顶点数在最少时，图是极大图的情况只有五种，如图1。

图1 中除了图1，a中的a—b和a—c链只是相交，并没有交叉外，其它图中的a—b和a—c链都是有一次相交叉的；除了图1，e不能同时移去两个同色b外，其它各图都是可以同时移去两个同色b，给待着色顶点v着上b；在同时移去两个同色b时，图1，a和图1，b在交换b—c和b—d链时是不分先生次序的，而图1，c和图1，b在交换b—c和b—d链时则是有先后次序的，否则图就会转化成图1，e那种不能同时移去两个同色的构形。图1，e中有一条环形的c—d链，把a—b链分成了不连通的两部分，交换任一条a—b链都可使图中连通的a—c和a—d链变得不连通。有了不连通的链，就可以再次使用坎泊的颜色交换技术，给待着色顶点v着上图中已用过的四种颜色之一。我们把这种方法叫“断链法”。
从图1中我们还可以看到，五个图中都有相交的a—c和a—d链，这是他们的共性。图1，a和图1，b中有环形的a—b链，把c—d链分成了两部分；图1，c和图1，d中a—b链和c—d链各只有一条；图1，e中有环形的c—d链，把a—b链分成了两部分。由于图1，a和图1，b在同时移去两个同色时，交换的次序不分先后，我们叫他非H—构形，而图1，c和图1，d在同时移去两个同色时，交换的次序是要分先后的，所以我们叫他半H—构形（也属于非H—构形之列），图1，e不能同时移去两个同色，只能用断链法断链后才能着色，所以我们叫他H—构形（因为它是从赫渥特图简化而来）。
2、任意顶点数的5—轮极大图构形
现在我们在图1中的5—轮与3—圈之间增加顶点，在保证图仍是极大图情况下：若图只要能同时移去两个同色时，就是非H—构形；否则就是H—构形。若图中仍有经过5—轮轮沿的c—d环形链时，仍是H—构形，赫渥特图就是这种图；若图中a—b链和c—d链均是单条时，就是张彧典先生第八个构形的图（用Z—构形表示）；若图中有经过5—轮轮沿顶点的a—b环形链，也有不经过5—轮轮沿顶点c—d环形链，两环形链成同心园，两园内外各有a—b和c—d直链一支，这就是米勒图（用M—构形表示）。这几种构形示意画法如图2。

    图2 中的非H—构形（包括半H—构形）都是可同时移去两个同色的；H—构形可交换任一条a—b链，使相交的a—c和a—d链断链（如赫渥特图及张彧典先生《探秘》一书中的图5.5、图5.7的着色）；M—构形可交换任一条c—d链，也可使相交的a—c和a—d链断链（如张彧典先生《探秘》一书中的图5.4、图5.6的着色）；而Z—构形则必须进行一次有关同色的色链交换后，使图转化成非H—构形或H—构形或M—构形，再用对非H—构形、H—构形、M—构形着色的办法进行着色。这一点请参见本人博文《对张彧典先生第八构形的研究》一文。
3、几个H构形的相互转化
在第一个问题中已经知道了半H—构形是可以转化成H—构形的，当然H—构形也一定可以转化为半构形的。当从图1，e的左边b色顶点进行b—d链的交换后，图就转化成为dcd型的类似于图1，d的半H—构形；当从图1，e的右边b色顶点进行b—c链的交换后，图就转化成为cdc型的类似于图1，c的半H—构形。
M—构形与H—构形间也是可以相互转化的。张彧典先生《探秘》一书中的图5.4向图5.5的转化，就是一个M—构形向H—构形转化的倒证，图5.5向图5.6的转化，是一个H—构形向M—构形转化的倒证，图5.6向图5.7的转化，又是一个M—构形向H—构形转化的倒证，图5.7向图5.8的转化，又是一个H—构形向M—构形转化的倒证。
在第二个问题中，我们还看到了Z—构形向H—构形，M—构形的转化。
4、M—构形的结构分析
为什么米勒图中只能交换C—D链而不能交换A—B链：因为米勒图中的A—B环链是在5—轮轮沿顶点上，不能交换，若进行了交换，仍然是一个M—构形的米勒图。若把张彧典先生《探秘》一书中的图5.4的米勒图中的A—B环链进行交换，得到的是一个与原图结构完全相同的图5.6（如图3中图），也是一个M—构形；图5.4中的米勒图中的A—B直链又不在5—轮上，就是交换了也没有什么用，若是交换了，也得到的是形如图5.6的图（如图3右图），还是一个M—构形。

两种交换得到的结果相同，图中有均有两条相交的连通链，也有构成同心园的两条a—b环链和c—d环链，在同心园内外分别有a—b直链和c—d直链，只是相交链的相交顶点成了4个而不是原来的2个。所以米勒图只能交换任一条c—d链进行断链，使图转化成非H—构形（如图4），两种交换得到的结果也想同，均成了有两连通链只一个相交顶点的图。这是一个非H—构形的图。这也是一个M—构形向非H—构形转化的例证。相应的，再进行同样的交换，又可以把非H—构形转化成M—构形。

米勒图进行一次有关同色的交换后得到的图是一个如图5右图的H—构形，这也就是张先生书中的图5.5。图中有一条环形的a—b链，把c—d链分成了环内环外两部分。只是两相交链交叉了两次，多了一个交叉顶点。

图5右图中有一条环形的a—b链看，可以从任一条c—d链进行交换，使图变成非H—构形（如图6）。这两个图中虽然也各有两条相交叉的链，但只是交叉，并不是同一起点，所以不同H—构形。他们均可通过一次坎泊的颜色交换技术后，就可分别着上非同色顶点颜色的另三种颜色之一。
5—轮构形中，还有没有另的构形，我们不得而知，但是不是四色猜测就不行进行证明了呢，还是的。请看下面的4。

4、用“断链”的观点证明四色猜测
在未着色顶点的5个相邻顶点4着色的情况下，要给待着色顶点着上图中已用过的四种颜色之一，就必须从待着色顶点的5个邻接点中去掉一种颜色。我们知道，5—轮的对角顶点的颜色构成的色链若是连通的时，这样的色链是不能交换的，是空不出颜色的，只有5—轮的对角顶点的颜色构成的色链是不连通时，才可交换，空出颜色。只要能证明任何链都是可以断开的，也就能使四色猜测得到证明。
A、B、C、D四种颜色，在A—B链的两侧一定都是着有C、D二色的顶点，可以从A—B链中的任一个A（或B）色顶点交换A—C（或A—D）链，都可以使A—B链断开。这就为5—轮对角链的不连通链创造了条件，也为从待着色顶点的5个相邻顶点4着色情况下空出一种颜色创造了条件，最后达到解决四色问题的目的。

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

任在深

找出一个符合拓补数学的数学函数结构式足以！
            因为
                (1) f(S)=3X²+1
             又 (2)  F+V-E=1
          所以  (3) f(s)=F
            即  (4) 3X²+1=E-V+1
                (5) 3X²=E-V
            证
              i.X=1，E=9，V=6
                3X²=3
                E-V=9-6
                   =3
             ii.X=2，E=30，V=18
                3X²=12
                E-V=30-18
                   =12
            iii.当X=n,显然符合拓补不变原理
           iiii.当X=n+1
                f(s)=3(n+1)²+1，应然符合拓补不变原理！
         四色猜想成立！
          证毕。
    道理通，路路通！
    道理不通，迷路一程！！