浅谈敢峰张彧典雷明三人的平面图着色理论

雷明85639720

浅谈敢峰张彧典雷明三人的平面图着色理论
雷  明
(二○一八年六月十八日)

在对四色猜测的证明过程中，四十年来，雷明、敢峰，张彧典三人都是用了给地图的对偶图顶点着色的办法进行证明的，都是把对无限的平面图的着色变成了对有限的不可免构形的着色的办法，把无限的四色问题变成了一个有限的问题进行解决的。从最近敢峰先生写成的《四色问题终极证明之路——四证四色定理兼论终极图》（简称《四证》，还未发上网）和张彧典先生6月14日在《中国博士网》上所发的《四色猜想中的染色困局构形猜想》的贴子看，三人的理论统一的时机已基本成熟，有望在不久的将来可以得到统一，希望三位老先生携手完成这一大业。
（一） 有关平面图H—构形的一些问题：
1、平面图H—构形的定义：
为区别可以直接使用坎泊的空出颜色的颜色交换技术，和区别直接从5—轮的轮沿顶点进行交换，就可空出颜色给待着色顶点着上的构形；我们把不可直接使用空出颜色的颜色交换技术，而必须使用断链交换或转型交换的坎泊颜色交换技术，先使构形进行转型，以便于使用坎泊的空出颜色的颜色交换技术，空出颜色给待着色顶点着上的构形；叫做H—构形，相应的也就把可直接使用空出颜色的交换而空出颜色给待着色顶点着上的构形，叫做K—构形。因此，H—构形的定义应是：
不能使用空出颜色的交换空出颜色给待着色顶点着上的构形。相应的把可直接使用空出颜色的交换空出颜色给待着色顶点着上的构形就是K—构形。
2、平面图构成H—构形的条件：
根据赫渥特图的特点，可以看出构成H—构形的必要条件是有两条有同一起始顶点的相互交叉的连通链。但这并不是充分条件，因为即就是有了这样的条件的图，并不都是H—构形。如BAB型的九点形构形中除了有C—D环形链的一个是H—构形外，其他的三个都不是H—构形。因为这三个构形都可同时移去两个同色B。因此，把H—构形也可说成是不可直接空出任何颜色给待着色顶点，而必须使构形转型成K—构形的图。
3、平面图H—构形的不可免集：
构成H—构形的BAB型的图中一定含有连通且相交叉的A—C链和A—D链，这是构成H—构形的必要的条件。既然是连通的链，就不可能再进行交换，因为交换了这样的链是不可能空出颜色的。再看图中还有的B—C链和B—D链，该两链又不能同时交换，所以也不可能同时移去两个同色B。因此，这两条链也是不能交换的。四种颜色所能构成的六种链中，已有A—C，A—D，B—C，B—D四种链不能交换了，固定死了，不能动了。那么就只有A—B链和C—D链两条链可以动了。
A—B和C—D这两种链在图中的分布关系只可能是：
A类，有一条环形的A—B链；
B类，有一条环形的C—D链；
C类，既无环形的A—B链，又无环形的C—D链；
D类，在C类中的构形中，又有以一条A—B链作为构形的对称轴的对称构形；
E类，既有环形的A—B链，又有环形的C—D链，既可归入A类，也可归入B类，也就不再单独列为一类了。
C类中又可分为左式和右式，因为C类是非对称的构形。
A—B和C—D这两种链在图中的分布关系除了以上的A、B、C、D四种外形式外,再也没有别的形式了，所以由以上的A、B、C、D四类构形就构成了H—构形的不可免集，而且是完备的。
4、平面图各类不可免构形的着色方法：
以BAB型的构形为例进行说明。
（1） A类构形中有一条通过5—轮轮沿1B—2A—3B三个顶点的A—B环形链，把C—D链分隔成互不连通的两部分，交换A—B环形链内、外的任一部分C—D链，都可使连通的A—C链和A—D链断开，使图成为K—构形而可约。
（2） B类构形中有一条通过5—轮轮沿4D和5C两个顶点的C—D环形链，把A—B链分隔成互不连通的两部分，交换C—D环形链内、外的任一部分A—B链，都可使连通的A—C链和A—D链断开，使图成为K—构形而可约。
（3） C类构形中没有环形链，A—B链和C—D链都不可交换（交换了也不可能使图转型的），六种链都不能交换，怎么办呢？还有办法。B—C链和B—D链不是不可同时交换吗，那就先交换一个吧。先交换一个，就可先移去一个B，使图进行转型，由BAB型转化成DCD型或CDC型。无论是从逆时针还是顺时针哪个方向转型交换，由于C类分左式和右式，所以左式右式交换的结果是不同的。一种是直接转化成了可以连续移去两个同色C或D的K—构形；一种是转化成了有环形链A—B的B类构形，再按B类构形去解决即可。
（4） D类构形中也没有环形链，也需要进行转型交换，但连续两次同方向的转型交换后，得到的是一个非对称的C类构形，再按C类构形去解决即可。可见D类构形解决时，一定要先把图转化为非对称的C类构形。
5、平面图各类H—构形间的关系：
D类对称的H—构形可以转化成C类非对称的H—构形，需用要两次转型交换。C类非对称的H—构形进行转型交换，一种是直接转化成可连续移去两个同色的K—构形；另一种是转化成B类H—构形。B类H—构形进行断链交换，可直接转化成K—构形。A类H—构形进行断链交换，也可直接转化成K—构形。其关系用图表示则是图（一）。

