再评11223344介绍的两个贴子

雷明85639720

再评11223344介绍的两个贴子
雷  明
（二○一六年元月三十日）

11223344所介绍的“紫色”的博客中转载87674938的两贴，其题目分别为《在k＝0时，定理10.20的证明不成立》和《如何证明构形是可约的》（见附后），现对其评论如下：
1、对《在k＝0时，定理10.20的证明不成立》的评论
㈠　哈拉里《图论》书中公式12.12中的向上取整符号用错了。因书中公式12.7是向下取整的，用的是符号是[ ]，而书中公式12.14是向上取整的，用的符号是{ }，而这里的公式12.12是对p≥（7＋√（1＋48n））/2取整，应是向上取整，应用与公式12.14中相同的向上取整符号{ }，而作者却用了与公式12.7中相同的向下取整符号[ ]，是不应该的。[ ]意为不大于[ ]中的数字的整数；而{ }则意为不小于{ }中数字的整数。
㈡　贴中说：“⑶ 在n＝0时，图G为极大平面图，并由（12.12）式，可得p≥4。因为不能证明所有极大平面图为4—着色的，所以在n＝0时，（12.7）式的证明是不成立的，即在k＝0时，《图论导引》定理10.20的证明不成立。”这段话有好几个地方都是错误的：①首先，哈拉里的书中一开始证明之前就在公式12.7和12.8中都已经有了（n＞0）的附加条件，这就说明哈拉里本身就没有证明在n＝0时，公式12.7是否成立的问题，所以说这里说的这一段话是没有任何意义的。它只能说明写此话的人认为在n＝0时，公式12.7是不成立的，但他并没有去证明，据何下这样的结论呢。②再看“所以在n＝0时，（12.7）式的证明是不成立的”这句话，道底是公式12.7本身不成立呢，还是对公式12.7的证明不成立呢，没有说清楚。从字面上看，好象说的是在n＝0时，“证明”不成立，但人家哈拉里本来就没有进行证明，何言成立不成立呢。哈拉里只是在公式后附有条件（n＞0），而并没有说公式12.7就不适用于n＝0的情况，反而是说12.7式“在n＝0时的特殊情形就是4CC。”这个“特殊情形”是指“n＝0”本身，还是指n＝0时的某些情况，还有待研究。我认为就是指“n＝0”本身。
㈢　因为哈拉里《图论》书中的公式12.7就是沙特朗《图论导引》书中的公式10.20，再由于㈡中的错误，所以本贴的题目《在k＝0时，定理10.20的证明不成立》也就是错误的。本贴的目的本来是要说明在k＝0时，沙特朗《图论导引》书中的定理10.20是不适用的（当然也包括在n＝0时，哈拉里《图论》书中的公式12.7也是不适用的。），但他却没有说清楚，甚至连题目也都是错误的，别人看了后还以为是说沙特朗对定理10.20的“证明”是“不成立的”呢。
2、对《如何证明构形是可约的》的评论
㈠　该贴实际上是通过张彧典先生的的口气，把坎泊过去的证明再重复了一次。但他绕来绕去，还不如直接去看坎泊或张彧典先生的证明。
㈡　该文中对于坎泊未证明的一种有两链相交叉情况的构形的着色本来是正确的，他却不相信自已的证明是正确的。他也不去分析一下，5—轮构形除了此种构形以外，还会不会有别的构形，就直接说了“但是，有二色链 A—C—A与A—D—A相交的平面图还有很多，用这种方法并不能给它们都着上4色。”他就没有看一看，除了这个构形外，5—轮构形真的是再也没有别的情况的构形了。这里顺便要说一下，该贴的作者这里对赫渥特“九点形”的4—着色，方法步骤太多，很烦锁，不如直接把顶点A2换成B（即交换A—B），使A—C链和A—D链断开，图中不再存在连通链，再交换一步即可给V着A、C、D三种颜色之一（如图1），共用两次交换。而该作者却用了三次交换。
  

㈢　该贴作者说：“在把图G的顶点A2和与其有关连线去掉后，该图则退化为 Wernicke 定理的（5—5）构形。因此，图G是（5—5）构形的一种着色情况，将无法证明（5—5）构形是可约的。”又说：“有二色链A—C—A与A—D—A相交的平面图还有很多，用这种方法并不能给它们都着上4色。因此，具体图G可着4—色，并不能证明d（v）＝5和（5，5）构形是可约的。”
这个有两条交叉链的“九点形”图，是一个顶点数非常少的图，而往往是顶点数少的图比顶点数多的图还更难着色一些（这就是张彧典先生说的构造构形时的“顶点最少的原则”）。例如我们在上面这个“九点形”图中再增加几个顶点，如图2。这两个图都是可以同时直接移去两个同色B的，比上面的两种着色方法都要快一些，只要同时交换两个关于同色B的链即可。
这个“九点形”是一个具体图，又是一个构形，你说说那个构形不是一个具体的图呢。这个图中无论是在哪一条边上，或是在哪一个面内，还都是可以再增加顶点和边的。从这个意义上来说，这个“九点形”又不是一个具体的图。要认为d（v）＝5和（5，5）构形是不可约的，就得要找出一个不可约的5—轮构形来，作为反例；如果没有，就没有资格下结论说d（v）＝5和（5，5）构形是不可约的。难道这就是87674938和11223344所说的（5，5）和（5，6）构形都是不可约的原因吗。

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

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

