坎泊链及其应用

雷明85639720

坎泊链及其应用
雷  明
(二○二○年九月二十四日)
（图发不上来，请到＜中国博士网＞中去看）

1、链：在《图论的例和反例》一书中，链是这样定义的：“一条从V1到Vn的其点交错的着有颜色A和B的道路称为一条从V1到V2的A—B链。”链也叫做色链。如图1。
2、相反链：由A、B、C、D四种颜色所构成的A—B链和C—D链就叫一对相反链。相反链即两条链中的四种颜色都是不相同的两条色链。当然，A—C链与B—D链也是一对相反链。
3、相反链的互不穿透性：即两链是不能相互穿过的。若A—B链构成了一个环时，则其内、外的C—D链就不可能再相互连通了（如图2）。
4、链的交换：若A—B链与一个没有着色的顶点共同构成了一个环时，则其内、外的C—D链也一定是互不连通的（如图3）。这时如果要改变与未着色顶点相邻的C点或D点的颜色，就可以从C点或D点开始交换C—D链中的顶点的颜色（如图4），从而达到改变C点或D点颜色的目的。
5、坎泊链和坎泊链法：色链是1879年坎泊首先提出并使用的，所以做坎泊链。坎泊在证明四色猜测中就是用了色链的交换，所以也叫坎泊链法。坎泊认为：“如果一个顶点V与五个其他用四种颜色着色的点邻接，那么总能够多出诸颜色之一用来给V着色。他用了邻接点交错着色的道路，交换这些道路上的颜色便于空出一种颜色给V。”（摘自《图论的例和反例》一书）。从坎泊的证明中可以看出，这种交换都是交换了围栏顶点的对角顶点的颜色构成的对角链的。
6、坎泊的证明并不彻底：坎泊就是用了这种坎泊链法证明了无双环交叉链的并有颜色冲突的构形都是可4—着色的。可惜他却遗漏了有双环交叉链的这种构形（如图5），使得他的证明不彻底。

7、空出颜色的交换：坎泊证明中不但用的都是对角链的交换，而且每次交换也都能空出一种颜色来，所以把坎泊所用的链的交换方法又叫做空出颜色的交换法。
8、断链交换：既然交换色链中各顶点的颜色可以达到改变链中任何一个顶点的颜色的目的，那么也可以在不需空出颜色的情况下进行应用。比如在有经过构形围栏顶点的环形链的情况下，交换环内、外的任一条相反链，虽不能空出任何颜色给V，但可以使双环交叉链断开，使构形变成无双环交叉链的构形。所以这种交换也可叫做断链交换。无双环交叉链的构形则是坎泊早已证明了是可约（即可4—着色）的构形。这就解决了一部分（有环形链的）有双环交叉链的构形的可约性的问题。这种交换如果交换的是环形链内的相反链时，这条相反链一定是至少经过了两个或三个相邻的围栏顶点的链，所以也可叫做邻角链交换。
9、连续转型交换法：当使用坎泊链法无法通过一次或两次交换从有双环交叉链的、但又无经过围栏顶点的环形链的构形中空出颜色来时，就得使用同方向的连续的转型交换法。所谓转型交换，即是从一个两个同色的顶点开始，交换了一条关于两个同色的对角链时，构形峰点的颜色和位置都会发生变化，这就叫转型，相应的交换也就叫做转型交换。所谓同方向的连续转型，就是每转型一次后，还不能空出颜色的情况下，就按相同的方向（逆时针或顺时针）再继续转型。直到构形转化成可以连续的移去两个同色的可约构形为止。
10、连续转型交换的次数是有限的：可以证明，这种无环形链的含有双环交叉链的构形最多在二十次转型之内一定是可以转化成可以连续的移去两个同色的可约构形的。证明略。
11、四色猜测是正确的：现在已经证明了有双环交叉链的构形在有环形链和无环形链的两种情况下的构形都是可约的，加上原来坎泊已经证明了的无双环交叉链的构形都是可约的，所有平面图的不可避免的构形就都是可约的了，四色猜测也就证明是正确的了。
雷  明
二○二○年九月二十四日于长安

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，

雷明85639720

．．．．．．．．

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，