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

图[G]的点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色，同时要求所有顶点的色集合也不相同，所用的最少颜色数称为图[G]的点可区别V-全色数。根据点可区别V-全染色的约束规则，设计了一种启发式的点可区别V-全染色算法，该算法借助染色矩阵及色补集合逐步迭代交换，每次迭代交换后判断目标函数值，当目标函数值满足要求时染色成功。给出了算法的详细描述、算法分析和算法测试结果，对给定点数的图进行了点可区别V-全染色猜想的验证。实验结果表明，该算法有很好的执行效率并可以得到给定图的点可区别V-全色数，并且算法的时间复杂度不超过[O(n3)]。