图的染色问题是图论中的一个经典难题,它也是科学计算与工程设计中一个重要和基本的问题。事实上,许多现实生活中的问题例如考试时间表问题和任务分配问题等都可以被模拟成图的着色问题的拓展。其中图的边着色和图的全着色问题以及图的色数问题都可以转化为图的顶点着色问题进行处理。由于图的着色问题属于NP完全问题,不可能在多项式时间内得到最优解。现已有一些经典算法如遗传算法、神经网络、模拟退火算法等是求解这类NP完全问题的有效方法,但在规模增大的情况下,特别是在完全图的点可区别强全染色的应用中,它们会表现出一些不可避免的缺陷。本文的主要研究工作如下:(1)分析了基于经典算法(遗传算法、神经网络、模拟退火算法)的正常K-点染色,并把它们应用到完全图的点可区别强全染色中,分析了应用之后出现的一系列问题以及造成的后果,结果表明这些算法是不适合应用在完全图的点可区别强全染色中的。(2)结合完全图和点可区别强全染色的特点,在得到完全图的点可区别强全染色色数的情况下,把需要染色的颜色分为两部分:超色数和正常色数,并且算法的重点是超色数的染色,本文在研究了超色数染色的数学推理之后,巧妙地实现了超色数的染色。在.net环境下用VB语言对算法进行描述,在短时间内对任意点的点可区别强全染色得到了预期的实验结果。实验结果验证该算法有较快的运行速度和较高的收敛速度。也可对算法稍加改动,即可得到有关完全图的其它一些染色结果,如邻点可区别边染色、邻点可区别全染色、点可区别边染色、点可区别全染色等。(3)分析了路和圈的特点,推理得到了圈的点可区别强全染色的色数,本文设计了一个算法,并在.net环境下验证得到12个点以内的5染色结果,这用手工染色在短时间内是无法完成的。