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

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

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.