论文研究 随机图的点可区别全染色算法.pdf

点可区别全染色（VDTC）是指在满足正常全染色的基础上，还要使得图中由顶点颜色和其关联边颜色构成的顶点色集合也不同，所使用的最少颜色数称为点可区别全色数。提出了一种针对随机图的点可区别全染色算法，算法的基本思想是对图G中的边随机地进行预染色，查找存在边染色不正常的冲突集，然后根据规则逐步迭代，直至使目标函数的值满足要求，此时说明染色成功。实验结果表明，算法能够有效地求得给定点数随机图的点可区别全色数，算法时间复杂度不超过O（n3）。