对王树禾《图论》一书中所谓伯克豪夫钻石构形的4—着色

雷明85639720

对王树禾《图论》一书中所谓伯克豪夫钻石构形的4—着色
雷  明
（二○一五年九月十四日）

1、所谓伯克豪夫钻石构形：
一个多月前，一位名叫12341234的数字先生在网上提出了要张彧典先生给王树禾先生的《图论》一书99面中图5.16的所谓名叫伯克豪夫钻石的构形进行4—着色，并要张先生看该构形能归到张先生“九构形”中的哪一类的问题。

所谓伯克豪夫钻石构形，是一个有四个待着色顶点和六个围绕栏顶点的平面图（如图1）。图中a、b、c、d、e、f是围栏顶点，g、h、i、j是待着色顶点。这种构形属于用来代替5—轮构形的构形中的一种（其实阿贝尔的近2000个构形都是用以代替5—轮构形的构形，因为其他的构形早已证明是可约的了，阿的证明只是为了解决5—轮构形的可约问题的。），我个人认为它不仅不能代替5—轮构形，而且也是代替不了的。我还认为一个构形中只能有一个待着色顶点而不能有多个，因为待着色顶点再多，着色总是要一个顶点一个顶点的去着，最后总是只剩下只有一个待着色顶点的构形，只要把这个顶点着上了图中已用过的4种颜色之一，这个构形的着色就完成了，也就说明了该构形是可约的。如果一个构形可以有若干个待着色顶点，那么这“若干个”也可以认为是“无穷多”个，这无穷多个构形能验证得完吗，阿的近2000个构形是一个有穷集，他是否证明就只有这近2000个构形吗。后来又有人减少到1000多个，以至到更具体的633个，这似乎很精确，其实也并没有得到证明来说明平面图的不可免集就是只有这么633个。我认为平面图的不可免集就只有顶点度小于等于5的六种构形。
2、张彧典先生的回复：
张先生很快（8月17日）就进行了回复，全文我转录如下：
解答12341234先生的问题
                           张彧典
网友12341234最近问我：能否对王树禾教授在新版《图论》第99页的5-16所示构形归纳为我的九大构形中？
    现在我用《Appel-Haken第四不可避免构形的简化》中最后给出的求解法则来解答。

