随机图的点可区别V-全染色算法

胡腾云，尹 波，代素敏，李敬文

兰州交通大学 电子与信息工程学院，兰州 730070

1 引言

图的染色问题一直是图论中的一个重要的研究课题，具有重要的理论和现实意义，组合优化、资源分配、交通运输等问题都可以转化为图的染色问题来解决。图染色问题起源于著名的“四色猜想”，20世纪初期，一些数学工作者着力于研究图的点染色、边染色，直到后来提出了点可区别正常边染色。1965年，M.Behzad和V.G.Vizing分别独立地提出了著名的全染色猜想[1-2]；2002年，张忠辅在点可区别正常边染色的基础上提出了图的邻强（点可区别）边染色[3]的概念和猜想，国内外专家也做了大量研究[4-9]；随后张忠辅等人又相继提出了邻点可区别全染色、点可区别全染色、距离为β的点可区别边染色、距离为β的点可区别全染色等概念和猜想[10-13]，受到了国内外的广泛关注。目前所获得的关于图的可区别染色的大部分结果都是针对特殊图的，如路、圈、星、扇、轮、完全二部图、树以及它们的联图等，但现实中的问题转换成图运用图染色方法解决时，面对的绝大多数都是随机图，本文设计了一种算法，能够求出2 000个点以内简单连通图的点可区别V-全色数，文中给出算法测试案例的详细执行步骤，并给出了部分图的点数、色数、边密度和平均度的曲线关系图。本文所研究的图为简单连通图，文中所用术语及符号参见文献[14]。

2 相关定义

定义1.1[15]对于阶数至少为2的简单连通图G，f是从V(G)∪E(G)到正整数集 {1，2，…，k}的映射，而C(u)={f(u)}∪{f(uv)|uv∈E(G)}称为点u的色集合，称为点u的色补集合，点u的度数记作d(u)。如果

（1）∀uv∈E(G)，有f(u)≠f(uv)，f(v)≠f(uv)；

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

（3）∀u，v∈V(G)，有C(u)≠C(v)。

则称f是图G的k点可区别V-全染色，简记为k-VDVTC（k-vertex-distinguishing V-total coloring），(G)=min{k|G存在k-VDVTC}为图G的点可区别V-全色数。

定义1.2[15]设G(V，E)是一个简单图，ni为V(G)中度为i的点的个数，称δ(G)≤i≤ Δ(G)}为G的组合全度，其中δ(G)和Δ(G)分别为G的最小度和最大度。

猜想[15]对于简单图G，有。

3 点可区别V-全染色算法

点可区别V-全染色必须满足条件如下：（1）相邻边染色不同；（2）顶点与其关联边染色不同；（3）所有点的色集合不同，由此三个条件可以构造出算法的约束函数。

3.1 构建点可区别V-全染色算法的目标函数

（1）边约束函数

相邻的边必须染不同的颜色。边约束函数定义如下：

其中两电平VSC的接地需求包括2个方面：(1)交流侧滤波器的接地需求；(2)直流侧电容的接地需求。由于VSC电平数少，采用高频脉宽调试方式，开关频率高，换流器出口将含有较大的高次谐波，需在变压器阀侧加装较小容量的高频谐波滤波器。VSC在直流线路上有集中电容，可采取电容中点直接接地或通过组件接地的方式，如图1所示。

（2）点边约束函数

（3）色集合约束函数

（4）总体目标函数

由上述三个染色条件的约束函数，给出总体目标函数：Yvdvtc=Yae+Yve+Yc。

3.2 点可区别V-全染色的算法步骤

算法：点可区别V-全染色算法

输入：给定图的邻接矩阵，或者给定图的顶点数。

算法步骤：

步骤1接收给定的邻接矩阵，或者接收图的点数n，生成n×n的空矩阵，由random（）随机地生成边的总个数，并将矩阵的主对角线上方的n×(n-1)/2位置上随机地放置1；若主对角线上方元素中的每一行或者每一列至少有一个1，则将主对角线下方元素对称补充完整，主对角线的元素全放置元素0，输出邻接矩阵，否则重新生成。

步骤2将图的邻接矩阵存储在color[][]中，计算各顶点的度d(vi)，并由组合全度定义计算所需要的色数k，并由random（）生成n组1到k之间的随机数对G的边预染色，保证对于顶点vi，color[i][i+1]至color[i][n]中的颜色互不相同，并且所取的颜色不是color[i][1]至color[i][i-1]中的任何一个。

步骤3检测顶点vi的度d(vi)与其色补集合中元素个数之和是否等于k，若则顺序检测下一个顶点，否则做如下检测：

①若f(uv)=f(uw)且，则令f(uv)=f(vu)=a1，修改，计算。

②若f(uv)=f(uw)且，则令f(uw)=f(wu)=b1，修改，计算。

③若f(uv)=f(uw)且则设，如果存在m∈{1，2，…，i}使得f(vp)=km且 ，则 令f(vp)=f(pv)=c1，f(uv)=km，并修改，计算；重复以上步骤直至。

步骤4检测度相同的顶点的色集合是否相同，若都不同则进入步骤5。

步骤5选择顶点染色，将各顶点按照其色补集合中的元素个数从小到大排序，设当前待染定点为{k1，k2，…，kx} ，依次取出一个元素km(m∈{1，2，…，x})给当前顶点染色，若存在顶点vj使得，说明顶点色集合相同，令m+1，否则令f(vi)=km；直至所有顶点染色完毕。

