[原创]着色过程中必须注意的几个问题

雷明85639720

[watermark]

着色过程中必须注意的几个问题
雷  明
（二○一四年元月二日）
研究四色问题时，必然要进行着色，着色时必然要使用泊所创造的颜色交换技术，进行链的交换，也必然要遇到所交换的链的连通性问题，对所进行交换的链的选择性交换问题等等。
1、进行交换的目的性：
有三种交换目的：㈠ 一是通过交换以达到从5—轮的轮沿顶点中空出一种颜色给待着色顶点着上；㈡ 二是通过交换以达到改变某顶点的颜色，或者达到破坏某链的连通性（断链），或者达到改变构形有结构（顶点着色相对的改变），并不是要空出颜色；㈢ 三是通过两次交换达到同时移去5—轮轮沿顶点中两个相同颜色的目的。交换的目的性不同，交换的链，交换的起点，也就是不同的。目的㈠必须交换在5—轮轮沿顶点中只用了一次的颜色的不连通的对角链；目的㈡必须交换的是从图整体上看是不连通的链；目的㈢则必须交换5—轮轮沿顶点中用了两次的颜色的链，共交换两次，其先后次序也是有选择的。
2、链的连通性问题：
四种颜色着色，每两种颜色所能组成的链只有六种。在一个已着色的图中，㈠ 从图整体上看，从某两种颜色组成的链的任何一个顶点起，可以到达图中所有着这两种颜色的顶点时，这样的链叫连通链，否则就是不连通链。一个图若从整体上看，只要含有这种整体上的不连通链时，那么该图中由另外两种颜色组成的链一定是带有环的链（连通不连通倒不一定），该环把上面所说的那条不连通连分成了环外环内互不连通的两部分。交换了一个部分，都不会影响另一部分的着色情况。㈡ 从只有一个中心顶点未着色的5—轮看，其两对角顶点的颜色所组成的链，从一个对角顶点能到达另一个对角顶点时的链叫连通链，否则也是不连通链。一个5—轮中只要有一条连通的对角链，那么另一条不同颜色构成的对角链一定是不连通的。
3、交换的链的选择问题：
无论交换的目的是什么，只要是要用坎泊的颜色交换技术，都存在一个交换什么样的链（连通还是不连通，是整体连通的还5—轮对角连通的）和选择交换那条链的问题。㈠ 如果交换的目的只是为了空出一种颜色给待着色顶点着上，交换的链应是连接着5—轮轮沿顶点的不连通的对角链，否则是空不出颜色的；㈡ 如果交换的目的只是为了改变构形的结构（即改变某顶点的颜色和破坏某链的连通性的“断链”），交换的链应是从图整体上看是不连通的链，否则也是不能改变图的构形结构的；㈢ 如果交换的目的是为了同时移去5—轮轮沿上的两个同色，则：① 对于H—构形是不须进行选择的，先从那一个同色顶点开始交换都是可以的，交换的结果使图由一个H—构形变成了一个半H—构形，并没有移去两个同色；② 对于非H—构形，也是无须进行选择的，也是先从那一个同色顶点开始交换都是可以的，只是交换的结果与H—构形交换的结果不同，而是直接就空出了两个同色，给待着色顶点——5—轮的中心顶点着上即可；③ 对于半H—构形，则必须进行很好的选择，首先开始交换的顶点和链选择对头了，就能同时移去两个同色，给待着色顶点着上，否则图的构形将又会变成H—构形，产生恶性的循环。赫渥特对他的图不能进行4—着色，可能就是这样的原因吧。
4、交叉链与构形的问题：
在5—轮构形的5个轮沿顶点4着色的情况下（设共用了b、r、g、y四种颜色，其中r色用了两次），其对角链有共用顶点的情况有多种情况：㈠ 两链虽有共用顶点，但实际上并没有真正意义上的交叉，这种共用顶点叫“相交点”，这种链应叫“相交链”；㈡ 如果两链在共用顶点处产生了真正意义上的交叉，则这种共用顶点叫“交叉点”，这种链叫“交叉链”。㈢ 只有一个“相交点”的“相交链”的构形是非H—构形（如5—轮中的b—g链和b—y链相交）；㈣ 含有两个同色顶点颜色的两链若只有一个“交叉点”的“交叉链”的构形也是非H—构形（如5—轮中的g—r链和y—r链相交叉）；㈤ 不含两个同色顶点颜色的两链有一个“交叉点”的“交叉链”的构形则是H—构形（如5—轮中的b—g链和b—y链相交叉）。㈥ 不含两个同色顶点颜色的两链若含有奇数个“交叉点”时，是H—构形；㈦ 而含有偶数个“交叉点”时，则是非H—构形，因为每两个“交叉点”已相互抵消，实际上已经不相交叉了。
雷  明
二○一四年元月二日与长安