与张彧典先生交换对万春如翻译的《一种试探式的平面图四染色》的看法

雷明85639720

与张彧典先生交换对万春如翻译的《一种试探式的平面图四染色》的看法
雷  明
（二○一九年二月二十四日）

张先生：
1、现在我把文件全部文字复制在我的电脑上，放大字号，然后再看，这很好。但图却复制不出来。
    2、你发在网上的图可能是照像发的，不知是原图不清晰，还是你没有照清晰，很模糊，看不清，这是一点不足的地方。
3、作者对坎泊证明方法的看法以及坎泊证明存在的漏洞的看法，与我们两个的看法都是相同的。就是因为坎泊没有看到交换了一个同色顶点的链后，却会产生另一个同色顶点到其对角顶点的连通链的可能这一点。说以才被后来的赫渥特进行了否定。
4、文中段落，所用的编号不明确，常有文字中提到了编号，但从前面的文字中，却是找不到的情况。
5、定理、算法等的编号也不清，在后面的文字中看到了定理××、算法××，可再向前面找时，根本就找不到编号和内容。
6、文中提出“重新标记顶点和颜色”，没有说清是在什么情况下使用的。我认为如果象你那样，把对米勒图进行了各次颠倒后的图做为初始状态的图时，有必要做这一步工作；但如果是对一个初始状态下的图，不断的进行颠倒时，是没有必要做这一工作的。作者在这里没有把这一情况说精楚，加上图也看不清，所以对他所说的这一作就有点难以理解。
7、CK—0图就是米勒图，算法2.1就是转型交换，即你的颠倒。
8、按作者所说，使得算法2.1产生循环的图不只是CK—0图，在CK族内可能还有很多，但却在CK族之外找不到能使2.1产生循环的图。张先生你的理解是不是这样，我们交换一下。你曾在一个文章中说过你文中的图3就是一个能使颠倒无限循环的图，我也作了工作，的确这个图是一个无限次颠倒也不能空出颜色的图。这个图就是属于CK族中的一个， 是在米勒图的某一个四边形中增加了一个四色部件的图。
8、文中说了几次，颠倒的循环周期是20，所以说你的四次小循环和八次大循环是不准确的。准确的说，就是构形的类型（如BAB型或CDC型等）是四次颠倒一个循环，而构形的着色模式则是颠倒20次颠倒一个循环。因为20次颠倒后，构形的着色模式返回到了最初始时的状态，这才是一个真正的循环。
9、文中提到的米勒图的中心顶点的颜色无论在进行多少次颠倒时都没有发生变化，是因为颠倒时都没有涉及到该顶点，当然其颜色是不会改变的。
10、文章的前半部分还是可以看明白的，但后半部分不知什么原因就很难看明白，只能大概的有一个印象，大概是在图中增加各种各样的四色构件，也可能是因为图看不清楚的原因才看不明白吧。所以我建议你能不能再把图照一下，发给我来是否可以。       
       
11、补充：“因为对于任何给定的平面图，都有有限数目的染色，所以如果算法不能终止，就必须有重复的染色，之后算法就会循环。……，因此，如果该算法是循环的，那么将图形返回到原始染色所需的迭代次数是20的倍数 。”作者发现非CK0图“都可在很短的时间内由这种算法而染色。如果所有的图都在一个固定的迭代次数 (例如20) 内终止，那么可以证明运算时间有一个正式的O(n^2)的上限。”这说明了非CK0的任何图的颠倒次数一定都是有限的，即不会超过19次迭代。这就是我提出最大的颠倒次数不会超过22的原因，但我这只是考虑了从一个方向颠倒得出的结论。考虑到一个H—构形是可以从两个方向施行颠倒的，把按一个方向颠倒所得的最后一个H—构形，再按相反方向又颠倒到按另一个方向的颠倒所得的最后一个H—构形，共有39个H—构形，最多只颠倒了38次。但这个H—构形再颠倒一次后，才能得到一个可以连续的移去两个同色的K—构形；这个K—构形再交换两次便可空出两个同色的一种颜色给待着色顶点，一共就是41次颠倒或交换。但不管是22次，还是41次，或者是9次，都是有限次的，都是一个有限的数字。所以我是不主张研究所谓最大的交换次数的，因为从不同的角度出发，研究出来的结果都是不相同的，但它们只是有共同的特点——都是有限的数。

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

