图的点可区别Ⅰ-全染色算法

The Algorithm for Vertex Distinguishing Ⅰ-Total Coloring of Graphs

对一个图G,当图中相邻点、相邻边的染色以及任意两点的色集合都不同时称为点可区别I-全染色,其所用最少颜色数称为点可区别I-全色数.根据点可区别I-全染色的约束规则,设计了一种启发式的点可区别I-全染色算法,该算法借助染色矩阵及色补集合逐步迭代交换,确立3个子目标函数和1个总目标函数,利用交换规则逐步寻优,直到目标函数值满足要求时结束.文中给出了详细的算法设计步骤及流程,同时进行了测试和分析.测试结果表明:该算法可以得到图的点可区别I-全色数,并且算法的时间复杂度不超过O(n3).

A graph is said to be vertex distinguishing I-total coloring if the colors of two adjacent vertexs,ad-jacent edges and all vertexs＆#39;color set which formed by the association edge color are different.Meanwhile, the minimum number of colors is called the vertex distinguishing I-total chromatic number.A new heuristic intelligent algorithm is presented for vertex distinguishing I-total coloring according to its constrain rules.By means of the iterative exchange between dyeing matrix and color complement set,three sub-objective func-tions and a general objective function are established.Then by using the exchange rule,the optimum solu-tion is gradually searched and it is ended until the value of general objective function meets the requirement. The detailed design steps of the algorithm are presented and the algorithm is tested and analyzed at the same time.The test results show that this algorithm can calculate vertex distinguishing I-total chromatic number of a graph and its time complexity is less than O（n3 ）.