随机图的邻点可区别 I-全染色算法

摘要：

针对随机图设计了一种启发式的邻点可区别I 全染色算法，能够求解随机图的邻点可区别I 全色数。该算法根据邻点可区别I 全染色条件，确立了3个子目标函数和1个总目标函数，利用交换规则逐步寻优，直到目标函数值满足要求时结束。给出了详细的算法设计步骤及流程，同时进行了测试和分析，测试结果表明，该算法可以得到随机图的邻点可区别I 全色数，并且算法的时间复杂度不超过O（n3）。

关键词：随机图、算法、邻点可区别I-全染色、邻点可区别I-全色数

分类号：O157.5(代数、数论、组合理论)

资助基金：国家自然科学基金项目11461038．

在线出版日期：2015-05-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：8-15