图的点可区别边染色算法研究  

Research of algorithms for vertex-distinguishing edge coloring of graphs

作　　者：李敬文[1] 张云寒 陈志鹏[1] 孙亮[1] 

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

出　　处：《计算机应用研究》2014年第3期760-764,共5页Application Research of Computers

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

摘　　要：针对一般图设计了一种新型的点可区别边染色算法。该算法把概率思想和图染色相结合,根据点可区别边染色的约束规则确立目标函数,利用交换规则逐步寻优,当目标函数的值满足要求时染色成功。给出详细算法步骤并进行了测试和分析,实验结果表明该算法可以求出满足猜想的点可区别边色数。This paper designed a new algorithm for vertex-distinguishing edge coloring of graphs. This new algorithm had com- bined probability thought and graph coloring, established objective function according to the constraint rules of vertex-distin- guishing edge coloring, used exchange rules to optimize the results gradually, accomplished coloring when the value of objec- tive function met the requirements. The paper also described the algorithm steps in detail, tested and analyzed it. And the ex- perimental results show that the edge chromatic number that the algorithm got conforms the conjecture of vertex-distinguishing edge coloring of graphs.

关 键 词：经典算法 一般图 点可区别边染色 概率思想 约束规则 交换规则 

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