坎泊颜色交换的实质

雷明85639720

坎泊颜色交换的实质
雷  明
（二○一六年元月六日）

在着色或者是对四色猜测的证明中，经常要用到坎泊的颜色交换技术。现在多们就重新把这一技术剖折一下。
在已着了颜色的图中，把用两种颜色交替着色的一条道路，就叫做一条色链，简称链。把某条色链中各顶点的颜色相互交换，以达到改变链中某一顶点颜色的目的，这就是坎泊的颜色交换技术。
用四种颜色着色时，任两种颜色都可组成一条色链，共可以组成6种情况的色链。由某条色链的两种颜色以外的另外两种颜色组成的色链，就是该色链的相反色链，简称相反链。
如果一条链是一个圈，那么这个圈就把该色链的相反链分隔成了圈内圈外互不连通的两部分。交换该色链中任一部分顶点上的颜色，不但不会影响到相反链中各顶点的颜色，而且也不会影响到另一部分相同色链各顶点的颜色。
根据色链的这些特性，在给图着色时就可以利用。当我们需要对某个顶点的颜色进行变动时，就可以应用坎泊的这一颜色交换技术。比如说，当图中只有一个顶点未着上颜色，而图中其他的顶点都已着上了四种颜色之一（符合四色猜测的要求，即没有相邻顶点用了相同的颜色），且与未着色顶点相邻的顶点已占用完了四种颜色的情况下，要想给这个未着色顶点着上图中已用过的四种颜色之一，就得使用坎泊的颜色交换技术。
颜色交换技术使用的条件：如果某链与其相反链均在图中都只有一条时，是不能交换的。因为交换后只相当于把图中所有着某两种颜色的顶点的都颜色进行了交换，从整个图的着色布局上看是并没有发生变化的，而只是颜色类别发生了变化。
可以使用产色交换技术的各种情况：
一般情况下，是在与待着色顶点相邻的顶点已占用完了四种颜色的情况下，才使用颜色交换技术的。交换的目的是要从待着色顶点的邻接顶点中空出一种颜色来给待着色顶点着上。
待着色顶点一般是处在一个轮的中心位置的，若要移去其轮沿顶点中的某一颜色，就要看从着该颜色的顶点出发的某色链能否到达该轮的另一个对角顶点。若不能到达，该链对于这个轮来说，肯定是不连通链。直接从该顶点进行交换就可以空出一种颜色给待着色顶点了。若能够到达，我们称为连通链。这样的链是不能交换的，因为交换后并不能空出颜色给待着色顶点。但这种链与待着色顶点构成了一个圈，把其相反链分隔成圈内圈外互不连通的两部分。这种情况下，该圈（色链）的相反链肯定就是不连通的。那么就可对这一相反链进行交换，空出一种颜色给待着色顶点。
有时交换的目的并不是为了直接空出颜色给待着色顶点，而是为了给下一步交换能空出颜色创造条件。比如，交换的目的是为了把某一条或两条连通链“断开”，变成不连通链，然后再通过颜色交换空出颜色给待着色顶点。
还有交换的目的既不是为了直接空出颜色给待着色顶点，也不是为了“断链”，而是为了“转型”。即把以待着色顶点为中心的轮的轮沿顶点中用了两次的颜色变成另一种。这也是为了能给待着色顶点空出颜色创造条件。因为的确有些图，若不这样做，就不可能给待着色顶点空出颜色来。

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

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