对张彧典先生九构形的剖析

雷明85639720

对张彧典先生九构形的剖析
——六评张先生的九构形
雷  明
（二○一四年三月十四日）
（图请见上面的DOC文件）
1、H—构形的特征及其基本模型
在“五评”中我们已经说过了，平面图的不可免构形主要分为两大类，即非H—构形（包括半H—构形）和H—构形。H—构形是不能同时移去两个同色的构形，否则就是非H—构形。半H—构形虽然可同时移去两个同色，但它却包含着H—构形中所含有的两条相交叉且连通的色链，这是其它非H—构形所不具备的。如图1。所以说，半H—构形是处在由非H—构形向H—构形过渡阶段的构形。
图1中的非H—构形或者说半H—构形都是可以同时移去两个同色B的，图1，c的构形两次交换是不分先后次序的，而图1，a和b的构形两次交换则要分先后次序的。图1，d的H—构形则无论怎么交换也是不能同时移去两个同色的，只能先把图变转化成非H—形，再去进行着色。要把H—构形转化为非H—构形，只能从两交叉链A—C和A—D的任一个相交顶点进行A—B链的交换，使A—C和A—D都变得不连通，也不交叉，再对待着色顶点着色。
2、赫渥特图的剖析
可以看出，张先生的构形一就是图1，a，构形二就是图1，d，构形三就是图1，b。而图1，d（即张先生的构形二）就是赫渥特图简化后的九点形。如图2。可以看出真正的赫渥特图是在简化模型中的B1—D2和D1—C2之间增加了一些顶点（如图3，a，在这里图中只是增加了必要的顶点，比赫渥特原图中增加的顶点数要少一些）。赫渥特图并不左右对称，如果按以上增加顶点的方法，增加到左右对称时则是图3，b。

从图3中可以看出，赫渥特图中有两条连通且相交叉的链A—C和A—D，不能同时移去两个同色B给待着色顶点V。图中还有一条C—D环链，把A—B分成了互不连通的两部分（其中A2也应视为是一条A—B链，该链是只有一个顶点的特殊色链），只能从两交叉链的相交顶点进行交换，使A—C和A—D链变得不连通，使图变成一个含有B—C和B—D（或B—C和B—D）相交叉的半H—构形（也即非H—构形）后，再通过一次别的交换，可给待着色顶点分别着上C、D、A（或C、D、B）三色之一。如图4（这时只对图3 中每个图给出了两个着色模式，还有很多的其它着色模式，读者可自已画一画）。


从图3中还可以看出，赫渥特图在保持了基本模型（图2，a）中的A1—C2—A2—C1和A1—D2—A2—D1链仍只是四个顶点三条边，A1—C2—A2—D2—A1仍是一个四边形（C2—D2是其对角线，两对角顶点是相邻的）情况下，而只是在A1—C2—A2—C1—V—A1环内和A1—D2—A2—D1—V—A1环内增加了一些顶点，并保持了图是一个极大图。

3、米勒图的剖析

现在再看一看米勒图（图5）。米勒图也有两条连通且交叉的链，也不能同时移去两个同色。我们把米勒图（图5，a）按张先生的习惯画法，经拓扑变形画成图5，b，可见米勒图无论怎样变形都是左右对称的。A1—C2—A2—D2—A1仍是一个四边形，C2—D2仍是四边形的对角线，两顶点是相邻的，只是相交叉的A—C和A—D链的长度增大了。所增加的顶点主要是处在H—构形基本模型中的A2—C1—D1—A2三角形内。为了看清楚增加的顶点主要处在A2—C1—D1—A2三角形内。我把米勒图按我画图的习惯画在了图6中，以与图5进行比较。

米勒图也是不能同时移去两个同色B的，也必须把图进行变化，使其转化为非H—构形，再进行着色。米勒图既是H—构形，首先就应可以从两连的任一相交顶点进行断链，使构形由H—构形转化为非H—构形，如图7。虽图中仍含有两条连通且交叉的链，但不是原来的两条链，交叉顶点数已不再只是一个（次），而是三个（次），两次交叉的作用相互抵消，只有一次是真正的交叉，图仍是一个米勒图式的H构形。图7，a是从两链的交叉A2进行断链的，若从另一交叉顶点A1进行断链，也可得到相同的结果，如图7，b。
由于米勒图还有不同于H—构形基本模型的地方，其中的A—B链仍是两条，但C—D链却不只是基本模型中的一条而是两条，这就增加了从A—C和A—D两链的非相交顶点进行断链的可能，实践证明也是可以的这样断链的。由于米勒图中有两条C—D链，从哪一条C—D链的任一个顶点开始交换C—D都是可行的，都可同时移去两个同色B。如图8。其中交换C1—D1直链的一种就是张先生的Z换色程序。图8这两个图都是可同时移去两个同色B的非H—构形。


注意，当我们从米勒图中两连通链的相交顶点进行断链后，则图中又产生了两条新的A—C和A—D链，其交叉顶点不再是原来的一个，而是三个，但这还是一个H—构形的图。如果我们把它仍看成是一个米勒图，从两链的非相交顶点进行C—D链的交换，则可使图变成一个仍有两条连通的A—C和A—D链，但两链却不交叉的非H—构形，也可同时移去两个同色B。如图9就是对图7，a交换C—D链所得的结果，图中有两条连通链，但却不交叉。对图7，b交换C—D链也会得到同样的结果。

4、张先生第四到第七构形的剖析

