[原创]我对坎泊证明方法的理解

雷明85639720

[watermark]

我对坎泊证明方法的理解
雷  明
（二○一二年十一月六日）
1、图和图的着色：
图是由顶点和在某些顶点间的连线（边）所构成的集合。由某些边所围成的一个连续的区域叫做图的面。图的着色是给图的各个顶点着以不同的颜色，使有边相连（相邻）的顶点具有不同的颜色。
2、什么是坎泊链：
所谓坎泊链，实际上就是图中的一条道路（道路是由若干条边首尾依次连接起来而开成的）。不过这条道路是经过了着色的，且是用了两种颜色交替进行着色的道路。这种道路由于是坎泊在证明四色猜测的过程中首先使用的，所以大家喜欢叫它为坎泊链（简称链）。坎泊链的特征是：首先是一条道路，且已给道路中的顶点着了色；二是只用了两种颜色，且两种颜色是交替着色的。坎泊链中的顶点数可以有多有少，链可以有长有短，有奇数链，有偶数链，一个单独的顶点也是一条坎泊链，只要它是着了色的顶点。一个顶点的坎泊链的另一种颜色就是与该顶点所相邻的顶点中没有用到的颜色。如顶点A已着红色，而与顶点A相邻的顶点中没有用到黄色，则顶点A就是一条由红—黄二色构成的坎泊链中的一个已着了红色的顶点。
3、坎泊所创造的颜色交换技术：
在一条坎泊链中，把各顶点所用的颜色交换一次，即在一条由A—B二色构成的坎泊链中，把原来着A色的顶点改着B色，把原来着B色的顶点改着A色，就可以达到改变该链中任何一个顶点的颜色的目的。这就是坎泊创造的颜色交换技术。
4、坎泊的颜色交换技术的主要作用：
在对图的着色过程中，如果遇到一个顶点V，其周围的所有顶点都已着上了颜色，但还希望该顶点能着上其周围已用过的颜色之一时，就得想办法把该顶点周围顶点中的某一种颜色去掉，空出该种颜色给V着上。这一空出颜色的过程就要使用到坎泊的颜色交换技术。所以说，使用坎泊的颜色交换技术的目的不光是为了改变某条坎泊链中某一顶点的颜色，更重要的是把改变了的某一顶点原来所着的颜色空了出来，而给要着色的顶点V着上。这才是使用坎泊交换技术的真正目的。
5、交换什么样的坎泊链才能达到空出颜色的目的：
如果要改变与待着色顶点V相邻的某一顶点的改色，并把该顶点的颜色空出来给V着上，交换的链是要满足一定的条件的。这一条件就是要交换的链一定要与待着色顶点V不能构成回路（即圈）。这就是我们平常所说的该链一定是不连通的。所谓不连通是指该链的两个端点不能同时都与V相邻。如果这一条件不能满足，即就是进行了交换，使链的两个端点顶点都改变了颜色，但因其都是与V相邻的顶点，所以仍是空出不颜色给V的。这一点必须弄明白，随便的交换是不能达到目的的。
6、坎泊对四色猜测证明的方法：
首先，坎泊证明了任何地图中都不可避免的至少存在着一个国家与两个国家相邻，一个国家与三个国家相邻，一个国家与四个国家相邻和一个国家与五个国家相邻的这四种情况中的一种情况。也即任何一个平面图中一定存在着顶点度小于等于5的顶点，这就是平面图的不可避免构形，即2—轮构形，3—轮构形，4—轮构形和5—轮构形。这就给我们在证明猜测时，把一个无穷的问题变成有穷的问题创造了条件。所以我个人认为坎泊在以下的证明中是用的数学归纳法，一种情况一种情况的进行排除，等到把以上四种情况下的待着色顶点，都排除了用第五种颜色的可能时，也即不存在所谓的最小的五色地图时，四色猜测也就得到了证明是正确的。
坎泊所用的归纳—排除法具体操作步骤如下：
㈠ 当图中的顶点数小于等于4是，显然4 种颜色一定是够用的。
㈡ 当图中的顶点数大于4时，除了待着色顶点V外，图中其它顶点均已着上了四种颜色之一：
这种情况下，一种情况是，与V相邻的顶点没有占用完四种颜色，当然V着上四种颜色之一一定是可以的，四种颜色也就够用了；
另一种情况是，与V相邻的顶点已占用完了四种颜色：这种情况下有V与四个顶点相邻（即4—轮构形）的情况，还有V与五个顶点相邻（即5—轮构形）的情况。
A、在V与四个顶点相邻时，坎泊用他所创造的颜色交换技术已给V着上了已用过的四种颜色之一；
B、在V与五个顶点相邻时，坎泊用他所创造的颜色交换技术已给不存在连通链的情况和有一条连通链的情况，以及虽有两条连通链但两链并不相交的情况中的V着上了已用过的四种颜色之一；这时他就根据以上各种情况下V能着上已用过四种颜色之一，就也认为5—轮构形也是可约的，即是4—可着色的。这就给赫渥特留下了空子可钻，否定了坎泊的证明。可以说坎泊是没有最后证明5—轮构形也是可约的，即没有证明5—轮构形也是能够4—可着色的。
7、赫渥特图是4—可着色的：
赫渥特构造的图是一个极大图，除了一个处于一个5—轮的中心的顶点未着色外，其余的顶点均已着上了四种颜色之一，符合着色要求。这个图的最大特点就是图中有两条连通链，而且是相交的。赫渥特认为这个处于5—轮中心的待着色顶点是无法着上已用过的四种颜色之一的。
上面说了，坎泊的颜色交换技术主要的作用是为了从与V相邻的顶点中空出一种颜色给V，但不要忘了，只要交换某条链时，该链的所有顶点的颜色都是会变化的。对于赫渥特图我们可以利用这一点，使两条交叉链变得即不相交又不连通，为下一步的坎泊交换，空出颜色创造条件。
赫渥特图中用了b、r、g、y四种颜色，有b—g和b—y链是连通的且是相交的，交换r—g或（和）r—y都不能空出颜色给V。但我们可以从两交就链b—g和b—y的交叉顶点（肯定是着b色）开始进行b—r链的交换，使b—g和b—y两链变得均不连通，也不交叉。这时图中就不存在连通链了，再任交换一条链都可以空出颜色给V的。
8、赫渥特交换的是连通链，当然就空不出颜色来：
赫渥特当年对他的图是这样处理的：首先从5—轮中的顶点1开始交换b—g链，使顶点1变成了g色，由于5—轮中还有一个着r色的顶点3,所以他再继续从顶点3开始交b—y链时，但不能移去r。所以他就认为，虽然能移去一个r，但却不能同时移去两个r，只有给V着上第五种颜色。实际上在他从顶点1开始交换了b—g链后，原来的b—y链已由原来的不连通变成了连通的链了。上面已经说过了，交换连通链是不能空出颜色来的，所以说在这一点上，赫渥特是没有正确的使用坎泊的颜色交换技术的。
9、坎泊当年也没有认识到交换坎泊链空出颜色给待着色顶点时的条件必须是交换非连通链：
由于坎泊还没有认识到交换坎泊链空出颜色给待着色顶点时的条件必须是交换非连通链，所以他也就一时不能对赫渥特的图中的待着色顶点V着上已用过的四种颜色之一。也就只好承认他自已“弄错了”，并在英国皇家数学会上介绍了赫渥特的结果。当时如果坎泊明白这一点，也就不会有赫渥特否定坎泊的事情发生了。这是一个历史的悲剧。
10、5—轮构形是4—可着色的：
我们现在对赫渥特图的4可—着色，只能说是对坎泊证明中的漏洞的一个补充，但对这样一个具体的图的4—着色还不能说说明了5—构形就是可4—着色的，更不能说明四色猜测就是正确的。赫渥特图可以简化成一个只剩下该图中重要顶点的“九点形”图，该图具有赫渥特图的一切性质，用给赫渥特图着色时的交换方法可以给其中的待着色顶点V着上已用过的四种颜色之一，说明了任何5—轮构形都是4—可着色的。
11、四色猜测是正确的：
使用坎泊所创造的颜色交换技术，可以证明平面图各种情况的不可避免构形都是可4—着色的。在对任意的平面图着色时，可以把不可避免的构形放到最后来着色（这种构形是一定可以从图中找到的），也一定能着上图中已用过的四种颜色之一的。这就证明了平面图的四色猜测是正确的。由于地图也是平面图，其对偶图也是平面图，对地图的面上的着色也就相当于对其对偶图的顶点着色，由于平面图是4—可着色的，所以任何地图也是4—可着色的。这也就证明了地图四色猜测是正确的。
12、坎泊的颜色交换技术与约当曲线是没有联系的：
坎泊在使用颜色交换技术的过程中说，如果有一条A—B链与V构成了一个圈，即A—B链是连通的，尽管该链是不能进行交换的，但一定有C—D链是被A—B链分隔成两部分于该圈的内外的，即C—D链一定是不连通的，可以交换C—D链空出产色给V。这里并没有涉及到约当曲线的问题，而是只要有不连通的链，就可对其进行交换而空出颜色给V的。
可现在有些人说，赫渥特在对他的图着色时是违背了约当曲线定理的。不知道他们是怎么把这一问题与约当曲线能联系在一起的。约当曲线是一条封闭的曲线（圈或环）。而约当曲线定理是说从约当曲线某一侧要到达约当曲线的另一侧时，必须要经过该曲线上的点。而赫渥特交换的正好是在C—D链与V构成的约当曲线上进行的，没有涉及该曲线以外的任何顶点，怎么能说是违背了约当曲线定理呢。
13、结论：
坎泊的颜色交换技术是正确的，坎泊对猜测的证明方法也是正确的。赫渥特没有正确的使用颜色交换技术，所以他不能给他的图进行4—着色。他对坎泊的否定是错误的，所谓的弱一点的“五色定理”更是错误的。

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