摘要
针对随机图设计了一种启发式的邻点可区别I-全染色算法,能够求解随机图的邻点可区别I-全色数.该算法根据邻点可区别I-全染色条件,确立了3个子目标函数和1个总目标函数,利用交换规则逐步寻优,直到目标函数值满足要求时结束.给出了详细的算法设计步骤及流程,同时进行了测试和分析,测试结果表明,该算法可以得到随机图的邻点可区别I-全色数,并且算法的时间复杂度不超过O(n3).
A random graphs is said to be adjacent vertex distinguishing I-total coloring if the color of two adjacent vertexs ,adjacent edges and the color set of adjacent vertex w hich formed by the association edge color are different .Meanwhile ,the minimum number of colors is called the adjacent vertex distinguishing I-total chromatic number w hich can be compute through a new heuristic intelligent algorithm that this pa-per proposed .This algorithm according to adjacent vertex distinguishing I-total coloring conditions to es-tablish three subfunction and a main function ,using the exchange rule gradually search the optimum solu-tion ,until when the value of main function fulfill the end requirement .This paper gives detailed design steps of the algorithm ,meanwhile tested and analyzed it .The test results show that this algorithm can cal-culate adjacent distinguishing I-total chromatic number of a graph w hich has definitized vertex number quickly and efficiently .The time complexity of this algorithm is less than O（n^3 ）.
出处
《西南师范大学学报（自然科学版）》
CAS
北大核心
2015年第4期8-15,共8页
Journal of Southwest China Normal University(Natural Science Edition)
基金
国家自然科学基金项目(11461038)
关键词
随机图
算法
邻点可区别Ⅰ-全染色
邻点可区别Ⅰ-全色数
random graph
algorithm
adjacent vertex distinguishing I-total coloring
adjacent vertex distinguishing I-total chromatic number