步骤6染色完成，判断结果集是否正确，若出现顶点色集合相同，将k增加1返回步骤2，否则输出正确结果。

4 点可区别V-全染色算法测试

本文选取9个点的图进行测试，其邻接矩阵如矩阵（1）所示：

详细染色步骤为：

（1）边预染色。由邻接矩阵可知，度为5、6、7、8的顶点个数分别为3、4、1、1，由全组合度猜想颜色数k=9。利用random（）函数产生9组1到9的随机数，根据染色规则对边预染色。边预染色结果如矩阵（2）所示：

（3）进入算法步骤4，检测度相同的顶点的色集合是否相同，由（2）中（i从1到9）可知，不存在顶点色集合冲突的情形，因此进入顶点染色的步骤。

（4）给顶点染色。将各顶点按照其色补集合中的元素个数从小到大排序，顺序依次为：v4，v2，v3，v5，v6，v9，v1，v7，v8按照步骤 5给顶点染色，染色结果如矩阵（4）所示：

Yvdvtc=Yae+Yve+Yc=0，染色成功。

由以上结果可知，k=9即，由于μT(G)=9，所以本结果符合点可区别V-全染色猜想：μT(G)≤χvvt(G)≤μT(G)+1。

本文从800以内的点数中选取了99个测试案例，测试环境：操作系统为Win7，内存为4 GB。在点可区别V-全染色中，点数、色数、边密度、平均度之间的关系如图1、2、3所示。

图1 点数、色数、边密度关系图

图2 点数、色数、边密度关系图

图3 点数、色数、平均度关系图

5 点可区别V-全染色算法复杂度分析

由于本算法采用的n×n邻接矩阵来存储顶点和边的颜色，所以算法步骤1和步骤2在生成图和边预染色方面算法的时间复杂度都为O(n2)；步骤3和步骤4调整色集合冲突，其最坏复杂度为O(n3)；步骤5给n个顶点染色，首先必须将顶点按其色补集合元素个数从小到大排序，其最坏时间复杂度为O(n2)，给顶点染色的时间复杂度为O(n)。综合分析，总算法的时间复杂度为T(n)=O(n3)。

6 结论

本文给出了针对随机图的点可区别V-全染色算法，该算法借助染色矩阵及色补集合逐步迭代交换以实现目标函数设定的目标。文中还对算法的时间复杂度进行了分析，其时间复杂度为T(n)=O(n3)，但该算法的空间复杂度较高，当图的顶点个数比较多时（超过2 000左右），测试出现问题，不能完成染色。本算法已经过大量测试，求出了8个点内（179 404 840个）和800个点内随机抽取的5亿个简单连通图的点可区别V-全色数，给出了点数、色数、边密度和平均度之间的关系曲线图（因画图限制，挑选了99个有代表性的图如图1、2），为进一步证明图的点可区别V-全染色猜想提供新思路。

[1]Vizing V G.On an estimate of the chromatic class of a p-graph（Russian）[J].Discret Analiz，1964，3：25-30.

[2]Behzad M.Graphs and their chromatic numbers[D].Michigan：Michigan State University，1965.

[3]Zhang Zhongfu，Liu Linzhong，Wang Jianfang.Adjacent strong edge coloring of graphs[J].Applied Mathematics Letters，2002，15（3）：623-626.

[4]Balister P N，Györi E，Lehel J，et al.Adjacent vertex distinguishing edge colorings[J].Discrete Math，2006，1（21）：237-250.

[5]Wang Weifan，Wang Yiqiao.Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree[J].Journal of Combinatorial Optimization，2008，19（4）：471-485.

[6]Hocquard H，Montassier M.Adjacent vertex-distinguishing edge coloring of graphs with maximum degree at least five[J].Electronic Notes in Discrete Mathematics，2011，38：457-462.

[7]Wang Weifan，Wang Yiqiao.Adjacent vertex-distinguishing edge colorings of K4-minor free graphs[J].Applied Mathematics Letters，2011，24（12）：2034-2037.

[8]Akbari S，Bidkhhori H，Nosratir N.Strong edge colorings of graphs[J].Discrete Mathetics，2006，306（23）：3005-3010.

[9]Hatami H.Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number[J].J Combin Theory：Series B，2005，95（2）：246-256.

[10]Zhang Zhongfu，Chen Xiangen，Li Jingwen et al.On adjacent vertex distinguishing total coloring of graphs[J].Science in China Ser A：Mathematics，2005，48（3）：289-299.

[11]Zhang Zhongfu，Qiu Pengxiang，Xu Baogen，et al.Vertex distinguishing total coloring of graphs[J].Ars Combinatoria，2008，87（2）：33-45.

[12]Zhang Zhongfu，Li Jingwen.D(β)-vertex distinguishing edge coloring of graphs[J].Journal of Mathematics，2006，49（3）：703-708.

[13]Zhang Zhongfu，Li Jingwen，Chen Xiangen，et al.D(β)-vertex distinguishing total coloring of graphs[J].Science in China Series A：Mathematics，2006，49（10）：1430-1440.

[14]Chen Xiangen，Gao Yuping，Yao Bing.Not necessarily proper total colorings which are adjacent vertex distinguishing[J].InternationalJournalofComputerMathematics，2013，90（11）：2298-2307.

[15]Bondy J A，Murty U S R.Graph theory with applications[M].New York：The Macmillan Press Ltd，1976.