上面构形中红色所示就是网友12341234提出的构形，其中含有四个五度顶点。
首先，添加三条黑线使这个构形极大平面图化；
其次，把上面一个五度顶点作为待染色点V,  V的五个相邻点分别染色A1、B1、B2、C1、D1，其余四个点顺时针染色A、C、B、D，这样构造出一个Heawood反例类构形。
分析它的染色特征：右边A1-C1环内的红色B2-C链与环外的黑色C-D链、红色D-C1链以及V围成一个闭合圈，
与《构形同解的判定法则》一文总结出的三大法则比较可知，符合第二个法则，所以这个构形的解法与我的图3-2相同。
由于两个环的交点A在V的下方，所以具体解法只是把图3-2的解法中的内外互换一下就可以了：
在A1-C1环外颠倒B-D链的染色，生成B-C环；在B-C环内颠倒A-D的染色，生成新的A-C环；再在新的A-C环内把孤点B2改染色D,可以给V染色B.
希望网友具体操作一下吧。
同时我也8月17日对于2341234进行了回复，提目是《给12341234数字先生提出的图的着色》，并发表在《中国博士网》上，网址是：
张先生对12341234回复后，我在其后发了评论贴：“12341234所要求对这个构形的着色实在是太容易了，这个构形本身连一个顶点也没有着色，相当于一个图一样，不同的人可给出不同的解法。这里关键盘的问题是我们这位2341234数字权威大人，他就不懂四色猜测，不懂什么是构形。他就不知道构形是一个只剩下一个顶点未着色的图（当然我是不同意构形中有若干个未着色顶点的这种说法的），它都没有给出所谓围栏顶点的颜色，这算什么构形呢。12341234所给出的图，他说是一个构形，其中有4个待着色顶点，而张先生对其在着色时，还不是要把它看成是只一个待着色顶点的构形吗，这不就是一个5—轮构形吗。你用这么多的待着色顶点能代替得了5—轮构形吗。所以我就认为用别的构形来代替5—轮构形就是错误的，也不可能代替了，是一种绕着矛盾走的办法，最终还是不能绕过的。一个构形，其围栏顶点一定是要占用完了4种颜色的，而你这里的构形围栏顶点却有6个，占用四种颜色的方式有：其中一种颜色使用了三次，也可以是其中两种颜色分别使用了两次，你没有给明白，让别人怎么去着色呢。”
张先生的回复发出多少天后，12341234并不回复，也不知他是看到没有，还是有意不回复。在我多次的摧促下，他才不得不在近几天承认了张先生的着色是对的，但又强调说张先生把那个构形变成了极大图，说王树禾的原图不是极大图（在我的回复后，他把他的原贴删除了，我也引用不到他的原话了），要张先生再考虑等等。但对我的着色只字未提。
我对12341234的回复贴于9月12日发表了以下的回复：“不是极大平面图的图更容易着色，张彧典把图5.16的构形改为极大平面图了，都能4—着色，就说明王树禾图5.6那个构形是可约的。要知道，相同顶点数的图，从极大平面图变成非极大平面图时的色数是不会再增加的。难道这个构形的色数还会大于4不成吗。王树禾在这里明明说的都是三角剖分，即极大图，而“很好”却硬要说这里是一个非极大图，不知是为什么，也不知他看明白了没有。张彧典先生在王树禾的图5.16中增加的几曲线，并不是只是几条边，而是几条二色链，你认为张先生是把图变成了极大图也可以（当那几条链都是单边链时的情况），认为仍是非极大图（当那几条链都是非单边链时的情况）也可以。总之张先生增加的是链，而不只是边。在研究构形是否可约时，一般都是认为除了待着色顶点外，其他顶点是一个可4—着色的图，且构形的围栏顶点已占用完了四种颜色。可是王树禾对图5.16的着色时，其围栏顶点却只占用了3种颜色，这样的构形的着色并不是很难的，而难着色的构形则是围栏顶点已点用完了4种颜色的情况。王树禾对图5.6的构形着色中，认为其围栏顶点的“好着色”中，既有只占用了三种颜色的，也有占用完了四种颜色的，在他的所谓“坏分布”中，其围栏顶点也有占用完了四种颜色的，也有只占用了三种颜色的。不知道王的“好着色”和“坏分布”的标准是什么，概念是什么。我认为看书一定要看明白，不明白就要提出来，不能人家怎么说，自已也就怎么念。这永远是跟在别人后面跑，总是不会有自已的主见的。我看这里有一些人就是持这种态度的，书上怎么说，自已就怎么哼，完全没有自已的一点主见。这看书还有什么用呢。”
后来13日又有一位数字先生1234567发贴说了一通话后，我对其进行了两次评论：
1、我认为王树禾先生对其《图论》一书中的图5.6这个构形的着色存在着以下的问题：该构形有4个待着色顶点，有6个围栏顶点。王先生在对六边形的围栏顶点着色的31种色分布中，有用了3种颜色的，也有用了4种颜色的，这不符合围栏顶点全部占用完四种颜色的要求；王先生的所谓“好着色”与“坏分布”这两个概念不清，或者说就没有给以定义，因为在“好着色”和“坏分布”中均有既在围栏顶点中用了3种颜色的，也有用完了4种颜色的，使人不知道什么样的着色是好着色，什么样的是坏分布；进行坎泊链交换的目的是要把围栏顶点所占用的颜色由4变成（减少到）3，空出一种颜色给待着色顶点，而王先生在这里却明确说的是把围栏顶点所占用的颜色由3变成（增加到）4（在这里王说把围栏顶点的“坏着色121313能转换成‘好着色’121213和121343”），请问，这时待着色顶点该怎么着色呢？还有一点，王先生在这里谈到用坎泊链法时，也没有考虑所交换的链在围栏顶点中是否构成了连通链或者叫环链。连通时则不能交换，交换了也达不到减少围栏顶点所占用颜色多少的目的，而只有不连通时才可交换，也才能达到减少围栏顶点占用颜色的目的。另外，王先生谈到使用坎泊链法时说“这只要把Kemple链上的1与4或2与3互换即可”。既没有指出是交换那个顶点上的1与4或2与3（因为该构形的围栏顶点上有3个着1色的顶点，两个着3色的顶点和一个着2色的顶点），也没有考虑所交换的1—4色链和2—3色链是否连通的问题。以上问题，请网友们考虑。雷明
2、这位数字先生：你那样的不顾及围栏外各顶点的着色情况的着色方法，那一个不能对这个图5.16进行4—着色呢，连小孩子也可以做到。你说的“王树禾老师在《图论》第 100-101 页，是这样证明构形图 5.17(a) 是可约的 ---- 1。先设该图中间的 4 个顶点（从最上边那个顶点起，按顺时针方向）分别为 ghij。2。把图 5.17(b) 的 abcdef 各顶点分别着 121313 色。把 ghij 各顶点分别着 4242 色。3。因为 hj 这两个相邻的顶点均着 2 色，故可把 hd 两个顶点着的 23 色，互换为 32 色。于是，则有图 5.18 的 4-着色，即图 5.17(a) 是可约的！4。以上这些，是对该书第 101 页第 13-15 行“例如，……，2与3互换即可”文字的解释！”你解释了这些，还不如不解释。你明明知道待着色顶点h和j是相邻的，你为什么还要给他们两个都着上同一种颜色2呢。你把g和i着以4，把顶点h和j之一着上2，剩下的另一个顶点不就是一个度为5—的构形吗，这个5度顶点的5个邻接顶点已经占用完了4种颜色。这不就是待着色顶点的邻邦接顶点已占用完了4种颜色，如何给待着色顶点着色的问题吗。我不知你们为什么非要把这个只有一个5—度顶点的5—轮构形说成是有两个5—度顶点的双5—轮构形呢。你们不能证明5—轮构形是可约的，也不能用别的别的所谓构形来代替它而绕开矛盾走呀，你能绕开吗，最后还不是要对一个5—轮构形进行着色吗。由于这里不能画图，我将另文在你上面着色的基础上，用我说的办法，对分别以顶点h和j为只有一个待着色顶点的两个5—轮构形进行着色，来说明5—轮构形也是可约的，5—轮构形并不要用什么别的构形进行代替，也是代替不了的，客观的实际就是存在着5—轮构形，想绕着走也是不可能的。我将要进行的着色方法很可能在上次我对你提出的对该图的着色时我的着色文章里已经出现过，但那时与你对围栏顶点的用色不一定相同，所以这次我再给你着色一次，请你好好的看看，开开眼界。雷明
3、我对所谓伯克豪夫钻石构形的着色：
我按1234567数字先生说的把“abcdef 各顶点分别着 121313 色”和“把 ghij 各顶点分别着 4242 色”，作了如图2，a的图。因为顶点h和j是相邻的，直接着同一种颜色是错误的，所以我给其中之一先不着色，就成了两个5—轮构形（如图2，b，c），其待着色顶点的邻接顶点都已占用完了四种颜色。


