0 引言

图染色是图论中具有重要实际价值和理论意义的课题之一，起源于著名的“四色猜想”，计算机通信、交通定向、物品存储、组合优化等现实生活中的很多问题都可以用图染色的方法来解决，具有很好的应用价值，而均匀染色特别地被用来解决一些如任务调度、分区和负载平衡等有均匀要求的问题。近现代以来，一些数学工作者着力研究了图的染色问题,文献[1-5]在点可区别边染色的基础上提出了邻点可区别全染色、点可区别全染色、距离为β的点可区别全染色、邻点可区别均匀全染色、邻点可区别均匀V-全染色(Adjacent Vertex-Distinguishing Equitable V-Total Coloring,AVDEVTC) 等一系列的概念与猜想，同时还有其他相关概念和研究成果^[6-16]。图的染色问题一般都是NP问题，常见的智能算法如遗传算法、蚁群算法、神经网络等应用于解决图的染色问题时，一般仅限于解决单一约束条件的图染色问题，而面对如邻点可区别均匀V-全染色^[4-5]这样的多约束条件的图染色问题时，普通智能算法就表现出了很大的局限性。目前笔者还未在公开发表的文章中找到利用计算机算法来解决图的邻点可区别均匀V-全染色问题的介绍，因此在以往的研究基础上，提出一种改进的基于多目标优化的染色算法来解决新的问题：即图G的邻点可区别均匀V-全染色问题。算法设计了一个总目标函数和四个子目标函数来对应AVDEVTC的多个约束条件，在染色矩阵上通过每个点的颜色集合的迭代交换操作，使得每个子目标函数都达到最优，进而满足总目标函数的要求。通过大量的实验和分析表明，该算法有着很高的计算效率且能够正确地得到邻点可区别均匀V-全色数(Adjacent Vertex-Distinguishing Equitable V-Total Chromatic Number,AVDEVTCN)^[4-5]和染色后的图的邻接矩阵。最后还给出了大量的测试结果，为以后的图的染色相关定理或猜想的证明提供了基础研究数据。

文中的图为简单无向连通图。对于任意的无向图G(V,E)，V(G)表示图G的顶点集，E(G)表示图G的边集,C(v)表示顶点v和其关联边所用颜色构成的集合，C(v)表示顶点v的色补集合(即未使用颜色集合)，Δ表示图G的最大度。

定义1^[5] 设G(V,E)是阶数不小于2的简单连通图G，k为正整数，f是从V(G)∪E(G)到C={1,2,…,k}的映射，如果f满足如下条件：

1) ∀uv∈E(G),u≠v, f(u)≠f(uv),f(v)≠f(uv)；

2) ∀uv,uw∈E(G)，v≠w，有f(uv)≠f(uw)；

3) ∀uv∈E(G)，C(u)≠C(v)；

则称f是图G的k-邻点可区别V-全染色，简记为k-AVDVTC，并将χ_vt(G)=min{k|k-AVDVTC of G}称为图G的邻点可区别V-全色数,其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}。

定义2^[4-5] 假设f是图G的k-AVDVTC，若同时满足|T_i|-|T_j|≤1(T_i、T_j分别表示颜色i、j的使用次数)，则称f是G的一个邻点可区别均匀V-全染色，简记为k-AVDEVTC。称χ_avdevtc(G)=min{k|G有k-AVDEVTC}为G的AVDEVTCN。

猜想1 对于简单图G，Δ+1≤χ_avdevtc(G)≤Δ+2。

1 图的邻点可区别均匀V-全染色算法 1.1 算法描述

本文算法的基本思想是：先给顶点随机地染色，任意两点所染颜色可以相同；顶点染色完成以后，剔除顶点已经使用的颜色，用剩下的颜色再给顶点相关联的边随机染色，并利用目标函数判断染色结果是否正确，若不满足，按照算法的规则逐步调整存在冲突的染色结果。算法统计了迭代次数并检验了染色结果，经过有限次的颜色调整和交换，最终的染色结果能满足目标函数的要求。具体描述如下：

