随机图的均匀边染色算法  

Algorithms for equitable edge coloring of random graphs

作　　者：代素敏[1] 胡腾云[1] 尹波[1] 李敬文[1] 

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

出　　处：《计算机应用研究》2016年第6期1703-1707,共5页Application Research of Computers

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

摘　　要：图的均匀边染色是指图中任意两条相邻的边都分配到不同的颜色,且任意两个色类的颜色个数最大相差1。对图G进行均匀边染色所需的最少颜色数叫做G的均匀边色数。针对图的最小均匀边色数进行了研究,提出一种启发式算法。该算法根据均匀边染色条件设计了目标函数,并借助染色矩阵的色补矩阵迭代交换逐步寻优;给出了详细的算法设计流程,并且进行了大量的测试和分析。实验结果表明,该算法可以高效地求出给定点数图的最小均匀边色数,算法时间复杂度不超过O(n3)。An equitable edge coloring of graph G is that adjacent edges of a graph have different color and the sizes of its color classes differ by at most 1. The minimum number of colors is called the equitable edge chromatic number. This paper proposed a new heuristic intelligent algorithm with the study of minimum equitable edge chromatic number. According to the conditions of edge coloring,it created object function,exchanged the color complement matrix of coloring matrix iteratively to find the optimum solution. It gave detailed algorithm,with lots of testing and analysis cases. For a graph with fixed number of vertices,this algorithm can find the minimum equitable edge chromatic number efficiently,while the time complexity of this algorithm is less than O（ n3）.

关 键 词：图 均匀边染色 均匀边色数 启发式算法 染色矩阵 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]