图论是离散数学的一个重要研究分支,现实生活中很多实际问题都可以抽象成图,并应用图论的知识解决。图染色问题是图论中一个重要的研究方向,在理论和工程上很多组合优化、加工调度、最大支配集等问题都可利用图染色的方法解决,因此,图染色受到了国内外的专家学者的广泛研究,并取得到了很多有价值的研究成果。图染色问题是一个NP完全问题,目前应用于解决此问题的算法主要有仿生算法和智能优化算法,如:遗传算法、模拟退火算法、神经网络,且这些算法仅限于解决图的正常点染色和边染色问题,对于染色条件复杂D(β)-染色问题,目前尚未发现相关的算法,本文旨在设计一种新的算法来解决此类问题。2006年,张忠辅教授等给出了图的D(β)-点可区别边染色和D(β)-点可区别全染色的定义和相关猜想。截止目前,对于D(β)-染色的研究,仅得到了针对特殊图如路、星、扇、轮、完全图等的一些研究结果,但针对一般图的解决方法目前还没有。本文针对随机图(即:简单无向连通图)的D(β)-点可区别边染色、D(β)-点可区别全染色给出了相应的解决算法,其主要研究工作包括以下几个方面。(1)设计并实现了随机图的生成算法和有限点所有同构图的生成算法,并分别进行了测试,得到了一系列结果,为后续染色算法的测试做准备。(2)设计并实现了解决D(β)-点可区别边染色和D(β)-点可区别全染色问题的2个多目标优化算法。根据定义,将染色的多个约束条件分别设计成子目标函数,总目标函数设计为子目标函数值之和,每一个子目标函数按照顺序迭代运算,逐步得到最优解,此时染色成功;同时,对算法的正确性、收敛性和复杂度进行了分析。(3)设计了详细的算法测试方案,进而得到了大量的染色结果。通过对实验结果的分析,得到了2个重要结论,同时也表明两个染色算法有很好的执行效率。