四色问题讲座：第三讲 平面图着色中的“构形”

雷明85639720

四色问题讲座：第三讲  平面图着色中的“构形”
    雷  明
对平面图着色时，总是一个顶点一个顶点的着，也总存在着最后一个要着色的顶点。与该顶点相邻的顶点所占用的颜色数小于4时，该顶点一定是可以着上图中已用过的四种颜色之一，或者直接着上图中还没有用过的第四种颜色的。该图的可4—着色也就成功了。若与该顶点所相邻的顶点所占用的颜色数等于4时，如何给该顶点也能着上图中已用过的四种颜色之一，就是四色问题研究的主要任务。这种情况有人叫“染色困局”，也有人叫“颜色冲突”现象。象这样的只有一个顶点未着色，其他顶点都已进行了可4—着色的极大平面图，坎泊在研究四色问题时，就叫做“构形”，现在大家也都一直是这样叫的。构形中未着色的顶点叫“待着色顶点”，常用V来表示；与待着色顶点相邻的顶点叫“围栏顶点”。在画“构形”时，一般情况下只画出待着色顶点和围栏顶点，其他已经4—着色的顶点是不画出的。由于极大平面图中的各个顶点，都是处在一个轮形图的中心位置的，所以这种构形就叫“轮构形”。在具体研究时，各种情况下的构形中需要画出特殊链时，才画出围栏顶点以外的顶点。所以在具体研究时的构形，不一定都是极大平面图，也有非极大图的。各种情况下的构形中的待着色顶点都能着上图中已用过的四种颜色之一时，四色问题也就解决了。这样，就可以用只研究构形的“可约”性（即可4—着色。坎泊用语），来代替对全图中所有顶点的全部着色了。构形是可约的，也就是说构形是可4—着色的。

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，