对万春如的译文《一种试探式的平面图四染色》的评论

雷明85639720

对万春如的译文《一种试探式的平面图四染色》的评论
——与张彧典先生交换意见
雷  明
（二○一七年十一月二十九日）

张先生，几个月前看了你所发的万春如先生的译文后，随便写了几句，不成文章，也就没有在网上发表。今天发现这个搞子后，也就随手发表在这里，也是与你的相互交流。
（一）
张先生，是作者的原因，还是译者的原因，文中对坎泊方法的叙述，还没有我们（你和我）自已的叙述好理解。
1、其对于度为3和4的顶点的着色完全与坎泊的方法是相同的；
2、对于3度和4度顶点着色完全不需要去掉3度4度的顶点；
3、就是去掉了3度4度顶点，也没有必要再在所得到的多边形面内增加边，使图成为三角剖分图。
4、作者在对3度4度顶点着色时，也并没有利用到所增加的边，所以我上面说不必要去掉3度和4度顶点，也不必要再在所得到的多边形面内增加边，使其变成三角剖分图。
5、相反，若增加了这条边，才使得这条边把这两点以外的两条链连结了起来，成了一条链，任何一个顶点的颜色也不能再变化了。若要变，两个顶点的颜色就同时都发生了变化，这个四边形面的四个顶点仍然是占用了四种颜色，根本就不可能空出颜色给去掉的顶点Z着上图中已用过的四种颜色之一了。
6、这一部分总的冠名是“Kempe 的算法”，实际上说得很难看明白，用了不少复杂的术语，结果4度顶点还没有着上图中已用过的四种颜色之一颜色（作者虽说已给这个4度顶点着上了颜色，但实际上由于在四边形面内，增边了一条边，而使这点实际上是不能着上四种颜色之一的）。
7、在对5度顶点的着色中，仍然谈到去掉5度顶点的问题，没有必要，原因如上述所说。
8、作者对5度顶点着色的看法，与我们（你张先生和我）的看法是相同的，是因为坎泊把两条连通链相交叉的一种情况漏掉了，所以在有相交叉的情况时，就产生了从两个同色顶点之一交换其对角链后，就会产生另一个同色顶点到其对角顶点的连通链，造成总不能同时移去两个同色的情况。用译文作者所译的话说，就是“对K24（v）换色将会生成从w至y的（2，3）链。”
9、我只看了这一部分，下面看了作者的“Kempe 迭代算法”一节后，再作评读。
10、请你也谈一些读后的感想，相互交流。

（二）
1、所谓“Kempe 迭代算法”实际上就是你所说的颠倒法，也就是我说的转型交换法。作者在谈论“Kempe 迭代算法”之前，没有交待清楚是在两条连通链（以下仍用我们的习惯术语用法）A—C和A—D不但有共同起始顶点，而且有交叉顶点的情况下进行迭代的，就直接谈“迭代算法”是不合适的。没有A—C和A—D的相交叉，完全是不用“迭代”就可以解决问题的。比如，他说的在的在顶点2A和4D间有连通的A—D链时，从顶点3交换B—C，构形由BAB型转化为CDC型，顶点4成了“峰点”。这时他并没有交待因从顶点3交换了B—C而产生了从顶点1到顶点4的连通的B—D链，就直接进行下一次的同方向的颠倒，也是不合适的。在从2A到3C间没有A—C链或者即就是存在A—C链，但与2A到4D间的A—D链不相交叉的情况下，再从从1B开始交换B—D链，一定是可以同时移去两个同色B的。
2、构形的结构组成是一个非常重要的因素，不顾这个，只管按某一种方法交换下去，是一定会范错误的。就象米勒对其构造的图进行了颠倒后，不顾颠倒后的图的结构发生变化，一味的按同一个方向的颠倒颠倒下去，把一个只需颠倒一次，图的结构就发生了变化、且可以得到解决的图，最后弄成了一个出现了无限循环的结果（包括你张先生也是这样认为的）。所以说，图的结构组成是非常关键的因素，在构形分类上，抛开了这一原则，必然会范错误。我们两个一直就是在这方面存在着分岐的。
3、作者说：“我们注意到，在 5 次迭代之后，峰点回到初始位置，但是颜色却根据 （1，3，2，4）的次序而重新排列（这里有错误，应是根据（3，4，2，1，4）的次序而重新排列——雷明注），其周期为 4（参见图 2），因此，如果该算法是循环的，那么将图形返回到原始染色所需的迭代次数是 4 的倍数。”最初5—轮轮沿顶点的颜色排序是“1，2，3，4，2”而5次迭代后轮沿顶点的排序则是“3，4，2，1，4”，这就是我过去说过的，虽然敢峰—米勒图经过了四次颠倒后，构形回到了BAB型，但各顶点的颜色却没有回到原始状态，且这时的“峰点”也没有到达顶点1。作者说的“图形返回到原始染色所需的迭代次数是 4 的倍数。”这就是我说的要使敢峰—米勒图中各顶点的颜色返回到原始状态，需要经过二十次颠倒的原因。
4、作者有几个术语，没有进行定义或说明，读者根本不可理解是什么含义：①“如果所有的图都在一个固定的迭代次数 （例如 4）内终止，那么可以证明运算时间有一个正式的O（n2）的上限。”这里，不知“运算时间有一个正式的O（n2）的上限”是什么意思。②“尽管我们可以将一个有n个顶点的连通平面图的不同染色的数量表达成一个简单的上限4•3n-1，我们发现对于顶点的度为 5 或更高的平面三角剖分图，不同的染色数量约为O（1.3n）。”这里，“不同的染色数量约为O（1.3n）”是如何来的也没有交待；“度为5或更高”的顶点的用语也不太合适，因为任何平面图中至少有一个顶点的度是一定是小于等于5的，把这样的顶点作为未着色的Z完全就可以了，不必要再对5度以上的顶点进行证明。
5、作者还说：“需要J次迭代的染色数量大约是需要J－1次迭代的染色数量的一半，在很多时候常常会更少（少过一半）。”这样的结论不知道是如何得来的，也不应该用“大约”二字来说明。“采用能使算法 2.1 迭代的平面三角剖分图的平面对偶图，并截断它，通常会产生更多的能使算法迭代的图。”更看不出是如何操作的。
6、这就是我看了该文后的感受，不知张先生有什么样的感觉呢。


雷  明
二○一七年十一月二十九日于西安