全文总字数：5620字

1. 研究目的与意义及国内外研究现状

在图论中，最出名的且持续了很长时间才被解决的问题莫过于四色问题，该问题起源于一个著名猜想，称为四色猜想，由此而激发了对图着色问题的深入研究。更重要的，图着色问题受到科学领域内不同学科学者的兴趣和关注还在于其在各个领域中都有广泛的应用，如：

(1)课程考试安排问题：设某一学校有n门课程由学生选修。学期结束要进行考试，当然每个学生每场只能参加一门课程的考试。显然没有共同学生的两门课的考试可以在同一时间进行。试问这次考试最少要进行几场?

在平面上取v₁,v₂,…, v_n，n个顶点分别表示这n门课程，若有同学同时选了课程i和课程j，则过v_i和v_j两点连一条边，结果得一有n个顶点的图g。考试的安排问题相当于图g的顶点着色问题。着同一颜色的顶点对应的课程可同时进行考试。使图g的相邻顶点有不同颜色的最少颜色数目，便是进行考试的最少场数。

(2)物资储存问题：设有n种物资要存放在仓库里，但有的物资不能放在同一房间里，否则将引起损坏，甚至发生危险。问存放这n种物资最少耍几个房间?

2. 研究的基本内容

（1）介绍图染色的相关理论知识，以及求解图染色问题的几种简单算法；

（2）分析粒子群算法的流程，简单介绍粒子群算法的几种应用；

（3）将粒子群算法应用于求解图染色问题，设计出新的算法，并对过程中出现的不合法解以一定的方式进行修改；

3. 实施方案、进度安排及预期效果

1、实施方案

用粒子群算法解决图染色问题，在设计出新的算法时着重于分析迭代过程并且对出现的不合法解及时进行修改。

2、进度安排

4. 参考文献

【1】黄晓妃.浅谈图的染色理论及其实际应用[J].成功（教育），2011，No.14:279.

【2】严肃.图的染色理论研究得到新的结果[J].中南民族学院学报（自然科学版），2001（04）：72.

【3】张楠,蒋海凤.图的染色问题及其应用[J].计算机光盘软件与应用, 2014，No.17:166-167.

【4】袁占亭,张秋余,刁雪峰,张安杰.课程表问题的一种模拟退火超启发式算法[J].计算机工程与设计，2008（02）：398-400.

【5】张卫平,赵强.图染色思想在物流配送中的一种应用[J].电脑知识与技术，2011，No.16:3936-3937.

【6】孙湘, 周大为,张希望.惯性权重粒子群算法模型收敛性分析及参数选择[J].计算机工程与设计，2010，No.18:4068-4071.

【7】刘衍民.粒子群算法的研究及应用[D].山东.山东师范大学,2011.

【8】刘丽芳.粒子群算法的改进及应用[D].山西.太原理工大学，2008.

【9】严露.粒子群算法研究与应用[D].四川.电子科技大学，2013.

【10】Raja Marappan,Gopalakrishnan Sethumadhavan, R.K. Srihari.

New Approximation Algorithms for SolvingGraph Coloring Problem - An Experimental Approach[J].Perspectives in Science,2016

【11】Jiang Xingpeng , Li Yin , Meng Ya , Meng Dazhi . A new DNA algorithmto solve graph coloring problem[J].Progress in Natural Science ,2007,(06),pp.733-738

【12】Dr.HusseinAI-Omari,Khair Eddin Sabri. New Graph Coloring Algorithms[J]. Journal ofMathematics and Statistics,2006,Vol.2 (4),pp.439