论文部分内容阅读
对“n阶最小5度最大平面图”min5GMn及“n阶最小5度平面图”min5Gn的四色着色方案的求解，提出了“移边法”。“移边法”的基本思想是，移去“n阶最小5度最大平面图”min5GMn或“n阶最小5度平面图”min5Gn中的一条二端点均为5度的边，则得到他们各自相应的子图“n阶最小4度平面图”min4Gn。显然，被移去那条边的二个端点，在各自相应的子图中均为4度。这就可以对子图“n阶最小4度平面图”min4Gn，用“降阶法”(即指“移4度点法”)求得子图“n阶最小4度平面图”min4Gn的一个(或多个)四色着色方案。以其中一个四色着色方案为起始，利用“多层次的二色交换法”，即可得到该子图“n阶最小4度平面图”min4Gn的一个相应的“相近四色着色方案集”。在这个“集”中，被移去的边的二个端点是异色的那些四色着色方案，就是原母图“n阶最小5度最大平面图”min5GMn或“n阶最小5度平面图”min5Gn的部分四色着色方案。由此，原母图的四色着色方案就被求得，这就是“移边法”。文中以实例(“Heawood的反例，HCE”GM25.HCE)验证了该方法的正确性和有效性;并得到了“Heawood的反例”的一些四色着色方案(计84种)。