求证四色问题的构形及分类

晋源泉

求证四色问题的构形及分类

一、地图的构形及其不可免构形集
1、地图的构形：
      任何一个区域的周边的区域数d≥0 , 这就是地图的构形。                          
2、地图构形的不可免构形集
    由肯普定理（每一幅正规地图必定至少含有一个边数少于6的区域）可得每一幅正规地图M n的对偶图Gn必定至少含有一个度数小于6的顶点，在对偶图Gn中，度数小于6的5、4、3、2、1、0度顶点的集合叫地图构形的不可免构形集。
二、求证四色问题的构形及其不可避免构形集
1、着色困局：
对无穷多的任何平面图着色时，经常发生最后才着色的一个顶点周围已着了4种颜色的情况，这种情况就叫着色困局。
2、待着色顶点和可着色顶点：
在着色困局中的最后才着色的这个顶点叫待着色顶点。不是着色困局中的最后才着色的这个顶点叫可着色顶点。
3、求证四色问题的构形
在求证四色问题时，把含有一个待着色顶点的平面图就叫做“求证四色问题的构形”。
4、待着色顶点的度也叫构形的度。构形的度虽然可以是无穷大的，但任何平面图中总存在着至少有一个小于等于5度的顶点，在着色时总可以把待着色顶点的度确定为小于等于5。用小于等于5度的有限构形替代大于等于6度的无穷构形，就把一个大于等于6度的无穷多的问题转化成了一个相对有限的问题了。把小于等于5度的构形的集合就叫做求证四色问题的平面图的不可避免构形集。
5、求证四色问题的不可避免构形集：
在LQD系列图表中的0、1、2、3度系列中不存在着色困局，最后才着色的这个顶点叫可着色顶点。因此，小于等于3度的构形不存在。所以，4、5度系列的构形集合就是平面图的不可避免构形集。
三、求证四色问题的构形分类
按其顶点的最小度进行分类，求证四色问题的构形只有顶点的最小度分别是4、5度无穷系列两类构形。
1、4度无穷系列类构形：
这一类是构形中顶点的最小度是4的4度无穷系列构形G n ， n≥6。只要研究者具体构建的求证四色问题的构形中存在顶点的最小度是4度，其就属于4度无穷系列构形G n之一。因为，任何一个4度以上的待着色定点都可以移动到最小度是4度的顶点上。
2、5度无穷系列构形：
这一类是构形中顶点的最小度是5的5度无穷系列构形G n ， n≥14 。只要研究者具体构建的求证四色问题的构形中存在顶点的最小度是5度，其就属于5度无穷系列构形G n之一。因为，任何一个5度以上的待着色定点都可以移动到最小度是5度的顶点上。