给leisurely发一点有关着色的方法

雷明85639720

给leisurely发一点有关着色的方法
雷  明
（二○一七年元月六日节选）

Leisurely朋友：
以下是我所写《四色问题与欧拉公式》一书（未发表）中的节选：
6、破圈着色法
如果给某图着色只剩了最后一个顶点（或者在着色中途也可能产生这样的顶点）V未着色，但其周围的顶点已用完了已用过的四种颜色，且与V邻接的顶点数大于等于5，这种情况下，虽然使用坎泊的颜色交换技术是可以空出颜色给V的，但对于一个具体的、顶点数比较多的图来说，不象前面第36节《用坎泊创造的颜色交换技术对猜测进行证明》一节中的图4—1中的m，n，o三图那样，直接就可以看出是属于那一种，这样的具体的图要确定是属于那一种则是比较难的。不能确定属于那一种类，也就无法有针对性的按不同的方法去使用颜色交换技术了。在这种情况下，首先我们一定要坚信该顶点是一定能着上已用过的四种颜色之一的。但确定不了是属于那一种类也不要紧，但可以用一种叫做“破圈着色法”的方法将其着上已用过的四种颜色之一。

图4—46是一个用破圈着色法对其中的待着色顶点V进行着色的路线图（图中顶点上的短线说明该顶点上还连着别的顶点），箭头方向是破圈时顶点颜色移动的方向，如图4—46，a中，箭头表示从左边的6—轮中的着g色的轮沿顶点破圈（因为以V 为轮心的6—轮的轮沿顶点中g色只用了一次，是这个6—轮中使用最少的颜色。破圈的意思是指把该6—轮上的已着了四种颜色的6—圈（色圈）破坏，使其成了一个不完善的色圈），把箭尾顶点的g色给待着色顶点V着上，得到图4—46，b，这时原来6—轮中的着g色的轮沿顶点就变成了新的待着色顶点。就这样，沿着某条路线一直破下去，直到新得到的新的待着色顶点的度小于或等于5时，再使用坎泊的颜色交换法，或者就一直破下去直到新待着色顶点的度小于4或者当待着色顶点V周围只用了不大于4种的颜色时，如图4—46，f那样，直接给V着上四种颜色之一就行了，不需要再使用颜色交换技术。
破圈法主要的依据就是平面图中至少总存在着一个顶点的度是小于等于5的这一特点的。说穿了，它的过程实质上还是坎泊的颜色交换法，只不过是交换颜色的链很短，破一次圈只有一个顶点进行了颜色交换。
Heawood—图也可以不用我们在前面第42节《赫渥特图的4—着色》一节中的着色方法，就直接使用我们这里所说的破圈的方法，也是可以给其4—着色的。这里就不再画图了，读者可以自已去画图，用破圈法试着一下。
我们在这里用了“破圈法”一词，但实质上是对“待着色顶点”进行着“变动”。另一方面，如果说与待着色顶点邻接的顶点构成的分子图不是轮呢，那不是就不存在轮沿顶点构成的圈了吗，这时该破什么呢。所以说把这一着色方法叫做“破圈法”还不如叫做“变动待着色顶点位置法”较为合适与科学。
7、用“断链”的思想证明四色猜测
对于平面图的不可免构形集中的每一个构形来说，只要其围栏顶点（即轮沿顶点）所占用颜色总数未达到4，该构形中的待着色顶点也总是可以着上图中已用过的四种颜色之一的，即该构形也一定是可约的。但当构形的围栏顶点所占用的颜色总数已达到了4时，就得想办法从其中减少一种，空出其给待着色顶点着上。减少围栏顶点所占用颜色总数的办法，也只能是用坎泊所创造的颜色交换技术。
如果由构形的某两个对角顶点所着的两种颜色构成的色链，对于这两个对角顶点来说是连通的，那么即就是施行了颜色交换技术也是空不出颜色来的；而只有当该色链是不连通时，在施行了颜色交换技术后才可以空出颜色来。四种颜色中由某两种颜色构成的色链连通时，而由另两种颜色所构成的色链则一定是不连通的，交换这条不连通的链后，就可以空出一种颜色来。当构形是一个4—轮时，即就是其围栏顶点已占用完了四种颜色，也一定是可以空出一种颜色给等着色顶点的。但在5—轮时，5个围栏顶点占用完四种颜色时，必有两个顶点是用了同一颜色的。由于5—轮的每一个顶点都有两个对角顶点，所以当两个相同颜色顶点之间的那个顶点的两条对角链都是连通的时，则与各色链颜色不同的另外两种颜色构成的色链则一定都不连通，这时可施行两次颜色交换技术，一定可空出5个围栏顶点中用过两次的那种颜色来。但当两条连通的对角链又相交叉时，即就是按上述所说，交换了另外的两条链，也仍是空不出颜色来的。如赫渥特图那样。怎么办，就得想办法把已连通的链断开，然后再施行颜色交换技术。断链的方法也是要用到坎泊的颜色交换技术。看来任何链能否断开，也就成了四色猜测证明的关键了。
设四种颜色A、B、C、D，若A、B构成的色链为A—B，则A和B在A—B链以外，只能与C和D相邻，构成A—C和A—D链，或者B—C和B—D链，从A—B链上的任何一个顶点A或B开始交换以上A—C和A—D链，或者B—C和B—D链中的任何一种链，都可使该链上的顶点A或顶点B变成C或D，使A—B链断开。这样就可以从5—轮中的一个轮沿顶点A或B交换A—B链，空出A或B来。
到此，就可以说明图中的任何链都是可以断开的，也就证明了四色猜测是正确的。

雷明85639720

，，，，