对于图2，b，先从顶点g交换4—3链（如图3，a），再从顶点i交换4—1链（如图3，b），就可空出颜色4给待着色顶点j着上（如图3，c）。也可以先从顶点i交换4—1链（如图4，a），再从顶点g交换4—3链（如图4，b），也可空出颜色4给待着色顶点j着上（如图4，c）。



对于图2，c，先从顶点g交换4—3链（如图5，a），再从顶点i交换4—1链（如图5，b），也可空出颜色4给待着色顶点j着上（如图5，c）。也可以先从顶点i交换4—1链（如图6，a），再从顶点g交换4—3链（如图6，b），也可空出颜色4给待着色顶点j着上（如图6，c）。
再看看图图2，b，其中只有一条从顶点h到顶点a的连通链2—1，而没有从顶点h2到顶点f3的连通链2—3，所以还可以分别从顶点h或f交换2—3链，空出2或3给待着色顶点j着上，如图7。


再看看图图2，c，其中只有一条从顶点j到顶点c的连通链2—1，而没有从顶点j2到顶点d3的连通链2—3，所以还可以分别从顶点j或d交换2—3链，空出2或3给待着色顶点j着上，如图8。
以上的着色都没有考虑围栏顶点以外的连通链的情况，现在回头再看看这种情况：
最复杂的情况是构形属于H—构形的情况，即不能同时移去两个同色的情况。这一情况是在交换了关于一个同色（该图中为4）后，是否能形产生关于另一个同色的连通链，若都能产生，则是H—构形，若只有一个不能产生时，都是非H—构形，都是可以同时移去两个同色的。
对于图2，b，先从顶点g交换4—3链（如图3，a），不会产生i4到a1的连通链4—1，也就是说该构形是不可能有两条连通链相交叉的情况出现的，所以它是一个非H—构形的图（从以上我们的着色中就可以看出这一点）。若对图2，b先从顶点i交换了4—1链（如图4，a），也不会产生g4到f3的连通链3—4，因为h到a已有一条连通的1—2链，把3—4 链分成了环外环内不连通的两部分。如果说原本图中就有一条从i4到a1的连通链，我们可以不同时移去两个同色，而用如图7的着色办法解决，可以给待着色顶点j着以2或3。其他的如图2，c，同样的也可以用如图8的办法解决。这一点也能说明该图也是一个非H—构形的图。所以我一直说这是一个很容易着色的图。
4、结论：
这里的多待着色顶点的构形，既然是用来代替H—构形的，但从上面我们的着色中可以看出其根本就不是H—构形，这不是就说明了阿贝尔所着过色的那么多的构形，原本就都不是H—构形嘛，H—构形仍是没有证明是可约的。这也能叫做证明了四色猜测吗。
雷  明
二○一五年九月十四日于长安
注：此文已于二○一五年九月十四日在《中国博士网》上发表过，网址是：

雷明85639720

，，，，，，，，