算法 邻点可区别均匀V-全染色算法。

输入 图G的邻接矩阵；

输出 图G的AVDEVTC矩阵。

1) 给顶点随机染色。

2) 剔除顶点染色已经用过的颜色，用剩下的颜色给顶点相关联的边随机染色，显然点和相关联的边所染颜色是不同的，即f₂(x₂)。

3) 解决边染色冲突。根据每个顶点的色补集合数量的大小生成排序集arrsort[],依次从arrsort[]中取出一个顶点v_i与其后的所有顶点v_j，一一比较两个顶点的色集合，若满足以下要求：

a) 两点之间有边，即color[v_i][v_j]≠0,v_i≠v_j;

b) v_i与v_j的色补集合有交集，即C(v_i)∩C(v_j)≠∅；令temp₁＝f(v_iv_j)。若(C(v_i)∩C(v_j)={a₁,a₂,…,a_i}(v_iv_j∈E(G))，则令f(v_iv_j)=f(v_jv_i)=a₁，并调整色补集合。第一轮变换结束之后，计算f₁(x₁)是否为0，如果不为0，重新生成排序集arrsort[]，继续变换颜色，直到f₁(x₁)=0。

4) 解决顶点的色集合冲突。重新生成排序集arrsort[]，依次从中取出一个点v_i与其后的度相同的点v_j作比较。若：(C(v_i)∩C(v_j)={q₁,q₂,…,q_i}(v_iv_j∈E(G))，则令f(v_iv_j)=f(v_jv_i)=q₁，并调整色补集合。

计算f₃(x₃)是否为0，如果不为0，重复步骤4) ,再次生成排序集，解决色集合冲突，直到f₃(x₃)=0。

5) 计算每种颜色的使用次数并降序排列，存到数组num[][]中，再计算任意两个颜色使用次数的差值，判断|T_i|-|T_j|≤1是否成立。

6) 若|T_i|-|T_j|≤1不成立，尝试调整边的颜色：生成排序集arrsort[]，从中取出两点vfirst和vnext，要求这两点必须满足以下三个条件：

a) 两点之间有边；

b) 两点之间的颜色为使用最多的颜色maxcol；

c) 两点的色补集合有交集，且交集中的元素含有使用次数最少的颜色mincol；

则将满足条件的两点之间的边颜色maxcol替换为mincol，并修改色补集合。重复步骤6) ,直至f₄(x₄)=0。

7) 计算总目标函数F(X)若等于0，则图G的AVDEVTC成功，输出结果集，否则重复上述染色步骤。

利用图的邻点可区别均匀V-全染色算法能够实现随机图的AVDEVTC。

1.2 构建多目标优化模型

多目标优化算法流程如图 1所示。

根据图G的AVDEVTC的定义，该算法必须满足如下几个子目标：①相邻边染不同色；②顶点与其关联边染不同色； ③相邻顶点的色集合不同；④任意两种颜色的使用次数相差不超过1。由以上4个条件可以构造出算法的多目标函数：

$F(\mathit{\boldsymbol{X}})={{f}_{1}}({{x}_{1}})+{{f}_{2}}({{x}_{2}})+{{f}_{3}}({{x}_{3}})+{{f}_{4}}({{x}_{4}})$

决策向量为:

$\mathit{\boldsymbol{X}}=\left( {{\mathit{\boldsymbol{X}}}_{1}},\text{ }{{\mathit{\boldsymbol{X}}}_{2}},\text{ }{{\mathit{\boldsymbol{X}}}_{3}},\text{ }{{\mathit{\boldsymbol{X}}}_{4}} \right)$

决策变量X₁、X₂、X₃、X₄如下：

1) 根据条件①，图G一共包含m条边(e₁,e₂,…,e_m)，因此决策变量X₁=(e₁,e₂,…,e_m)。

