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

On Algorithm for Adjacent Vertex Distinguishing V-Total Coloring of Random Graphs

作　　者：贾西贝[1] 董威[1] 李小慧[1] 李敬文[1] 

机构地区：[1]兰州交通大学电子与信息工程学院,兰州730070

出　　处：《西南师范大学学报（自然科学版）》2015年第2期14-19,共6页Journal of Southwest China Normal University(Natural Science Edition)

基　　金：国家自然科学基金项目(11461038;61163010;61163037)

摘　　要：图G的邻点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色,同时要求相邻顶点的色集合也不相同,所用的最少颜色数称为图G的邻点可区别V-全色数.根据邻点可区别V-全染色的约束规则,设计了一种启发式的邻点可区别V-全染色算法.该算法借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功.给出了算法的详细描述以及算法分析和算法测试结果.实验结果表明,该算法有很好的执行效率,并可以得到随机图的邻点可区别V-全色数,验证了邻点可区别V-全染色猜想,并且算法的时间复杂度不超过O(n3).For adjacent vertex distinguishing V‐total coloring of graph G ,the colors of both adjacent edges and vertex with its incident edges should be different .Moreover ,the color sets of any pair of adjacent ver‐tices are not the same .The minimum coloring number is called the adjacent‐vertex‐distinguishing V‐total chromatic number of G .In this paper ,a heuristic algorithm for adjacent vertex distinguishing V‐total colo‐ring has been designed according to its constrain rules .The algorithm iterates gradually in proper sequence with the help of the color matrix and complementary set .When the generic function value meets the re‐quirement ,we hold that the current coloring is successful .This paper gives a detail description of the algo‐rithm ,algorithm analysis and algorithm testing results .The experimental results show that the algorithm has good efficiency and can obtain the adjacent vertex distinguishing V‐total chromatic number of random graphs .The results permit the adjacent vertex distinguishing V‐total coloring conjecture ,and the time complexity of the algorithm is not more than O（n3 ） .

关 键 词：随机图 算法 邻点可区别V-全染色 邻点可区别V-全色数 

分 类 号：O157.6[理学—数学]