附：87674938的两个贴子：
一、在k＝0时，定进10.20的证明不成立
1。这个问题，可点击（网址） 见 G. 沙特朗 等《图论导引》k第 259 页的习题 10.21。关于 Heawood（希伍德）地图着色定理的由来，及其证明等，可参见以下图书。
2。可点击（网址 ）见 F. 哈拉里《图论》第 156-158 页。
    (1) 在证明《图论》第156 页不等式（12.7）即《图论导引》的定理10.20 时，已设图G 是一个三角剖分，是可以嵌入亏格为 n 的曲面Sn 的极大图。其顶点数，边数和面数，分别为 p，q 和 r 等。
    (2) 设 d 是图G 顶点度的平均值，可有 dp=2q=3r 即《图论》（12.9）式。因为 q = dp/2， r= dp/3，把 p，q 和 r 代入《图论》第 136 页的（11.4）式，可得 d =6 - 12（1-n）/p =12（n-1）/p + 6 即《图论》（12.10）式。因为 d <= p-1，可得 p-1 >= 12（n-1）/p + 6 即《图论》（12.11）式。解（12.11）这个方程，p 取正解，则可得《图论》（12.12）式。这里的 p 值，为图G 可以嵌入曲面Sn 的顶点个数。
    (3) 在 n = 0 时，图G 为极大平面图，并由（12.12）式，可得 p >= 4。因为不能证明所有极大平面图为 4-着色的，所以在 n=0 时，（12.7）式的证明是不成立的，即在 k=0 时，《图论导引》定理 10.20的证明不成立。
3。《图论导引》一书的译者范益政，今天上午对这个问题的答复为： 在该书第258页中，第二个不等式成立的条件是 k-1 >= 0 。因此，才有习题 10.21。（此第 3 点为 2015-12-02 18:30 新加的）                                                                                       ------ 网友“87674938”写于 2015-11-30

二、如何证明构形是可约的
1。张域典在《四色猜想图表解》见 （网址），谈到“肯普的证明”。这里，只从给构形着 4 色的角度，结合该文谈谈如何证明构形是可约的。
2。把该文第 2 页“独创了肯普链法”中的图设为“图K”。图K 的 V 面围栏 4 个面，是着 ABCD 色的。这时，在着 A 色面和着C 色面之间，有无 A-C-A 二色链（注意：当图K 为构形时，围栏外的二色链连线应该为虚线；当图K 为具体图时，围栏外的二色链连线应该为实线）可分为：（1）无 A-C-A 二色链时，可把着 C 色面改着 A 色，可给 V 面着 C 色，使图K 为 4-面着色的。（2）有 A-C-A 二色链时，可把着 D 色面改着 B 色，可给 V 面着 D 色，使图K 为 4-面着色的。于是，可证 d(v)=4 构形是可约的。应该看到，这种方法是证明 d(v)=4 构形是可约的一般方法Q。它已经考虑到了，包括围栏之外所有面在内的，各种平面图可能有的不同着色情况。
3。对该文第 3 页“肯普链法的应用”中 d(v)=5 构形，运用方法Q 可证，该构形在图(1)（注意：此时，顶点B2和C1 之间的连线，应该是虚线） 和 图(2) （此时，顶点 A1 与顶点 C1 和 D1 之间的连线，应该为虚线）的情况下是可约的。
4。把该文第 3 页“肯普链法的不足”中的图设为“图G”。图G 的二色链  A-C-A 与 A-D-A 是相交于顶点 A2 的（此时，顶点 A2 与顶点 C1 和D1 之间的连线，应该为虚线）。该文运用方法Q 却无法证明，该构形是可约的。同时，也没有找到其它的一般方法证明，该构形是可约的。同时，在把图G 的顶点 A2 和与其有关连线去掉后，该图则退化为 Wernicke 定理的（5-5）构形。因此，图G 是（5-5）构形的一种着色情况，将无法证明（5-5）构形是可约的。该定理可见 （网址） 王树禾《图论》第99 页。
5。可以看出，判定某个构形 M 的可约性，并不只是要找到一种方法 W，能给构形M 在某种具体情况 U 时（例如，d(v)=5 构形为具体图G）着 4 色的问题。关键在于，还要确定方法 W 是否为，能给与构形 M 在情况 U 时的条件相符的所有平面图，都着上 4 色的一般方法。例如，对于具体图G，先在 A-C-A 二色链内，把顶点 B1 和 D2 着色改着为 D 和 B，可生成B-C-B 二色链。再在 B-C-B 二色链外，把顶点A2 和D1 着色改着为 A 和 D，可生成新的 A-C-A二色链。最后，在这个新的 A-C-A 二色链内，把顶点 B2 着色改着为D，可给顶点V 着 B 色，也可使图G 为 4-着色的。但是，有二色链 A-C-A 与 A-D-A 相交的平面图还有很多，用这种方法并不能给它们都着上4色。因此，具体图G 可着 4 色，并不能证明 d(v)=5 和（5-5）构形是可约的！
                                                                                   ----- 网友“87674938”写于 2015-10-24

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，，，