谈谈“着色”与“证明”的关系

雷明85639720

谈谈“着色”与“证明”的关系
——兼论四色猜测的证明
雷  明
（二○一五年七月十五日）

四色问题说的是对任意的平面图顶点着色，使相邻的顶点不着同一颜色时的色数都不会大于4。但这还只是一个猜想，还没有得到理论上的严格证明，所以还不能作为定理直接地进行应用。
四色问题最开始是与地图中对区域的染色有关的，即对任意地图的区域的进行染色，使有共同边界的区域有不同的颜色时的色数都不会大于4。
由于地图是一个3—正则的平面图，其对偶图是一个极大平面图，所以给地图的区域（面）上的染色，就相当于给其对偶图的顶点着色。就这样一个地理学上的、对地图区域上的染色问题就自然的转变成了一个数学中的、对图的顶点着色的问题。
1、着色只是图论中的一种运算方法
在研究四色问题时，我认为一定要弄清“着色”与“证明”的关系。光着色并不等于证明，而证明不能只用着色的方法。
四色问题无论是从地理学上讲，还是从数学上讲，都是与图和着（染）色有关的，因此这一问题（猜想）的提出，也就自然而然的只可能来源于从事绘图的工作者——英国的绘图员法朗西斯。因为他们的工作整天就是接触大量的图，并给其着（染）色。法朗西斯能提出这一问题，一定是进行了大量的观察和实践的结果。他所绘的图和染过色的图的数量达没有达到2000个，我们也无从知道，但知道能得到这样一个结论至少不是从少量的几个个别的图中得来的。
后来坎泊也对大量的图进行了研究，从中又总结出了给平面图4—着色的方法——颜色交换技术。坎泊认为通过他的颜色交换技术，可以使任意的平面图实现4—着色。坎泊所用过的图达没有达到2000个，我们也不可能知道，但他的颜色交换技术的产生，也绝对不是从一两个个别的图的着色中得到的。
用坎泊的颜色交换技术，对4—轮以下的构形的4—着色都能很顺利的进行解决，成为可给的构形，即可以进行4—着色；而由于后来赫渥特构造了赫渥特图，加上在当时谁也不能对该图进行4—着色（也包括坎泊自已在内），从而使5—轮构形成了不可约构形。因此赫渥特就用他的图对坎泊的“证明”就进行了否定。
后来有人想了一个办法，企图使用别的构形来替代5—轮构形，比如用所谓的双5—轮构形代替5—轮构形。但其不知该构形中的两个待着色顶点总得是一个一个的进行着色，当给其中之一着上颜色后，对于另一个待着色顶点来说，这不仍然还是一个5—轮构形吗，仍然是不可约的呀。我们从现在的观点上看，用坎泊的颜色交换技术，是完全可以对5—轮构形进行4—着色的，我们对赫渥特图和米勒图的4—着色就是用的坎泊的颜色交换技术。
以上的这些工作，与其说是对四色猜测在进行证明，还不如说是在寻找平面图的着色方法。既然是着色方法，总有不完善的地方，但这并不是坎泊的颜色交换技术不完善，而是坎泊对他的技术还没有运用得很自如，所以他对赫渥特的图就没有能够4—着色。而实际上我们目前对赫渥特的图的4—着色仍然是运用的坎泊的颜色交换技术。
电子计算机的出现，由于它的计算速度非常用之快，所以就有人想借用电子计算机来代替人来对图进行着色。1976年的阿贝尔就是其中之一。为什么我这里说阿贝尔是用电子计算机对平面图进行4—着色而不说其是对四色猜测的证明呢，因为“着色”与“证明”完全是不同的两回事。着色如同数学中的加减乘除运算一样，通过对图进行着色运算求得某个具体图的色数是多少，但不能得到某一类图（如平面图）的色数的上界是多少（如平面图的上界是4），因为就从某一类图来讲，也是有无穷多个的，不可能把所有的该类图都着色完，当然也就不可能得到这一类图的色数的上界了。计算机所作的工作，实质上与法朗西斯和坎泊所作的工作相同，都是对大量的平面图进行了4—着色，都说明了平面图的色数都不大于4。同样的，四色猜测仍是一个猜想，还没有得到证明是正确还是不正确。因为仍有大量的平面图并没有进行着色，谁也不知道他们中间有没有色数是大于4的图呢。
电子计算机为什么能够对图进行着色，是因为我们的人是能够对图进行着色的，人们可以把画图的方法，并把对图顶点着色的过程编成程序让计算机去代替人进行工作。但计算机再快也只能是对人所给他的、部分的、个别图进行了着色，它只着了两千个图，而不是把所有的图都进行了着色。所以说计算机所进行的工作实质上和人用手工进行的对某些图进行的4—着色是一样的，仍只是对个别图的着色，尽管氧上过的图的色数都不大于4，但并不是对四色猜测的证明，也不能得出四色猜测是否正确的结论。为什么说它不是对猜测的证明呢，因为人还不会去进行证明，还不可能把证明的过程编制成程序叫计算机去执行。计算机完全是在人的指示下去工作的，人还不会做的事，计算机也一定不会做。不要以为计算机就是个万能的东西，它还必须要有人的指挥才能去工作，它是离不了人的。
阿贝尔用计算机对2000个平面图的着色虽然也是采用了坎泊的颜色交换技术，但他仍然把5—轮构形排除在外，用了双5—轮替代了5—轮构形。先不说它着过的图是不是无限多，就单从没有5—轮构形这一点上看，他就至少缺少了平面图的一个最基本的不可免构形，5—轮构形仍然没有从不可约构形中排除掉，仍是不可约的。现在我不仅要问，平面图的一个最基本的不可免构形仍是不可约的，都不能进行4—着色，那么何谈四色猜测被电子计算机证明了是正确的呢。而且我还要说，计算机的工作只说明了它所着过的2000个个别的图的色数都没有大于4，但还不能说明任何平面图的色数都不大于4，也还不能说四色猜测就是正确的。因为这2000个图只是无限的图中的极少的一部分，而四色猜测说的则是任意的平面图的色数都是不大于4的。
2、证明是普适的一种逻辑上的推理过程
什么是“证明”，它是一种运用逻辑推理的办法而使问题得到解决的过程。它不用去对任何一个具体的图去进行具体的着色，当然也用不着画具体的图了。
任何图都有一个最小的完全同态，这个完全同态的顶点数就是图的色数。最小完全同态中的每一个顶点都是由原图中互不相邻的若干个顶点同化而来的（“同化”即不相邻的顶点凝结到一起的过程），即完全同态的每一个顶点都代表着原图中互不相邻的若干个顶点，代表着原图的一个顶独立集。同一个顶独立集内的顶点或者说这互不相邻的若干个顶点着同一颜色完全是符合着色要求的，而最小完全同态即是完全图，当然着色时有几个顶点，就必须用几种颜色。所以说任何一个图的顶点着色色数一定等于其最小完全同态的顶点数，也等于其最小顶独立集数。
现在看，只要求出了图的最小完全同态，就能知道其顶点数，当然也就知道了该图的色数了。任何图都有其亏格，其亏格就是其可嵌入的曲面的最小亏格。一个图可嵌入某个曲面，即是把该图画到这个曲面上后，除了在图的顶点处存在边与边相交叉的情况外，在别的地方再没有边与边的相互交叉。一般情况下我们所说的一个图能嵌入到某个亏格的曲面上，就是指其所能嵌入的最小亏格的曲面，当然该图的亏格也就与该曲面的亏格相同了。
图的最小完全同态也是一个图，是图就必有其亏格。可以证明图的最小完全同态的亏格是小于等于原图的亏格的。
图的亏格是其可嵌入的曲面的最小亏格，那么亏格是n的图一定是可嵌入在亏格为n的曲面上的图。图的同化是在亏格为n的曲面上进行的，最后得到的最小完全同态也一定是嵌入在亏格是n的曲面上的图。比如K5图的亏格是1，其最小完全同态就是原图K5本身，其亏格也应是1；而K3,3图的亏格也是1，但其最小完全同态却是K2，虽然这个K2现在仍是嵌入在亏格为1的曲面上，但K2本身的亏格却是0（K2不但能嵌入亏格为1的曲面，也能嵌入亏格为0的曲面，小者是0，所以K2的亏格是0）。从这里可以看出，图的最小完全同态的亏格是小于等于原图的亏格的；但有没有图的最小完全同态的亏格是大于原图的亏格的情况呢。可以证明是没有的。
设一个任意的图是嵌入在亏格为n的曲面上的亏格为n的图，假设其最小完全同态的亏格是n＋1，大于原图的亏格。那么该完全同态就只可能嵌入到亏格为n＋1的曲面上。当我们把这个最小完全同态按同化时的相反方向返回到原图时，原图就是一个嵌入在亏格为n＋1的曲面上的亏格为n＋1的图，这与原题设的图是一个嵌入在亏格为n的曲面上的亏格为n的图出现了矛盾，所以必须否定原来假设的该图的最小完全同态的亏格是n＋1的假设，而得到图的最小完全同态的亏格是不可能大于原图的的亏格的结论。
3、四色猜测的证明
根据以上的结论，任何图的最小完全同态的亏格一定小于等于原图的亏格的结论，也就有任何亏格为0的平面图的最小完全同态的亏格也一定仍然是等于0的，也即任何平面图的最小完全同态一定都是平面图。要证明四色猜测，就相当于证明平面图中的完全图着色时，色数不大于4 也就可以了。
平面图的亏格是0，可嵌入亏格为0的曲面上的完全图有K4，K3，K2和K1，他们的顶点数都小于等于4。因为有任何图的色数都等于其最小完全同态的顶点数，所以也就有任何平面图的色数都小于等于4的结论。这就证明了四色猜测是正确的，整个证明过程中我们没有画任何一个具体的图，也没有对任何一个具体的图进行着色。
另外，四色猜测还可以这样来证明。设平面图的最小完全同态的顶点数是v，把完全图的边与顶点的关系e＝v（v－1）/2代入平面图的边的上界公式e≤3v－6中得
v（v－1）/2≤3v－6
v2－v≤6v－12
v2－7v＋12≤0
解这个一元二次不等式得
        v1≤4和v2≤3
