随机图的邻点可区别V-全染色算法

摘要

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