1. 研究目的与意义（文献综述包含参考文献）

图论是组合数学的一个分支，是离散数学的重要组成部分。

它起源于1736年欧拉发表的图论首篇论文#8212;《哥尼斯堡七桥问题无解》; 1936年，匈牙利数学家柯尼希(konig)出版的图论第一部专著《有限图与无限图理论》标志着图论正式成为一门独立的学科; 近半个世纪以来，随着计算机科学的发展，图论更以惊人的速度向前发展，可以说是异军突起，活跃非凡。

图的着色问题是现代图论中的一个主要的研究课题之一。

2. 研究的基本内容、问题解决措施及方案

图着色问题（graph coloring problem, gcp） 又称着色问题，是最著名的np-完全问题之一。

通常的解决着色问题的算法采用蛮力法，贪婪法，深度优先或广度优先等思想可以得到最优解，但时间复杂性太大。

故采用遗传算法这样的启发式算法来解决图着色问题，以提高算法效率，得到最优解。