与王树禾教授共同探讨有关着色问题

雷明85639720

与王树禾教授共同探讨有关着色问题
雷  明
（二○一五年九月十七日）

王树禾教授的《图论》一书（2008年1月第1版，2007年8月第4次印刷），我看了多次，可能是我不是专业人员，水平较低的原因，总感到“5.3 四色猜想为真的机器证明”一节中，有不少的问题不好理解或不能理解，但一直也没有提出来，最近网友们在网上进行关于“构形”的讨论，我又对该书这一部分进行了学习，过去的问题仍不能消除，所以我就冒昧的在这里提了出来，与王教授，与网友共同进行讨论。
1、关于“构形”的定义问题
什么是构形，王教授说：“平面三角剖分的某个圈中的导出子图称为一个构形（configuration），包围此构形的圈称为构形围栏，围栏上的顶数称为围栏长。”请问，“导出子图称为构形”，那么构形的围栏算不算构形的一部分呢。从书中的图可以看出“导出子图”中的所有顶点都是有待着色的顶点。从这个定义看，构形的待着色顶点可以是任意多的，那么构形也就无异于一个任意的平面图，与平面图则没有什么区别了。另外也可以看出，构形的围绕栏顶点也可以是无限多的。
我认为构形应该是“只有一个顶点未着上图中已用过的四种颜色之一的平面图。”这里说的构形就是一个任意的平面图，且是只有一个顶点未着色的图。因为要证明四色猜测为真，只要证明当图中其他顶点都已用四种颜色着色且满足着色要求（相邻顶点不用同一颜色）时，所剩下的唯一一个未着色的待着色顶点能够着上图中已用过的四种颜色之一就行了。
按我的定义，平面图的不可免构形集就是有限的，即待着色顶点的度是0，1，2，3，4，5的六种元素构成的集合。这是因为任何一个平面图中都不可避免的一定含有至少一个度小于等于5的顶点。也就是王教授书中的图5.11四个构形构成的集合的扩张（王教授的这四个构形是从地图的对偶图中得出的，而平面图中的却也又是存在着度为0和1的顶点的）。这个不可免构形集是有理论根据的，是可以证明的。这也就是王教授书中的定理5.5的“推论5.1 极大平面图T中，有一个至多5次的顶。”只要证明了这六种构形都是可约的，也就可以证明四色猜测是正确的。因为我们在着色时，总可以把图中某一个度小于等于5的顶点留下，作为待着色的顶点，这也是完全能够办到的，因为图中一定至少含有一个这样的顶点。
而按王教授对构形的定义，则平面图的不可免构形集则是一个无穷集合，不可能是有限的。当然也就是无法能够证明完毕。然而王教授的书中却认为阿贝尔用机器只验证了有限的（近2000个）由这种构形构成的集合是平面图的不可免构形集，又因为阿贝尔只是验证了其中的任何元素（构形）都是可约的，就认为这是证明了四色猜测是正确的。这合适吗。
2、我对构形可约的理解
王教授说：“如果一个构形C不含于4CC的最小（顶数最少）反例之中，则称此构形为可约的。它指出，若存在一个含构形C的反例，则我们能找到一个更小的反例。”我认为这里的“4CC的最小反例”就是一个顶点数最少的但不能用4种颜色来着色的平面图，只有这样，才称得上是4CC的反例。但这里说得有点含乎，不太明白，似乎应说成是“如果一个构形C不包含于4CC的最小（顶数最少）反例之中，则称此构形为可约的。”但后面的一句“它指出，若存在一个含构形C的反例，则我们能找到一个更小的反例。”还是不明白在说什么。至少王教授在书中把这句话再应说得祥细一点。
我认为可约构形应是不含“反例”的构形，即是最多可用四种颜色着色的构形。即可约构形一定是可用四种颜色着色的构形。
3、是否可用别的构形来代替5—轮构形的问题
平面图的不可免构形集中的5—轮构形，目前没有被证明是可约的，正象我们还不能解某一个方程一样，这个方程不可能是没有解的，只是我们还不会解它。5—轮构形没有被证明是可约的，也有可能其本身就是不可约的，若真是这样，四色猜测就不是真命题，也可以说是对猜测的一个证明。不一定我们就非得认为5—轮构形就一定是一个可约的构形。通过证明，是什么结果就是什么结果。5—轮构形是可约的，则猜测正确，否则则猜测不正确，只能是这两种相反结论中的一种。
把5—轮构形用别的构形去代替，这是一种绕开矛盾走的办法，其结果还将是绕不开的。这是认为5—轮构形就一定是可约构形的主观意断。是一种硬要把5—轮构形看作可约构形，而去寻找所谓的“证明”给以支持的做法，我认为这是行不通的。
前已述及，构形中只有一个待着色顶点，5—轮构形也不例外。而代替5—轮构形的构形中却至少有大于等于两个的若干个待着色顶点。待着色顶点再多，也得一个一个的去着色，当只剩下一个待着色顶点时，不就还是一个5—轮构形吗。能回避得了吗，能绕得开吗。如果这个5—轮构形中的待着色顶点能着上图中已用过的四种颜色之一，不就说明了5—轮构形也是可约的吗，为什么硬要说只有双5—轮是可约的呢。难道5—轮构形是不可约的吗，不可约还谈什么四色猜测是正确的呢。
如果说5—轮构形能被别的构形所代替，阿贝尔也证明了那些用以代替5—轮构形的构形都是可约的，当然也就说明5—轮构形也就是可约的了，这不就证明了平面图的不可免集中的所有的6种构形都是可约的了吗，四色猜测不就是得到证明是正确的了吗。证明中为什么要用那么多的构形呢，一个双5—轮构形不就可以说明5—轮构形也是可约的了吗，难道非要费那么大的气力去让计算机代替人去证明呢。
如果说这些用以代替5—轮构形的构形都是可约的，但还不能说明5—轮构形就是可约的，那么用他们去代替5—轮构形有何用呢，不仍然说明5—轮构形还未证明是可约的吗。平面图中不可避免的一个5—轮构形都是不可约的，那还能叫做四色猜测被证明是正确的吗。是不是只能得到其否定的结论呢。仔细分析阿贝尔验证所得的结果是自相矛盾的。
4、如何正确认识公式∑（6－k）•pk＝12的问题
公式∑（6－k）•pk＝12的展开式是：
4p2＋3p3＋2p4＋p5－p7－2p8－3p9－……＝12         （1）
式中： k是极大平面图每个顶点的度，pk是k度顶点的个数。这就是王教授书中的定理 5.5；
公式∑（6－k）•pk＝12还可以表示成∑（6－k）•Fk＝12，其展开式是：
4F2＋3F3＋2F4＋F5－F7－2F8－3F9－……＝12         （2）
式中：k是地图中每个区域的边数，Fk是边数为k的区域的个数；
由于极大图与3—正则的平面图（即地图）是互为对偶的，所以同一个公式就有了以上两个不同的表达方式。这两个方式都是可以通过欧拉公式推导出来的，都是有理论根据的。其推导过程在张彧典先生的《四色问题探秘》一书和其他文献中都有。上两式是一个恒等式，对于任何极大平面图与3—度正则的地图都是适用的，但对于其他的平面图是不适用的。
公式（1）∑（6－k）•pk＝12和公式（2）∑（6－k）•Fk＝12都是一个恒等式，对于任何的极大图与3—正则图（地图）都是适用的。公式（1）只能说明任何平面图中至少都一定存在一个度是小于等于5的顶点，这就是平面图的不可免度集，公式（2）也只能说明任何地图中也至少都一定存在着一个边数小于等于5的区域，这也就是地图的不可免区域集。我认为该公式再无它用。
5、如何运用公式∑（6－k）•pk＝12的问题
王教授在证明他书中的定理 5.6  即证明Wernicke1904年构造的构形集是不可免集时，用了所谓的放电原理，认为“带一个单位正电荷的每一个5次顶向每个带负电荷的邻顶输送1/5个电荷。如果不存在5次顶与6次顶或5次顶与5次顶相邻的现象，每个5次顶必有5个开始时带负电荷的邻顶，即5次顶与7次以上的顶相邻，最后5次顶上的电荷变为0。考虑k≥7的顶，即使这种顶的邻顶皆5次顶，这种k次顶所获电荷最多为k/5，使它带的总电荷数为（6－k）＋k/5＝6＋k/6－k＝（36－5k）/6＜0。于是T（王教授前面已定义“T是一个不含2次、3次和4次顶的三角剖分”——我注）上的总电荷量是是负的，不是12，此矛盾。”这就证明了Wernicke的构形集是不可免集。这里虽是证明Wernicke的构形集是不可免集，但整个证明过程中却没有涉及到Wernicke的构形集的任何信息，是否这种证明方法对于任一个构形集都可以这样来证明呢。接着王教授又说“用这样电荷输送的技术”阿贝尔又证明了其他几个构形集是不可免集。
这里存在几个问题；一个是很明显的（6－k）＋k/5＝6＋k/6－k＝（36－5k）/6＜0是错误的，应该是（6－k）＋k/5＝6＋k/5－k＝（30－4k）/5，然而（6－k）＋k/5＝6＋k/5－k＝（30－4k）/5也不一定是小于0的，例当k＝7时，其值是2/5而不是小于0。另外，这里说的只是一个度大于等于7的顶点的电荷数，怎么能与全图的中的总电荷数是12相比较呢。“带一个单位正电荷的每一个5次顶向每个带负电荷的邻顶输送1/5个电荷。”这里为什么只选择“输送1/5个电荷”而不选择别的电荷输送量呢。
定理 5.5 ∑（6－k）•pk＝12或4p2＋3p3＋2p4＋p5－p7－2p8－3p9－……＝12只是说明任何极大平面图中各顶点的度数被6所减所得的差的和都是恒等于12的。把某些5—度顶点的正电荷输送到带负电荷的某些次数大于等于7顶点上去，只相当于这一部分正负电荷相互抵消，但对于全图来说，剩余的电荷总量还应是12，不应发生变化。比如，一个算式
1＋2＋3＋4＋5＋6＋0－1－2－3－4－5－6－7＝－7
把正项的值各减去1，加到（输送到）负项中去，则是
（1－1）＋（2－1）＋（3－1）＋（4－1）＋（5－1）
＋（6－1）＋0（1－1）＋（1－2）＋（1－3）＋（1－4）
＋（1－5）＋（1－6）－7＝－7
最后得到
0＋1＋2＋3＋4＋5＋0＋0－1－2－3－4－5－7＝－7
两边都是－7，算式两边的结果并没有变化。
应该说，对于任何一个具体的图，其∑（6－k）•pk全都是恒等于12的，不管放电不放电，结果都是一个恒定的值12。就仅仅因为一个7—度顶点的电荷数不等于12（或者是负数），就说明T中的电荷总量与∑（6－k）•pk＝12是相矛盾的，而得到Wernicke的构形集是不可免集，这未免也有点太荒唐了吧。公式∑（6－k）•pk＝12与一个构形是不是平面图的不可免集又有什么关系呢，关于这一点，王教授在书中并没有提及任何说法。从证明的最后看，这好象是用的反证法，因为他认为得到了矛盾的结果，但在前面却没有看到反证法的假设是什么。这简直是牛头不对马尾的在凑合嘛。道理是不通的。
书中以上的所谓证明都只是说明了用以代替5—轮构形（严格说，主要是代替赫渥特的H—构形的）的几个构形都是不可免的，但并没有证明这个不可免构形集有多大，即其中有多少个元素。从阿贝尔的机器证明起，这个不可免构形集的元素个数由近两千个，几次进行减少，最后说只有633个。这样一个元素个数处在不断变动中的构形集，能叫做不可免集吗。从阿贝尔的近2000个不可免的构形到633个，相差一千多个构形。以前说这一千多个构形是不可免的构形，现在怎么又成了可免构形了呢。这633个构形中会不会还有可免构形呢，这个633是否经过证明就是平面图不可免集的最终大小呢。
另外，“放电”一词本来是物理学中的术语,我总觉得把放电原理用在图的着色上,并不合适。
6、关于书中“5.3.4  可约性”一小节中的问题
王教授这一节主要是通过以伯克豪夫钻石构形为例来展示如何证明一个构形是可约的。
关于该构形的4—着色问题，本人已写了两篇文章，即《对王树禾〈图论〉一书中所谓伯克豪夫钻石构形的4—着色》和《再谈伯克豪夫钻石构形的4—着色》两文，均已发表在本论坛中（网址分别是：
和
）。请朋友们去看。
从对伯克豪夫钻石构形着色中可以看出，该项构形实际上最后还是按5—轮构形去进行着色的，这个构形只是一个5—轮构形，但并不是H构形，它是可以同时移去两个同色的。这个构形虽能4—着色，是可约的，但并不能说明同属于5—轮构形的H—构形也是可约的，所以从总体来说，也就不能说所有的5—轮构形都是可约的。这样也就不能说四色猜测就得到了证明是正确的。用它来代替5—轮构形，然而最终仍没有能够证明5—轮构形一定都是可约的，那么还要去用机器验证那么多的有若干个待着色顶点的构形是干什么呢。实在是没有必要。
除了以上所说外，书中本小节还有以下几个问题：
1、这里用了“最小反例”的术语，书中没有进行定义，是否是“不能4—着色”的意思呢。如果是这样，那么“T是4CC的最小反例”，就说明T是不可4—着色的，则T中至少有一个顶点是用了第5种颜色的。“设T中含有伯克豪夫钻石构形，并且T＇是T上把伯克豪夫钻石上的内部4个顶删除后得到的图。则T＇是4色的，即χ（T＇）≤4。”这就意味着伯克豪夫钻石构形的4个待着色顶点（内部顶点）中至少有一个是要着上第5种颜色的。因为T是5色的，T＇是4色的，其中没有一个顶点用了第5种颜色，那么T－T＇＝伯克豪夫钻石的4个内部顶点，其中必有一个顶点是用了第5种颜色的。王教授接着说：“为了得到矛盾，我们将证明T＇的每个四色上色可以扩充为T的一种四色上色。”可以想象得到，如果伯克豪夫钻石的4个内部顶点可以不用第5种颜色，则该构形就是可约的，否则则是不可约的。这可能就是阿贝尔机器“证明”的主要出发点吧。我认为这个出发点应该是对的。
2、研究伯克豪夫钻石构形的可约性，主要应研究如何能使得该构形的4个内部顶点不用第5种颜色，这是主要目标（书中在谈到这一方面时，却只用了一在话，这也太的简单了，读者一下子还是看不明白的），而不能把主要精力用在研究其围栏顶点构成的六边形的6个顶点如何着色上，这里是否有点主次颠倒了。我认为，不要把各种可能的六边形的着色都列举出来，只要有一个可以达到使伯克豪夫钻石构形的4个内部顶点不用第5种颜色就可以了，这就已经能够说明该构形是可约的了。在研究六边形的着色中，不知六边形顶点上的色分布，为什么只用了3种、4种颜色，而没有用两种颜色着色呢。的确，六边形是可以用两种颜色来着色的。若六边形用了两种颜色来着色，那就是一条环形的二色链，这种情况在图着色中也是经常可以看到的，例如米勒的图（M—构形）中就含有这样的六边形的二色链。
3、这里提出了“好着色”与“坏分布”两个概念，但没有定义，是否可以这样理解：好着色就是指六边形的某个着色模式能够直接使得伯克豪夫钻石构形的4个内部顶点只用4种颜色；而坏分布则是指六边形的某个着色模式不能够直接使得伯克豪夫钻石构形的4个内部顶点只用4种颜色，而必须施行坎泊的颜色交换技术，才能使其着上4种颜色。


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

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