随机图的正常均匀全染色算法  

Normal equitable total coloring algorithm of random graphs

作　　者：尹波[1] 李敬文[1] 代素敏[1] 胡腾云[1] 

机构地区：[1]兰州交通大学电子与信息工程学院,兰州730070

出　　处：《计算机应用》2015年第8期2140-2146,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(11461038;61163037;61163010)

摘　　要：目前对图的均匀全染色的研究仅限于一些如完全图、正则图等特殊图,还没有发现用于研究一般简单连通图的正常均匀全染色的算法。为了研究一般图的正常均匀全染色,根据正常均匀全染色的点约束、边约束、点边约束和均匀约束四个约束规则,设计了一种新的启发式智能算法。首先,该算法确定四个子目标函数和一个总目标函数;然后,在每个子目标函数内借助染色矩阵及色补集合矩阵逐步迭代交换,直到子目标函数值为0时,子目标染色完成;最后,当每个子目标函数值都为0时,总目标函数值为0,染色成功。实验结果表明,该算法可以生成8个点以内的所有简单连通图,并能对每个生成图进行正常均匀全染色,得到其均匀全色数,且验证得对任意的正整数k,当3≤k≤9时,随机图G都有k-均匀全染色。同时在20到400个点之间选取了72个图,用所提算法对其进行均匀全染色,并依据染色结果绘制了它们的点数-边密度-所需色数关系图。The research on the equitable total coloring is limited to some special graphs such as complete-graph and join- graph. For the normal equitable total coloring of the simple connected graph, there is not any feasible method in the published paper. In order to research the equitable total coloring of the normal graph, a new heuristic intelligent algorithm was proposed according to four constraint rules including vertex constraint rule, edge constraint rule, vertex-edge constraint rule and equitable constraint rule of the equitable total coloring. First, four sub-functions and one total function were ascertained. Second, by using the dyeing matrix and complementary matrix in each sub-function, the iterative exchange did not stop until each sub-function value was zero, that meant the subgoal-coloring was completed. If each sub-function value was 0, the total function value was 0, which meant coloring was successful. The experimental results show that the proposed algorithm can generate all of the simple connected graphs in which the number of vertices is no more than 8, and it can achieve the corresponding coloring, and then obtains the equitable total chromatic number. Also when any positive integer k is not less than 3 and not more than 9, random graph G has k-equitable total coloring. At the same time, the proposed algorithm chooses 72 graphs whose vertex number is between 20 and 400, and draws the diagram about the vertex number, edge number and color number according to the equitable total coloring resuhs.

关 键 词：图 正常均匀全染色 均匀全色数 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]