CAJ | 학술논문

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