摘要
针对一般图设计了一种新型的点可区别边染色算法。该算法把概率思想和图染色相结合,根据点可区别边染色的约束规则确立目标函数,利用交换规则逐步寻优,当目标函数的值满足要求时染色成功。给出详细算法步骤并进行了测试和分析,实验结果表明该算法可以求出满足猜想的点可区别边色数。
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.
出处
《计算机应用研究》
CSCD
北大核心
2014年第3期760-764,共5页
Application Research of Computers
基金
国家自然科学基金资助项目(61163010
10771091)
关键词
经典算法
一般图
点可区别边染色
概率思想
约束规则
交换规则
classical algorithms
general graphs
vertex-distinguishing edge coloring
probability thought
constraint rules
exchange rules