（二）敢峰张彧典雷明三人对四色问题的研究工作：
（1） 敢峰先生的研究工作：敢峰先生1992年就用反求思路构建四色不可解线路集合、经过二十步大演绎的方法构造了”终极图”,创造了他在四色猜测证明中的“终极图”理论，创造了四环演绎和三环演绎法，并于1992年对“终极图”进行了4—着色（英国的米勒也在相同时段构造出了完全相同的图，但米勒未能对其进行4—着色，所以我称该图为“敢峰—米勒图”）。敢峰先生对该图所用的方法也就是雷明先生后来称作“断链交换”的方法。敢峰先生认为“终极图”中有一条环形的A—B链，把C—D链分隔成了环内、环外互不连通的两部分，交换任一部分C—D链，都可以使连通且相交叉的A—C链和A—D链断开，使图变成K—构形而得解。最近，敢峰先生又在其《四证》中对他的“终极图”进行的强行着色，也都是成功的。敢峰先生认为他的“终极图”涵盖了一切的构形，用一个“终极图”就可证明四色猜测是正确的。但笔者认为这是不可能的。因为对他的“终极图”进行演绎时，只能得到上述的A类和B类的H—构形，而不可能得到C类和D类的H—构形。所以，敢峰先生的“终极图”法是不能最终证明四色猜测的。敢峰先生在《四证》中还说：“在构建终极图的过程中，还可以终极得到四色可染定律：任何具有双环交叉五轮图构形的图，无论是否为终极图，都是四色可染的。其极限是16步。一般情况下，四步可染。至于非双环交叉构形的五轮图和非五轮图，显然都是四步之内可染的。”但这是一定要经过证明的，不能只是说说而已。希望敢峰先生进一步作工作，进行证明。同时，也希望敢峰先生把四环演绎和三环演绎讲得更明白一些，各个演绎都是怎么演绎的，两者的区别在什么地方，最后的结果又是什么。这都是读者需要明白的地方。
（2） 雷明先生的研究工作：雷明先生对赫渥特图的研究中，于1990年成功的对赫特图在赫渥特原着色的基础上进行了4—着色（1992年在专业的学术会议上作了学术论文报告），进一步坚定了他对四色猜测用手工证明的信心。通过对赫渥特图的着色，总结出了在一个环形的链的任一侧交换与环形链呈相反色链的链，虽不能空出颜色给待着色顶点，但可以使BAB型的H—构形中的连通且相交叉的A—C链和A—D链断开，成为K—构形的图，改变图的类型，为下一步进行空出颜色的交换创造条件。这就是雷明发现的坎泊所创造的颜色交换技术的另一个作用——断链的作用。同时，通过对赫渥特图的着色，也发现了赫渥特的错误所在——赫渥特第二次交换的是一条不可空出颜色的连通链，当然就不可能移去另一个B了。雷明先生还对平面图的顶点同化进行了研究，发现了不可同化道路，总结了平面图的色数只可能比其密度大1，但当平面图的密度是4时，图中就不可能再有不可同化道路，其色数一定是不大于4的。这也就证明了四色猜测是正确的。雷明先生根据构形（图）中是否含有环形链，把H—构形分为A、B、C、D四类，构成了H—构形的不可免集，研究了该集中每一种不可免构形的单独着色方法，证明了四色猜测是正确的（并在研究C类H—构形的着色方法中，应用了坎泊创造的颜色交换技术的第三种作用——转型的作用）。雷明先生认为敢峰—米勒图只是A类H—构形中的一种，敢峰先生的对该图的大演绎，张彧典先生对该图的连续颠倒，都只是表现在，图是在A类H—构形与B类H—构形间的无穷尽的循环转化过程中。关于BAB型的A类H—构形中，含有通过5—轮轮沿1B—2A—3B三个顶点的环形的A—B链的这一特点，可以说是雷明先生首先提出的。
（3） 张彧典先生和米勒分别研究的工作：张先生是在1992年完成了他的八大构形的（实际上其中的第一构形，第三、第四、第五、第六、第七构形都不是H—构形，因为其都是可以连续移去两个同色B的。而只有第二构形和第八构形，才是真正的H—构形），后来又用了很大的精力，花去了整整五年的时间，再也没有找到难点转化次数大于7的构形，也即没有找到颠倒次数大于8的构形。在此同时，也是在1990年，英国的米勒也对赫渥特图进行了研究，采用连续颠倒（即转型交换）方法，也对赫渥特图在赫渥特原着色基础上进行了4—着色。创造了连续颠倒法。他们企图以此想进一步证明四色猜测是正确的。但米勒在此不久之后的1992年，又构造出了米勒图——一个与敢峰的“终极图”完全相同的图。却无法用他创造的连续颠倒法对其进行4—着色，出现了无穷循环的现象。因而却又放弃了他们原来的想法，但至今未见任何进展。张彧典先生对其八个构形的着色，也是用的连续颠倒法，与米勒是不谋而合的。但当他在1999年接到英国的来信，看到了米勒图后，也是无法用连续颠倒法对其着色的。因此，张先生又“创造”了Z—换色程序，用此方法单独的对米勒图进行了4—着色（然而这种所谓的Z—换色程序与敢峰先生在1992年用以给敢峰—米勒图进行4—着色时，已使用过的方法的原理和程序是完全相同的）。在这种情况下,张先生也只好把米勒图作为一个不可免的构形。这样，就使他原有的不可免构形集由八个构形增加到了九个构形。张先生的构形集中的第八个构形，是一个既无环形的A—B链，又无环形的C—D链的构形，为雷明先生提出的C类H—构形打好了基础（当然，米勒图中有一条A—B环形链，也为雷明先生提出的A类H—构形打好了基础）。后来，张先生又介绍了1935年美国人Irving Kittell构造的一个对称的图（构形），又为雷明先生提出D类H—构形打好了基础。
（4） 张彧典先生的理论，用连续颠倒着色的方法和Z—换色程序，虽然也是可以给平面图进行4—着色的。但还需要进一步证明，有限的颠倒最多是多少次，以及无限循环的颠倒的构形（图）是否就只有敢峰—米勒图一个。有了这两个证明，张先生的理论也就更加完善了。关于这两点，雷明先生曾给张先生指出过多次，认为张先生的不可免构形集是没有经过严格证明是否完备的，但张先生却一直没有在乎。还好，最近张先生发现了颠倒次数大于8，而达到14次的图（构形），并在网上征求颠倒次数更多的构形（图）。同时，也在同一贴中张先生还提出了最多只需18次颠倒的“最后猜想”。从这里看，就完全说明了张先生原先的构形集是不完备的，是没有经过证明的。雷明先生提出的看法也是正确的。张先生最近的颠倒次数只需18次的新猜想，与敢峰先生最近提出的演绎或颠倒次数的“极限是16步。一般情况下，四步可染”的结论也是不谋而合的。但是否最大就是16步或18步，下限是否就是4步，希望子二人携手共同进行证明。
（5） 不管怎么样，我仍然认为以颠倒次数的多少来划分构形类型是不科学的，是错误的。因为这种分类方法没有涉及到构形的本质，即构形的特征。说得明确一点，就是没有涉及到构形中链与链的关系。这样就产生了张先生的H—构形不可免集中的构形数量在不断变化的情况。原先最早是八大构形，后来出现了敢峰—米勒图，无法着色，又成了九大构形；又曾一度减少到4个构形；现在又出现了至少有十四类构形的不可免集；并提出了最多有18次颠倒的“最后猜想”。这不就都说明了依据颠倒次数的多少给构形分类的方法是不科学的吗。三十多年过去了，从开始研究时的“坎泊猜想”，到今天的研究结果仍然是“张氏猜想”，不还都是“猜想”吗，有一点点进展没有呢，这三十多年证明的结论是什么呢。

以上三人的理论对四类构形的着色适应情况如下表一：

                                             （表一）
H—构形的类型            A类H—构形                        B类H—构形                   C类H—构形                          D类H—构形                           备     注
                           代表作是敢—峰米勒图          代表作是赫渥特图          代表作是张氏第八构形          代表是Irving Kittell的图       
    雷明理论                            √                                  √                                  √                                           √                        应该说比较完善
    张氏理论                            √                                        √                                  √                                           √                               还需补充证明
    敢峰理论                            √                                        √                                  ×                                           ×                              需完善所适构形

    看来三人的理论完全有统一的希望。我们共同携起手来，完成这一大业。


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

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