许多现实问题可转化为图的模型并由图论解决，图论中存在许多NP难问题，使这一领域成为很受欢迎的启发式算法的实验场。近些年，图算法专著层出不穷，图染色问题(Graph Coloring Problem，简记GCP)则可以看作图论中NP难问题群中的一个族。经典图染色问题狭义上指图的点染色问题，1889年Tait撰文提到图的边染色概念，文中他指出四色定理问题与使用三色集完成任意3连通平面三次图(3-connected planar cubicgraph)边染色是等价问题，并给出染色数的上界与G的有关，之后Vizing给出并证明了一个广义的上界，即对于任意简单图，边色数不超过最大度加1。国内外众多研究者设计了许多基于此理论的精确或启发式算法，保证此上界的前提下提高算法效率。在20世纪60年代出现多条件约束的染色—全染色问题，由M. Behzad和Vizing分别独立提出。由于计算机软硬件技术不断更新，全染色算法设计逐步变得可行并且受到重视。基于全染色问题的提出思路，一部分研究将重点倾向于在现有问题中添加约束条件。1993年，A. C. Burris和R. H. Schelp提出点可区别边染色的概念，并给出上界猜想。2002年，在点可区别边染色基础上，张忠辅提出了图的邻点可区别边染色，之后张在该研究问题上继续增加约束条件，于2004年提出邻点可区别全染色概念，同时给定了部分特殊图的邻点可区别全染色数，至2008年，又提出了点可区别全染色的概念，总结大量实验结果并提出此问题的染色上界猜想，之后其进一步提出了Smarandachely染色问题系列，包括Smarandachely邻点可区别边染色、Smarandachely邻点可区别全染色、Smarandachely点可区别边染色和Smarandachely点可区别全染色等概念及相关上界猜想。本文针对任意简单连通图设计了关于Smarandachely染色的四种启发式算法，并对算法进行了分析和测试，通过对测试结果深入分析，获得了一些有趣的结论。本文的主要研究工作如下：(1)主要了解了图染色尤其是Smarandachely染色的相关理论背景及国内外动态。学习研究了大量的有关于图染色的文献，特别研究了大量的应用于解决图染色问题的精确算法和启发式算法，比如图着色问题的新遗传算法、均匀染色问题的神经网络模型算法等。比较和分析这些文献中的算法特点，取其精华去其糟粕，为本算法的提出和实现提供了坚实的理论基础。(2)在上述学习的基础上，针对随机图设计了四种启发式算法，分别解决四种Smarandachely染色问题；对算法从正确性、收敛性和时间复杂度三个方面进行了分析；设计了测试方案，如10个点以内所有图的测试、特殊图的测试等，并对测试结果进行了分析。通过以上的工作，得到了一些有趣的结论为图染色相关猜想的研究提供有益的参考，也为将图染色应用于解决实际问题中提供研究手段。