图的邻点可区别全染色算法

作者：李敬文 贾西贝 董威 李小慧 闫光辉图算法邻点可区别全染色邻点可区别全色数

摘要：在图G的一个正常全染色下,G中任意一点v的色集合是指点v的色以及与v关联的全体边的色所构成的集合。图G的邻点可区别全染色就是图G的正常全染色且使相邻点的色集合不同,其所用最少颜色数称为图G的邻点可区别全色数。设计了一种启发式的邻点可区别全染色算法,该算法根据邻点可区别全染色的约束规则,确定四个子目标函数和一个总目标函数,然后借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。实验结果表明,该算法可以得到图的邻点可区别全色数,并且算法的时间复杂度不超过O（n^3）。

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社