论文研究随机图的均匀边染色算法.pdf

图的均匀边染色是指图中任意两条相邻的边都分配到不同的颜色，且任意两个色类的颜色个数最大相差1。对图G进行均匀边染色所需的最少颜色数叫做G的均匀边色数。针对图的最小均匀边色数进行了研究，提出一种启发式算法。该算法根据均匀边染色条件设计了目标函数，并借助染色矩阵的色补矩阵迭代交换逐步寻优；给出了详细的算法设计流程，并且进行了大量的测试和分析。实验结果表明，该算法可以高效地求出给定点数图的最小均匀边色数，算法时间复杂度不超过O（n3）。