| 图的邻点可区别全染色算法 |
| |
| 引用本文： | 李敬文,贾西贝,董威,李小慧,闫光辉.图的邻点可区别全染色算法[J].山东大学学报(理学版),2015(2). |
| |
| 作者姓名： | 李敬文 贾西贝 董威 李小慧 闫光辉 |
| |
| 作者单位： | 兰州交通大学电子与信息工程学院,甘肃 兰州,730070 |
| |
| 基金项目： | 国家自然科学基金资助项目(11461038，61163010，61163037)；预研基金 |
| |
| 摘 要： | 在图 G 的一个正常全染色下，G 中任意一点 v 的色集合是指点 v 的色以及与 v 关联的全体边的色所构成的集合。图 G 的邻点可区别全染色就是图 G 的正常全染色且使相邻点的色集合不同，其所用最少颜色数称为图 G的邻点可区别全色数。设计了一种启发式的邻点可区别全染色算法，该算法根据邻点可区别全染色的约束规则，确定四个子目标函数和一个总目标函数，然后借助染色矩阵及色补集合逐步迭代交换，每次迭代交换后判断目标函数值，当目标函数值满足要求时染色成功。实验结果表明，该算法可以得到图的邻点可区别全色数，并且算法的时间复杂度不超过 O（n3）。
|
| 关 键 词： | 图 算法 邻点可区别全染色 邻点可区别全色数 |
The algorithm for adjacent-vertex-distinguishing total coloring of graphs |
| |
| LI Jing-wen,JIA Xi-bei,DONG Wei,LI Xiao-hui,YAN Guang-hui.The algorithm for adjacent-vertex-distinguishing total coloring of graphs[J].Journal of Shandong University,2015(2). |
| |
| Authors: | LI Jing-wen JIA Xi-bei DONG Wei LI Xiao-hui YAN Guang-hui |
| |
| Abstract: | |
| |
| Keywords: | graph algorithm adjacent-vertex-distinguishing total coloring adjacent-vertex-distinguishing total chro-matic number |
| 本文献已被 万方数据 等数据库收录！ |