因为v2≤3已包含在v1≤4中，实际这里只一个根v1≤4。这就说明了任何平面图的最小完全同态的顶点数都是小于等于4的。由于任何图的色数都等于其最小完全同态的顶点数，所以也有任何平面图的色数都是不大于4确的结论。这就是四色猜测，这就证明了猜测是正确的。这个证明过程中也没有画任何图和给任何图着色。
再举一个证明四色猜测的例子。
设一个亏格为n的图同化后所得到的最小完全同态是Kv，该同态是一个顶点数是v的完全图。该Kv一定是能够满足多阶曲面上图的欧拉公式v＋f－e＝2（1－n）的。因为任意图中都有3f≤2e的关系，把f≤2e/3带入以上的欧拉公式中得
     3v－e≥6－6n
把该公式变形得
       e≤3v＋6n－6
这就是多阶曲面上图的边的上界公式。再把完全图中边与顶点的关系e＝v（v－1）/2代入上式得
        v2－7v＋12（1－n）≤0
解这个关于完全图（即亏格为n的图的最小完全同态）的顶点数v的一元二次不等式，得正根是
v≤（7＋√（1＋48n））/2
由于顶点数必须是整数，所以上式还得向下取整，得
v≤＜（7＋√（1＋48n））/2＞
式中用＜ ＞表示其中的数字向下取整。因为完全图的色数就等于其顶点数，所以又有
γ≤＜（7＋√（1＋48n））/2＞
这就是赫渥特的地图着色公式。当n＝0时，上式的计算结果是γ≤4，这也就是四色猜测。四色猜测得证是正确的。这里也没有画图和着色。
    当然不画图，不着色证明四色猜测的方法还有很多，而绝非只有这么三种，我们已经得到了十多种方法，都不画图，也不着色。

雷  明
              二○一五年七月十八日于长安

注：此文已于二○一五年七月十八日发表在《中国博士网》上，网址是：

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,..

雷明85639720

，，，，，，，，