2) 根据条件②，图G一共包含n个顶点(v₁,v₂,…,v_n)，因此决策变量X₂=(v₁,v₂,…,v_n)。

3) 根据条件③，图G共有n个顶点，色补集合(C₁,C₂,…,C_n),因此决策变量X₃=(C₁,C₂,…,C_n)。

4) 根据条件④，完成染色所需的颜色分别为(1,2,…,k)，因此决策变量X₄=(1,2,…,k)。

决策变量上下界分别为：u=(m,n,n,k)，l=(1,1,1,1) 。

下面构建目标函数：

1) 边染色目标函数。

对任意相邻的两条边e₁,e₂∈E(G)，令：

${{y}_{1}}({{e}_{1}},{{e}_{2}})=\left\{ \begin{matrix} 1, & f({{e}_{1}})=f({{e}_{2}}) \\ 0, & 其他 \\ \end{matrix} \right.$

则有${{f}_{1}}({{x}_{1}})=\sum\limits_{{{e}_{1}},{{e}_{2}}\in E(G)}{{{y}_{1}}({{e}_{1}},{{e}_{2}})}$，其中f₁(x₁)表示颜色不满足条件①的两边构成的边对个数，当且仅当f₁(x₁)=0时，目标得到最优解。

2) 点边目标函数。

对任意边uv∈E(G)，令：

${{y}_{2}}(v,e)=\left\{ \begin{matrix} 1, & f(uv)=f(u)或者f(uv)=f(v) \\ 0, & 其他 \\ \end{matrix} \right.$

则有${{f}_{2}}(x)=\sum\limits_{uv\in E(G)}{{{y}_{2}}(v,e)}$，其中f₂(x₂)表示与某个顶点颜色冲突的边的个数，当且仅当f₂(x₂)=0时，目标得到最优解。

3) 色集合目标函数。

对于相邻的两点u,v∈V(G)，有C(u)≠C(v)。色集合约束函数定义如下：

${{f}_{3}}({{x}_{3}})=\sum\limits_{uv\in E(G)}{{{y}_{3}}(u,v)}$

其中：${{y}_{3}}(u,v)=\left\{ \begin{matrix} 1, & uv\in \text{E}(G)且C(u)=C(v) \\ 0, & 其他 \\ \end{matrix} \right.$，${{x}_{3}}=({{C}_{1}},{{C}_{2}},...,{{C}_{n}})$； f₃(x₃)表示相邻点对的色集合冲突的个数，当且仅当f₃(x₃)=0时子目标得到最优解。

4) 均匀目标函数。

均匀目标函数的约束条件是任意两个颜色的使用次数相差小于或等于1。设f为E(G)到色集合C={1,2，…，k}的映射；T_i表示图G的染色中i色使用次数，T_i={f(uv)|f(uv)=i,uv∈E(G)}；T_j表示图G的染色中j色的使用次数，T_j={f(uv)|f(uv)=j,uv∈E(G)}。所以均匀目标函数定义如下：对任意两点构成的边uv∈E(G)，令

${{y}_{4}}(i,j)=\left\{ \begin{matrix} 1, & \left| \left| {{T}_{i}} \right|-\left| {{T}_{j}} \right| \right|>1 \\ 0, & 其他 \\ \end{matrix} \right.$

则有${{f}_{4}}(x)=\sum\limits_{uv\in E(G)}{{{y}_{4}}(i,j)}$。 f₄(x₄)表示不满足约束条件④的数量，当且仅当f₄(x₄)=0时，子目标得到最优解。

5) 总目标函数。

${{Q}_{avdevtc}}=\min F(\mathit{\boldsymbol{X}})$

(7)

其中F(X)=f₁(x₁)+f₂(x₂)+f₃(x₃)+f₄(x₄)。F(X)代表所染颜色不满足AVDEVTC四个条件的总数量，当且仅当F(X)=0时总目标得到最优解，即染色成功。

2 染色实例

本文选取了一个8个顶点的随机图来进行测试。

