基于遗传算法的图关联着色算法  

Algorithm for Graph Incidence Coloring Base on Hybrid Genetic Algorithm

作　　者：刘西奎[1] 李艳[1] 许进[2] 

机构地区：[1]山东科技大学信息科学与工程学院,泰安山东271019 [2]华中科技大学控制科学与工程系,武汉430074

出　　处：《工程数学学报》2004年第1期41-47,共7页Chinese Journal of Engineering Mathematics

基　　金：国家自然科学基金项目项目 (6 0 1 74 0 4 7和6 0 2 74 0 2 6 )

摘　　要：图的着色算法是一种典型的NP 完全问题。给出了一种用于图的关联着色的遗传算法。遗传算法用于进行全局搜索 ,从而有效的查找解空间。文中对关联色数为 6的一个图进行了仿真实验 ,给出了该图的关联色数以及 4种 6 关联着色。用本文提出的算法 ,得到了完全图、完全多部图的关联色数。实验结果表明 ,本文设计的遗传算法可以很好的对关联着色猜想进行求解 ,获得问题的高质量的解。The problem coloring on a graph is a NP-hard problem. We presents a genetic algorithm for the incidence coloring on graphs. Genetic algorithms are used to perform local global exploration among a population, while heuristics methods are used to perform local exploitation around the chromosome. The paper gives a simulating about a graph with incidence coloring number 6, and obtains the incidence coloring number of the graph, also obtains four different incidence colorings on the graph. Using the algorithm presented by this paper, we get the incident coloring number of the complete graphs and of the complete m-partite graphs. The experimental results indicate that the incident coloring number of graphs can be obtained by this genetic algorithm, and the solutions with excellent quality of problem can be obtained.

关 键 词：关联着色 关联色数 关联图 遗传算法 

分 类 号：O157.05[理学—数学] TP3[理学—基础数学]