焦永溢先生着色方法的反例

雷  明

（二○二○年三月二日）

最近，我仔细研究了焦永溢先生的着色方法，感到其作为着色方法，并不是完善的。而且作为一种着色方法，也不是好的方法，更不是证明的方法。这种着色方法，在碰得巧时，可能可以使用，但在一般情况下是行不通的。在给最后一个顶点着色时，还得要用到解决不可免构形的办法进行坎泊交换，否则是不能解决某些平面图的4—着色问题的。这就是它的缺陷。下面是一个十二面体的反例。

十二面体地图和对偶图如图1和图2。

 

1、用焦永溢的方法对十二面体的对偶图的顶点着色

去顶与合并路线1：按焦先生的操作方法，去掉任一个顶点，然后再合并某些顶点，最后一定会得到一个只有三个顶点的K₃图。然后再给K₃图着色，只用三种颜色。再按原路返回。一步步的把各顶点着上四种颜色之一。

去顶与合并过程如下：

 

 

 

 

 

返回着色过程如下：

 

 

 

 

 

与顶点1相邻的顶点已占用了四种颜色，用焦先生的办法，顶点1已是无色可着了。但用解决不可免构形的办法是可以解决的。因为以顶点2为峰点的5—轮构形中，从顶点2到顶点5的红—兰链和从顶点2到顶点4的红—绿链均不连通，是一个K—构形，用坎泊的颜色交换办法就可以解决顶点1的着色问题。操作如下：

 

 

 

去顶与合并路线2：不同的人可以有不同的去顶与合并路线，但最后都可以得到只有三个顶点的K₃图。返回后各顶点着的颜色当然也就有所不同了。这里的去顶与合并路线最后一个顶点着色时，也需要用解决不可免构形的办法进行解决。其去顶与合并过程如下：

 

 

返回着色过程如下：

 

 

 

 

 

这也是一个可约的K—构形。

该构形中的待着色顶点1也可以着上紫色、兰色、绿色三种颜色之一，其着色过程如下：

 

请焦先生看一看，那里有错，请指出来。也请焦先生自已来作一次，看看能不能直接做出来。我用了两种去顶与合并路线，都得到了同样的结果，说明你的着色方法是不能适合于任何平面图的。不能用个别去代替一般。你的着色方法是不正确的。

2、焦永溢的方法对十二面体的面着色

焦先生在对中国地图着色时用了一种方法，是把地图中某一个轮进行着色后，再将其中心区域的颜色去掉，把该区域并入与其某一个或两个不相邻的轮沿区域，使之成为一个区域。然后就一直这样进行下去，最后图中也是只剩下相互邻接的、染有三种不同颜色的三个大区域，其中都包含有若干个小区域。但焦先生却没有说明在剩下这三种颜色的大区域后，是如何再返回到原图可4—面着色的。也没有用图作演示。而只是说了一句：“以上步聚中每块区域最初所着的颜色，就是这个区域应该着的颜色，也就是把操作过程中改变的颜色（如步聚1.1的括号中所说盖上去的纸）拿掉，就可得到一幅完全的四色地图。”我理解这就是说，最开始某一个区域着什么颜色，就已经是确定下来了，最后的结果仍然是什么颜色。是不是这样呢？我们仍看一下十二面体地图的面着色。十二面体面着色过程如下：

 

 

 

 

现在是三种颜色构成的三个大区域，三个大区域均互邻。可以按最开始某区域所着的颜色进行复原。如下：

因为12、9、4、5最开始时分别是着黄、兰、黄、兰色，所以把黄色大区域从12开始，按黄、兰相间着各小区域，如图12。

 

因为10、11、6、1、3最开始时是分别是着绿、红、绿、红、绿色，所以把绿色大区域从10开始，按绿、红相间着各小区域，如图13。

因为8、2、最开始时分别是着红、兰色，所以把红色大区域从8开始，按红、兰相间着各小区域，剩一区域7未着，如图14。

 