2.1 初始化随机图G

生成8个顶点的随机图的邻接矩阵，如表 1所示，其中d(v_i)表示顶点i的度。

统计各个顶点的度，并确定初始色数k，由于图中最大度为Δ=7,而7度顶点的个数为1，则全染色所需颜色数k=Δ+1=7+1=8。各个顶点的度为7、5、4、3的个数分别为1、2、2、3。

2.2 顶点染色

首先按规则给顶点染色，从1~8中随机地选择颜色为各个顶点进行染色，顶点的颜色可以相同。

2.3 边预染色

在点染色完成后对边随机地预染色，剔除顶点染色用的颜色，用剩下的颜色给顶点相关联的边染色。初始染色矩阵如表 2所示。

由初始染色矩阵可得到各顶点的色补集合，即C(v₁)到C(v₈)依次为：{2,5,6,7}，{3,4,5,6}，{3,4,6,7}，{∅}，{6,7,8}，{6,8}，{1,2,5,6,8}，{2,5,6,7}。

2.4 查找冲突集

若d(v_i)+|C(v_i)|≠k-1，则说明边染色存在冲突，即染色不正常，冲突情况如表 3所示。

2.5 调整染色冲突

根据初始染色矩阵，可以得到冲突集：arrsort[]={v₇,v₁,v₂,v₃,v₈,v₅,v₆,v₄},依次从arrsort[]中取出一个点与后边arrsort中的所有点一一比较，按照算法规则，对存在冲突的颜色进行第一轮交换。依照规则，从v₇开始，依次与其后面的顶点进行比较，v₇与v₈之间有边，且C(v₇)∩C(v₈)={2,5,6}，则令f(v₇v₈)=f(v₈v₇)=2，再修改色补集合，即：C(v₇)={1,3,5,6,8}，C(v₈)={3,5,6,7}。表示为： f(v₇v₈):3→2(指将边v₇v₈的颜色由3调整为2，下同)，f(v₇v₆):7→6，f(v₁v₂):1→5，f(v₁v₈):8→6，f(v₂v₃):8→3,f(v₃v₅):2→6，f(v₃v₆):5→7，f(v₈v₅):4→7，f(v₈v₆):1→5。

经过本轮变换，conflict[0][0](冲突集个数)=0，经检测，点和边、边和边、相邻顶点的色集合的染色冲突已经解决。染色结果如表 4所示。

表 4所示染色结果对应的色补集合C(v₁)到C(v₈)依次为：{1,2,7,8},{1,4,6,8},{2,4,5},{∅},{2,4,8},{1,8},{1,3,5,8},{3,4}。

2.6 检验色数是否均匀

检验颜色使用情况是否均匀，颜色为6、7、1、2、3、4、5、8的使用次数分别为4、4、3、3、3、3、3、2。可以看出，颜色使用不均匀，则按照算法规则继续调整。颜色6使用了4次，颜色8使用了2次，因此尝试将一个边的颜色由6改为8。按照算法，找到了边v₇v₆的颜色为6，将其颜色调整为8，即f(v₇v₆):6→8。

再次检验各个颜色的使用情况，颜色7、6、1、2、3、4、5、8的使用次数分别为4、3、3、3、3、3、3、3。可以看出，各个颜色的使用次数相差不超过1，即f₄(x₄)=0；再次检验染色结果是否满足AVDEVTC的所有条件，经检验：F(X)=f₁(x₁)+f₂(x₂)+f₃(x₃)+f₄(x₄)=0+0+0+0=0，由此可得AVDEVTC成功。最终的染色结果如表 5所示。

表 5所示染色结果对应的色补集合C(v₁)到C(v₈)依次为：{1,2,7,8},{1,4,6,8},{4,2,5},{∅},{2,4,8},{1,6},{1,3,5,6},{3,4}。

3 实验结果数据集

利用该算法得到了大量的实验结果，一方面用来验证相关猜想的成立，另一方面也为相关的研究提供基础数据支持。测试结果主要包括以下5部分：