① 第四构形：该构形是在第三构形（半H—构形）的基础上，在A1—D2间增加顶点成为A1—D2链。在B1—D2间增加顶点成为B1—D2链，且把两链相交一次。如图10。

② 第五构形：该构形是在第四构形（半H—构形）的基础上，用在C1—A2和C1—间D2增加顶点的办法，使C1—D2和A1—C1链相交一次。如图11。

③ 第六构形：该构形是在第五构形（半H—构形）的基础上，用再增加顶点的办法，使B1—D2和B1—A3相交一次。如图12。
④ 第七构形：该构形是在第六构形（半H—构形）的基础上，用再增加顶点的办法，使B1—D2和C1—D2相交一次。如图13。

⑤ 从第三构形到第七构形，都是在第三构形的基础上增加顶点得到的，但所增顶点及边都是位于V—A1—A这个对称轴的左侧，右侧仍含有基本模型中的B2—A2这条单边，使得首先从B2进行了B—C链的交换后，不可能新生成从B1到D1的连通的B—D链，可再从B1开始交换B—D链，同时移去两个同色B。所以说，从第三到第七的五个构形实际上是同一个构型。
5、张先生的第八构形的剖析
张先生的第八构形如图14，它只是在图13的第七构形基础上在图的对称轴右侧增加了三个顶点，与第三到第七构形是不同的。
这个图由于对称轴右侧的A2到B2不再是单边，这就造成了首先从B2交换了B—C后，便新生成了由B1到D1的B—D连通链，不可能再从B1交换B—D，也不能同时移去两个同色B。但这个图中A—B链和C—D链分别都只是一条，从两条交叉且连通的A—C和A—D链的相交顶点断链也不可能，其结果只是把图中两种颜色所着的位置进行了改变，图并没有转变构形。同样的，从两交叉链的非相交顶点进行断链，也是不可行通的。这也就是说，图中的A—B链和 C—D链都是不可能进行交换的。这个第八构形如何着色，本人也就产生了极大的兴趣，这是一个既不同于赫渥特图，又不同于米勒图的构形，我们暂且叫它张氏图吧。这个图的着色也就只能首先从一个同色顶点B进行B—C或B—D链的交换后，看其会不会发生构形转化的情况。但决不会非得用到八次的交换，因为我们已经发现张先生对他的第八构形的八次交换中，有些图已经发生了构形的转化。有关这个图的着色，以后将会有专题研究，今天就此再不谈这一问题了。

6、赫渥特图，米勒图和张氏图三种H—构形的形成原理
图15是H—构形的最基本也是最小的模型。
从以上的剖析中可以看出，赫渥特图是在保持了基本模型中的A1—D2—A2—C2—A1仍为四边形，A2—C1—D1—A2仍为三边形时，在其它边和面中增加顶点和边形成的，如图16中的阴影部分。米勒图是在保持了基本模型中的A1—D2—A2—C2—A1仍为四边形时，在其它地方增加顶点和边（主要是在A2—C1—D1—A2三角形区域）形成的，也如图17中的阴影部分。而张氏图则是在只保证了基本模型中的A2—C2—D2—A2仍是三边形时，在其它部分增加顶点的边形成的，也如图18中的阴影部分。


    赫渥特图一类的图的着色方法除了从两交叉链的相交顶点断链外，还可从一个B色顶点进行B—C或B—D链的交换，使图变成一个半H—构形的图，再进行着色。米勒图一类的图除了从两交叉链的非相交顶点断链外，也还可从一个B色顶点进行B—C或B—D链的交换，使图变成一个非H—构形的图，再进行着色。而张氏图一类的图的着色，张先生用了逆时针赫渥特颠倒的H—换色程序已可进行着色，但交换的次数太多，手序太烦。可否用少量次数的交换就可使其构形进行转化，有待进一步的研究。因为张先生在着色过程中只考虑了图中还有没有相交叉的连通链，而没有注意到，一些图中虽含有相交叉的连通链，但也是非H—构形的图的这一事实。我们已经注意到了张先生的八次交换过程中已有这种情况存在。
7、平面图不可免构形的分类和平面图的不可免构形集
虽然赫渥特图一类图，米勒图一类图，张氏图一类图的形成原理不同，但他们都属于具有两条相交叉的连通链且不能同时移去两个同色的H—构形；H—构形和非H—构形又都同属于5—轮构形；而5—轮构形则是平面图不可免构形集中的一个元素。所以我认为用着色法证明四色猜测时，只须证明到5—轮构形中的H—构形是可以4—着色的时就可以了，不需要证明更多的构形了，因为你也无法把H—构形中所有的构形都能找出。这样以来四色猜测也就无法用着色法证明而得到最终的结论，所以我一直是不主张用着色的方法对猜测进行证明的，而要走纯图论、纯数学、纯理论的道路。从研究图的色数与图的顶独立集数和最小完全同态的顶点数的关系入手，从研究多阶曲面上图的欧拉公式入手，求得图的色数（γ）与图的密度（ω）或图色数与图的亏格（n）之间的涵数关系。在平面图的密度不大于5和其亏格等于0的范围内，以证明四色猜测的是否正确。本人通过近三十年的研究，已用自已所提出的办法证明了四色猜测是正确的。其结果是：γ平面图≤ω＋S（当ω＝1，4时，S＝0；当ω＝2，3时，S＝1。式中S是图中某最大团外的不可同化道路的条数）和γ≤ （n≥0），当图是平面图（n＝0）时，γ≤4，这就是四色猜测（其证明见我的有关文章，我的博客网址是：http://blog.sina.com.cn/leiming1946）。
雷  明
二○一四年三月十四日于长安