首页> 中文会议>中国电子学会电路与系统学会第二十二届年会 >平面图着色的“移边法”

平面图着色的“移边法”

页面导航

摘要
著录项
相似文献
相关主题

摘要

对“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种)。

著录项

来源
《中国电子学会电路与系统学会第二十二届年会》|2010年|110-115|共6页
会议地点上海
作者
冯纪先;
展开▼
作者单位

中国电子学会;

展开▼
会议组织
正文语种
原文格式 PDF
中图分类图论;
关键词
平面图; 着色方法; 降阶法; Heawood反例;

相似文献

中文文献
外文文献
专利

1. 某些平面图着色的性质 [J] . 韩友发 ,王英姣 ,沙欣 . 吉林师范大学学报（自然科学版） . 2016,第001期
2. 平面图着色实际推理过程 [J] . 王琳 ,许春菊 ,王瑛 . 林业勘查设计 . 2006,第003期
3. 关于最大平面图着色的探讨——希伍德的反例是4-色的 [J] . 董德周 . 科技通报 . 2002,第4期
4. 关于最大平面图着色的探讨 [J] . 董德周 . 科学中国人 . 2001,第006期
5. 平面图着色的遗传算法 [J] . 洪斌 . 贵州大学学报：自然科学版 . 1999,第004期
6. 长江口北支平面中缩窄工程对其泥沙输移影响的数值模拟分析 [C] . GUO Chuansheng ,郭传胜 ,TANG Liqun . 第十届全国泥沙基本理论研究学术讨论会 . 2017
7. 平面图着色及多项式在Potts模型中的应用 [A] . 李丹丹 . 2017

平面图着色的“移边法”

摘要

著录项

相似文献

相关主题

期刊订阅