1) 在1 000个点以内，测试了110万个图，其色数为Δ、Δ+1、Δ+2、Δ+3的图的数量如表 6所示。

2) 对3≤n≤8内的所有图进行了测试，如表 7所示，其中：3至7个顶点内的所有图为经过多方面人工校对过的非同构图最新数量，顶点8的图为包括同构图在内的由图生成算法生成的所有简单连通图数量。

3) 鉴于篇幅限制，只从5~8个点选择了20个图测试了度序列与色数和边数。在表 8中，每一行代表一个图，“度序列”下的数字指的是该图中的顶点度分布，“均匀染色”下的数字指的是该色数的使用次数。

4) 从20到400个点之间测试了100万个图，由于篇幅限制，仅列举了72个图的染色结果，色数和边密度的变化曲线如图 2所示。

从图 2可以看出，色数随着边密度和点数的增大而增大。

通过对表 6~8的结果分析，可得到如下结论：

结论1 8个顶点以内的所有简单连通图都存在AVDEVTC。

结论2 对于简单图G，当3≤n≤8时，Δ+1≤χ_avdevtc(G)≤Δ+2。

结论3 结合图 2、表 6~8的测试结果，猜想1成立。

5) 运行时间计算。使用此算法对500~1 000个顶点的随机图进行了测试，由于篇幅所限，仅列举了边密度为0.1时运行部分单个图的运行时间(由于最终的染色矩阵要写进txt文件，所以程序运行时间略有延长)，点数为500、600、700、800、900、1 000的时间分别为16.225 s、19.382 s、121.025 s、135.116 s、320.026 s、420.359 s。同时测试了7个顶点以内的所有非同构图以及8个顶点的所有图，运行时间如表 9所示。可以得出，该算法能够在较短的时间内得到染色结果。

4 算法时间复杂度分析

依据算法步骤，影响算法时间复杂度的因素主要包括以下几点(n代表图G的点数)：

1) 生成随机图。算法用m与n的矩阵存储随机图，所以该步最坏的时间复杂度是：T₁(n)=O(n²)。

2) 给顶点染色。依据染色规则，每个顶点仅染色一次，因此点染色的时间复杂度是：T₂(n)=O(n)。

3) 边的预染色。此步骤的时间复杂度取决于边的个数，在最坏的情况下，边的个数为n阶完全图的个数，所以这一步最坏的时间复杂度是：T₃(n)=O(n²)。

4) 解决边染色冲突。依据arrsort[]数组中顶点的顺序逐步迭代交换，使得图中所有边的染色均达到正常，这一步最坏的时间复杂度为：T₄(n)=O(n³)。

5) 调整色集合冲突。通过调用preexchange()函数得到最佳的处理色集合冲突的交换方式，这一步最坏的时间复杂度为：T₅(n)=O(n³)。

6) 解决均匀染色问题，对于n个顶点的随机图G，令调整的最大次数为max，一般情况下max不超过n，则最坏复杂度为T₆(n)=O(max×n²)。

综合上述分析，本算法的时间复杂度为O(n³)。

5 结语

本文提出了一种启发式优化算法来解决新问题：即图的邻点可区别均匀V-全染色问题。算法设计了一个总目标函数和四个子目标函数来对应AVDEVTC的多个约束条件，在染色矩阵上通过每个点的颜色集合的迭代交换操作，使得每个子目标函数都达到最优，直到满足总目标函数的要求。本算法较以往的人工染色而言节约了大量的人力和时间成本，而且能够在很短的时间内正确得到人工染色所得不到的上百个顶点以上图的染色结果。利用该算法，可以快速地获得大量的研究数据，验证了G的邻点可区别均匀V-全染色的一些相关猜想，为G的邻点可区别均匀V-全染色其他的相关定理和猜想的证明提供了基础数据支持，未来将会继续实现算法来解决图G的相关可区别染色问题。