用约当曲线理论解释图着色中坎泊的颜色交换技术

雷明85639720

用约当曲线理论解释图着色中坎泊的颜色交换技术
雷  明
（二○一五年三月三日）

图论中的道路实际上就是一条曲线，在该曲线上分布着图中的一些顶点。用两种颜色给某条道路上的顶点交替着色的道路就是一条色链（也是曲线）。这种用两种颜色交替着色的色链若是一条环形链时，就是一条约当链，也可以说是一条约当曲线。
用四种颜色着色的图中，若存在由某两种颜色组成的约当链时，则由另外两种颜色组成的相反链，一定是被该约当链隔离成了互不相通的两部分，从一部分到达另一部分时，必须要经过约当链上的顶点。
图着色中，坎泊的颜色交换技术实质上就是把色链上的顶点所着的两种颜色进行交换，使链中原来着A的顶点着上B，而使原来着B的顶点又着上A。
着色过程中使用坎泊颜色交换技术的目的是想通过交换以达到使与待遇着色顶点相邻的所有顶点所用颜色的总数减少的目的，以空出颜色给待着色顶点着上。当待着色顶点与其相邻的两个对角顶点组成了一条约当链时，即就是对该约当链进行了颜色交换，也是不能空出颜色来的，其结果只能是与待着色顶点相邻的两个对角顶点的颜色相互调换了一下，没有达到减少颜色的目的。而只有当待着色顶点与其相邻的两个对角顶点组成的色链不是约当链时，从与待着色顶点相邻的两个顶点中的任何一个顶点开始交换，都是可以空出颜色给待着色顶点的。这种交换就是坎泊已经用过的对非H构形进行的交换。
另外，图中若有一条约当链，但其中不包括待着色顶点，则交换该约当链内外任一部分的相反链时，另一部分的相反链并不会发生变化，这样就从整体上达到了改变已经着上了颜的色顶点间的各种链的相互关系，从而使构形发生了变化。比如对赫渥特图中的约当链C—D内外的任一条相反链A—B进行交换，对米勒图中的约当链A—B内外的任一条相反链C—D进行交换，都可以使图由H构形变成非H构形，然后再施行一次颜色交换技术，就可以空出颜色给待着色顶点着上。

雷  明
二○一五年三月三日于长安

雷明85639720

，，，，，，，，