摘要
本学位论文主要考虑图的不完备可区别染色问题。图染色是图论中一个非常重要的研究方向，在实际问题中有着很好的应用，排课表问题、任务分配问题、集成电路布线等都可以从图染色的角度来解决。可以说，图染色为一些实际问题的解决提供了一种新的思路和方法。由于实际问题的复杂性，单一的点染色或者边染色并不能完全满足问题的要求，研究者们便提出了各种各样的染色问题，如点（邻点）可区别染色、均匀染色、可约染色等，并得到了很多有价值的理论成果，而不完备可区别染色便是由于实际问题的需要，在正常可区别染色基础上的弱化。由于图的染色问题是一个NP-完全问题，目前解决图染色问题的算法主要依赖于智能算法，但只限于解决特殊图的点染色或者边染色，不能解决全染色和可区别染色问题，而现实中的很多问题所转化的图都具有一定的随机性，所以寻求针对任意一个图的高效的染色算法已成为图论研究者的一个重要的课题。对于不完备可区别染色，已发表的文献中虽然得到了一些理论成果，却没有可行的染色算法,而算法的实现对相关问题的研究具有较高的实际意义。所以，本文根据不完备可区别染色的染色要求，设计出了针对任意一个简单连通图的染色算法，通过大量的测试分析，算法具有较高的染色效率。本文的工作如下： （1）介绍了与本文有关的一些基本染色概念及猜想，同时给出本文有关内容的研究背景、国内外研究动态等。 （2）介绍了粒子群算法、遗传算法的基本思想、流程，及其在图染色中的应用，并对这些算法在解决图染色问题的性能上进行了分析。 （3）针对任意简单连通图设计了四种不完备邻点可区别全染色算法，包括一种基于正常点染色的邻点可区别E-全染色算法，和三种基于正常边染色的算法，分别为邻点可区别V-全染色算法、邻点可区别I-全染色算法和邻点可区别VI-全染色算法。前者采用先顶点染色再边染色的方法，而后者采用先边染色再顶点染色的方法。其中，算法中设计的边染色方法，可以解决任意一个图的正常边染色问题，而且根据染色条件的变化还可以解决其它基于正常边染色的全染色或可区别染色问题。文中给出了算法的详细流程及测试，并对算法的正确性、收敛性和时间复杂度进行了分析，最后对算法做了总结。
NETL