与区域7相邻的区域只用了红、黄、绿三种颜色，给区域7直接着上兰色即可，如图15。看来，的确象焦先生说的那样，各区域最开始着什么颜色，最后就是什么颜色。但这可能是正巧就碰上了这一结果，是否合并区域的路线不同时，还有需要用解决不可免构形的办法解决的情况呢？就象给十二面体的对偶图（极大图）的顶点着色那样，还有待进一步的研究。

3、用轮形图着色法对十二面体的着色

所谓“轮形图着色法”就是先选好一个顶点做为一个轮形图的中心顶点，并对这个轮形图进行4—着色。然后再对以该轮的每个轮沿顶点为中心顶点的轮进行4—着色，一直就这样进行下去。到最后剩一个顶点时，就是不可免的轮构形，用解决不可免构形的办法进行解决，就可以给最后一个顶点着上四种颜色之一，同时也就实现了给十二面体进行的可4—着色（如图3到图8）。操作如下：

顶点12和面12已无色可着，只能用坎泊的交换法进行着色了（如图9到图12）。

 

 

这里我们是对十二面体地图同时进行面着色和其对偶图进行顶点着色的。最后同样的都是遇到了需要用解决不可免构形的办法对最后一个顶点的着色的。否则，如果不这样做，这个图是无法实现可4—着色的。这说明了上面我们对十二面体地图按焦先生的办法着色时的一次成功，顺利的解决了问题，只是一种偶然的现象。所以说焦先生的着色方法是不能适用于任何地图或极大平面图的，不是一种普遍适合任何图的方法。

请焦永溢先生给以回复，要说理，不要蛮不讲理。

4、关于焦永溢先生对中国地图的着色方法

从焦先生对中国地图着色的步骤中可以看出，好象是对事先已经着好色的地图进行的。因为他说话的口气就是在已着好色的图上进行操作的。如：

“1.0.找到最小度数的北京2度，着黄色。红色的河北和绿色的天津包围它。

“3.0.找到最小度数宁夏3度，着黄色。绿色的内蒙、红色的陕西和蓝色的甘肃包围它。

“4.0找最小度数的山西4度（其实全图中还有一个更小度数3度的黑龙江落下了，但山西的外围点之间没有短路现象，也可以先来去掉这个山西），着黄色。红色的河北、陕西和绿色的内蒙、河南包围它。

“…………”

以上这种说法好象不是先着北京、宁夏、山西之后，再给河北和天津，内蒙、陕西和甘肃，河南等省区再进行着色，而听口气好象是把图已经着好了。图都着好了再讲一次，肯定还是能够4—着色的。这里应该说是：在北京、宁夏、山西分别都着了黄色之后，与北京相邻的河北和天津可分别着上红色和绿色；与宁夏相邻的内蒙、陕西和甘肃只能分别着以绿色、红色和兰色；由于河北和陕西已着了红色，内蒙已着了绿色，山西的度又是４，与山西相邻的河南着上绿色，当然是可以的，是符合用色最少和尽量多用已用过颜色的原则的。当然了，山西不着绿色，着上兰色也不是不可以。

不仅如此，着色中途还有一句是这样说的：

“11.0.找到最小度数的东面的绿色块4度，已着好绿色。蓝色的广东、北面的一块蓝和外面的黄色、红色的湖南（致所以不用与外面一样的黄色，是因为若用黄色会使重庆外围的颜色多达四种）所包围。”

这个时候，时湖南还没有着色，怎么就用了“红色的湖南”的说法呢？特别是括号中的话，湖南“只所以不用与外面一样的黄色，是因为若用黄色会使重庆外围的颜色多达四种”（说明一点，焦先生这里的“外面”二字说的是中国国境线和海岸线以外的区域，包括所有的陆地邻国和海洋）。湖南还没有着色呢，怎么能知道“重庆外围的颜色多达四种”呢？这分明是已经把图着好了嘛！

其实，即就是给湖南着了黄色，重庆外围的颜色达到四种时，完全也可以通过解决不可免构形的方法进行解决。这时分明是焦先生已经自觉或不自觉的使用了坎泊解决不可免构形着色时的颜色交换法，只是没有表现出来而已。故而给湖南不着黄色而着红色的。这就把一个需要用特殊的颜色交换方法来解决的不可免构形问题隐藏了起来。

