| 图的点可区别边染色算法研究 |
| |
| 引用本文： | 李敬文,张云寒,陈志鹏,孙 亮.图的点可区别边染色算法研究[J].计算机应用研究,2014,31(3):760-764. |
| |
| 作者姓名： | 李敬文 张云寒 陈志鹏 孙 亮 |
| |
| 作者单位： | 兰州交通大学 电子与信息工程学院, 兰州 730070 |
| |
| 基金项目： | 国家自然科学基金资助项目（61163010, 10771091） |
| |
| 摘 要： | 针对一般图设计了一种新型的点可区别边染色算法。该算法把概率思想和图染色相结合, 根据点可区别边染色的约束规则确立目标函数, 利用交换规则逐步寻优, 当目标函数的值满足要求时染色成功。给出详细算法步骤并进行了测试和分析, 实验结果表明该算法可以求出满足猜想的点可区别边色数。
|
| 关 键 词： | 经典算法 一般图 点可区别边染色 概率思想 约束规则 交换规则 |
Research of algorithms for vertex-distinguishing edge coloring of graphs |
| |
| LI Jing-wen,ZHANG Yun-han,CHEN Zhi-peng,SUN Liang.Research of algorithms for vertex-distinguishing edge coloring of graphs[J].Application Research of Computers,2014,31(3):760-764. |
| |
| Authors: | LI Jing-wen ZHANG Yun-han CHEN Zhi-peng SUN Liang |
| |
| Affiliation: | School of Electronic & Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China |
| |
| Abstract: | This paper designed a new algorithm for vertex-distinguishing edge coloring of graphs. This new algorithm had combined probability thought and graph coloring, established objective function according to the constraint rules of vertex-distinguishing edge coloring, used exchange rules to optimize the results gradually, accomplished coloring when the value of objective function met the requirements. The paper also described the algorithm steps in detail, tested and analyzed it. And the experimental results show that the edge chromatic number that the algorithm got conforms the conjecture of vertex-distinguishing edge coloring of graphs. |
| |
| Keywords: | classical algorithms general graphs vertex-distinguishing edge coloring probability thought constraint rules exchange rules |
|
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
