一种图简化方法及其与遗传算法的混合运用

A Method for Simplifying Graph and Its Application Combined with GAs

本文提出了一种适用于图着色问题求解的图简化方法．在这种图简化方法中，图中度小于某个特定值的节点不断被去掉，把这种方法与各种图着色算法结合使用，能提高这些算法的效率．文中分析了应如何设定其特定值，并着重叙述了与遗传算法的混合运用．最后在给出仿真结果的同时，进一步指出了本方法同样适用于求最大全连接子图等其它图论问题．

In this paper,we present a graph simplifying method which is fit for graph coloring problem. In this method,each node is deleted whenever its degree in the attained graph is less than a certain value. When graph coloring algorithms are combined with this simpliying method, their performances can be improved. We also exploit the schemes of setting the value and combining this method with GAs, and show the promising results of the simulation. Finally, it is pointed out that the method is also fit for other graph problems such as the largest clique, maximum independent set, etc.