一般在着色时，着到了那个区域时，该区域的颜色只要与已着过色的其他区域不“冲突”（或者叫不“撞色”）时，就可以在四种颜色之内随便的使用，是不会提前去考虑到下一步别的区域的外围用色多少的问题。只有在遇到了某个需要着色的待着色顶点的外围已用完了四种颜色时，才想办法要把四种减少到三种，这就是解决不可免构形的着色的办法。

焦先生可能是提前对图已着了色，知道若给湖南着黄色后，就会遇重庆外围出现四种颜色的情况。但他却没有说他是如何解决这一问题的，所以我只能说他是自觉或不自觉的使用了坎泊解决不可免构形着色时的颜色交换法。至于为什么把湖南的黄色改着成红色后，重庆外围的颜色数就会由四种减少到三种，他却是不清楚的，而他只知道的是这样做了以后，重庆外围的颜色数可以由四种减少到三种。而要解决这一问题，就要看构形围栏顶点间的对角链是否连通的问题了。这就是坎泊的颜色交换技术。

那么，焦先生在对中国地图的着色过程中是否遇到了不可免的构形呢？遇到了。这就是最后一个省——云南。其外围的五个区域，西藏和贵州用了兰色，四川和广西用了绿色，国境线以外是黄色，共三种。正好还有红色可直接给云南着上。这是一个直接可约（直接可着色）的不可免构形。还有在对新疆（或西藏）和辽宁着色时，也都是外围4个省区只用了三种颜色，所以各都还有一种颜色可着，都是可直接着色的不可免构形。现在还有一个可直接着色的不可免构形——上海市，焦先生却还没有给其着上应着上的红色。

再说，焦先生的着色办法并不是好的办法，而是很复杂，速度也很慢。不如用我们前面讲到的轮形图着色法。该法在着色过程中只要是遇到了不可免的构形时，就用相应的解决办法解决就是了。值到把最后一个顶点着上图中已用过的四种颜色之一为止。

另外，我只能说焦先生的方法只能是一种着色的方法，决不是证明四色猜测的方法。因为他在这里仅遇到的一次不可免构形的处理，并不是主动的，而是自觉或不自觉的，而且其他的不可免的构形他还没有遇到，在对别的图着色时，若遇到这样的不可免构形，他也是照样不会处理的。处理不了不可免构形的可约性问题，就等于不能证明四色猜测。

可以证明，不可免的构形一定是有限的。由这些构形共同构成了一个集合，叫做平面图的不可避免构形集，简称不可免集。证明四色猜测时，首先要证明不可免集是完备的，即除了这些不可免构形外，再没有别的构形是不可避免的了。这就把一个对平面图来说，实际上是无穷多个的平面图；对任一个平面图来说，顶点个数也可以是无穷多的；对某一个具体的平面图来说，各顶点的度也可以是无穷大的这三个无穷的问题，转化成一个有穷的问题了。只要证明了这些有限的不可免构形都是“可约”的，即是可4—着色的，也就证明了四色猜测是正确的。

证明四色猜测时，首先要证明不可免集是完备的。然后再人为的构造一些不可免集中的不可免构形的模型，解决了这些模型的可约性问题，就解决了四色猜测的证明问题。这就是对四色猜测的证明。然后在着色过程中，若遇到了具有符合以上这些不可免构形模型的特点的顶点时，就按解决这种模型的方法去处理，一定是可以解决问题的。这就是着色。这才是最好的着色方法。按照这样的着色方法去进行着色，可以说就是在着色的过程中动态的证明四色猜测。但对个别图的着色，特别是你对个别图进行的着色，却不能说明四色猜出测就是正确的。因为对个别图的着色，不可能把所有的不可免构形都遇到，何况你现在根本就没有一个不可免集的概念。

着色解决的是“是什么”的问题，而证明则解决的是“为什么”的问题，二都是不同的，是有区别的。

雷  明

二○二○年三月二日于长安

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

http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=4142