注：此文已于二○一九年二月二十四日在《中国博士网》上发表过，网址是：
（发在原文后的评论栏里）

附：二○一七年对万春如翻译的文章的评论：

2017年9月5日的评论：
对万春如译文《一种试探式的平面图四染色》的评论
张先生，是作者的原因，还是译者的原因，文中对坎泊方法的叙述，还没有我们（你和我）自已的叙述好理解。
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、请你也谈一些读后的感想，相互交流。

2017年9月6日的评论：
对万春如译文《一种试探式的平面图四染色》的评论（二）
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、这就是我看了该文后的感受，不知张先生有什么样的感觉呢。

2017年9月6日与张先生的交流：
张先生：
1、米勒的四次出现周期限循环是指构形类型的循不，即从BAB型反回到BAB型，并不是各顶点的颜色产生了循环，各顶点的颜色开始循环一定得要等一二十次。
2、你总强调米勒是动态的，动态提法本身就是错误的。顶点的名称是不能改变的，图一但画好后，也是不能再动的。不能在交换前是1号顶点，而交换后的同一个顶点却变成了别的序号的顶点。这就是你的图6.1中的错误。你的图6.1不光是顶点名称改变了，而且把顶点间的相邻关系也改变了，这更不应该。
3、144度是构形的“峰点”转了144度，从顶点2转到了顶点5或从顶点2转到了顶点4，这的却是144度。然而顶点2还是应该是顶点2，而不能把顶点4或5叫成了顶点2。你的图5.4到图5.8不知是你画的，还是原来米勒就是这样画的，反正进行交换后，把顶点名称改变了是不应该的。
4、为什么要把图画好后，就再不能动了，就是为了在以后的交换中不混乱，容易弄明白。所以顶点一定要用数字编号，顶点的颜色虽随着交换而改变，但顶点的序号却是不能改变的。顶点序号和颜色两个都改变了，你交换了什么呢。你的错误就是把颜色编了号，颜色是可变的，编号有什么用呢，而顶点是不可变的，编号才是有用的，但你正好就没有对顶点编号。
5、论图说的四次是最小循环，也是指构形类型的循环，并不是顶点颜色的循环。难道你到现在还看不到顶点颜色产生循环需要二十次颠倒吗。
6、你既认为图5.8等于图5,4，那么图5.8的“峰点”怎么没有转到最上面的顶点去呢。你既认为图5.8等于图5,4，那么最上面的顶点原来的着色是A，而现在着色怎么是C呢，返回初始状态了吗。
7、我认为构形的“峰点”循环一次需要四次交换，要使得图的最上面那个顶点既是构形的“峰点”又是着有最初的颜色，需要转二十个144度，即2880度。这2880度正好是360度的8倍数，即构形的“峰点”转了八圈。若把你的图5.8再进行一次颠倒，这时“峰点”可以回到最上面的那个顶点上（你介绍的这一论文中就是这样），这就已经转了720度了，是两个整圈的，但这时最上面的那个顶点仍不是原来最初时的A而是C，两个同色也不是原来的B而是D（你介绍的为一论文中也是这样说的）。
8、到现在我还是弄不明白你说的，米勒是四次小循环，你是八次大循环，有什么区别。四次循环，峰点没有回到最上面的顶点，你的八次大循环，峰点也回不到最上面的顶点呀。不都是半斤对八两吗。

注：以上的评论发在原文的评论栏内，网址是：


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

雷明85639720

，，，，，，，，