图着色和标号问题的蚁群优化算法  

Ant Colony Algorithms for Graph Coloring and Labeling Problems

作　　者：林妍[1] 吴瑾[1] 樊锁海[1] 

机构地区：[1]暨南大学信息科学技术学院,广东广州510632

出　　处：《数学的实践与认识》2012年第17期182-191,共10页Mathematics in Practice and Theory

基　　金：国家自然科学基金(10671076;11071089);中央高校基本科研业务费专项基金(21609602);广东省自然科学基金(10151063201000005);暨南大学优秀本科推免研究生科研创新教育培训项目

摘　　要：对图着色问题的最大最小蚁群算法进行了改进,测试结果表明算法有效可行.在此基础上,分别设计了求解图条件着色和标号问题的相应蚁群优化算法,并对中国地图的条件着色、三正则图的条件着色、广义Petersen图的条件着色和标号问题进行了求解优化,改进和完善了目前理论研究的结论.An improved Max-Min Ant algorithm for graph coloring problem is presented, and experimental results on test instances show improvement over existing Max-Min Ant algorithm. The designed algorithm is used to solve some practical problems such as conditional coloring of the map of China, conditional coloring and L（2,1）-labeling of generalized Petersen graph. The solutions by the algorithm improve and makes perfect conclusion from recent theoretical research.

关 键 词：图着色 条件着色 蚁群算法 三正则图 广义PETERSEN图 L(2 1)标号 

分 类 号：O157.5[理学—数学]