随机图的点魔幻全染色算法

宋 晨, 李敬文, 张荞君

(兰州交通大学电子与信息工程学院, 兰州 730070)

图染色问题一直是图论[1]中的一个经典课题,许多学者围绕它进行了一系列的研究和探索.近年来,信息技术的蓬勃发展有力地推动了图论的进步,许多新的概念被相继提出,如点可区别全染色[2-3],边魔幻全标号以及点魔幻边染色等等．

基于上述所提到的点魔幻标号[13]和点可区别染色[14]等概念,本文提出了一种全新的染色——点魔幻全染色.通过借鉴点魔幻边染色算法的核心思想并结合文献[15],设计出一种新型的点魔幻全染色算法,得到了14个点以内的路图、星图、扇图、友谊图、风筝图以及这些特殊图组合得到的联图的结果,最后通过对实验结果的分析,总结出若干定理及证明．

1 基本概念

定义2设圈图Cm的顶点集为{u1,u2,…,um},星图Sn的顶点集为{w0,w1,…,wn}.如果Cm和Sn有中心节点,分别用u1和w0表示,其中w0表示星心,Cm↑Sn表示将Sn的星心w0连接到Cm的任意一个顶点后得到的图,则有V(Cm↑Sn)=V(Cm)∪V(Sn),E(Cm↑Sn)=E(Cm)∪E(Sn),|V(Cm↑Sn)|=|V(Cm)|+|V(Sn)|-|w0|,|E(Cm↑Sn)|=|E(Cm)|+|E(Sn)|．

图1为顶点数为m的圈图Cm和星图Sn连接得到的联图Cm↑Sn(m≥4,n≥2且m-n=2)的示例．

图1 Cm↑SnFig.1 Cm↑Sn

定义3风筝图(Kite):(n,t)-K是圈图Cn中任意顶点与长度为t的路图Pt端点相连接的图,示例如图2所示．

图2 (n,t)-KFig.2 (n,t)-K

定义4n个C3组成的图称为友谊图,记为T(2,n)(n≥2),示例如图3所示．

图3 T(2,n)Fig.3 T(2,n)

2 VMTC算法

根据点魔幻全染色的定义,本文提出了VMTC算法,先预处理输入的邻接矩阵,然后通过调整函数逐步破坏平衡,再利用平衡函数进行判断并建立新的平衡,慢慢趋向最优解,完成对图的染色过程．

2.1 函数设计

1) 预处理函数process()

① 输入图的邻接矩阵．

② 计算出图G(p,q)的点数p,边数q,每个点的度degree以及最大度数maximumdegree．

③ 从邻接矩阵右上角三角形开始,对点数和边数逐个增加,并且保证色数要连续．

④ 使色和要接近最大度的色和或者等于,若不满足,则返回第③步．

⑤ 输出预处理后的邻接矩阵．

2) 调整函数adjustment2()

① 读取预处理后的图的邻接矩阵．

② 计算此时图G(p,q)的点数p,边数q,各个点的色和数sum．

③ 从右上角三角形开始,从左到右,从上到下依次进行调整,每次增加1,且满足色和数差值小于等于1．

④ 判断色数是否连续,若是,则执行下一函数,否则循环第③步．

3) 平衡函数balance()

① 判断所有点色和是否相同,若是执行下一个函数,否则回到调整函数adjustment2()．

4) 输出函数output()

① 判断是否到达最大色数．

② 若达到,且满足平衡函数balance(),则具有点魔幻全染色.若未达到,则循环调整函数adjustment2()与平衡函数balance(),在循环后达到最大色数.但不满足平衡函数balance()时,则判定此图不具有点魔幻全染色．

③ 输出符合的平衡矩阵．

2.2 函数流程

预处理过程流程图如图4所示．

图4 预处理过程Fig.4 Pretreatment process

VMTC算法总流程如下．

Input:图G(p,q)的邻接矩阵

Output:满足VMTC的图的邻接矩阵

Begin

1) 先预处理,读取处理后的邻接矩阵AdjaMatrix

2) getp,q,degree,maximumdegree

3) calculate sum

4) for(i=min;i

5) while(点色数不连续)

6) if(色数值差大于1 || 所有点色和不同)

7) Adjustment2(AdjaMatrix)

8) else

9) Output(BalanceMatrix)

10) end if

11) end while

12) end for

13) 输出最终满足点魔幻全染色的邻接矩阵AdjaMatrix

14) end

2.3 算法结果

结果统计条形图如图5至图8所示,展示了6个点到9个点不同边数的图总数中点魔幻全染色图数的情况,其中蓝色表示各个点相对应边数的非同构图的总数量,灰黄色表示相应具有点魔幻全染色图的数量．

图5 六个点统计图Fig.5 Six vertex statistical graph

图6 七个点统计图Fig.6 Seven vertex statistical graph

图7 八个点统计图Fig.7 Eight vertex statistical graph

图8 九个点统计图Fig.8 Nine vertex statistical graph

图9给出了部分图的点魔幻全染色示例．

图9 点魔幻全染色示例Fig.9 VMTC example

3 定理及证明

定理1对于路图Pn(n≥3),有

χVMTC(Pn)=n+1(n≥3).

(1)

证明设路图的点集V(Pn)={v1,v2,v3,…,vn},对点进行染色:

f(v1)=n+1;

f(vn)=n;

f(vi)=(n-i)+1 (2≤i

对边进行染色:f(v1v2)=1;

f(vn-1vn)=2;

f(vivi+1)=[(i+1)+[1+

(-1)i]/2]/2 (2≤i≤n-2).

对v1求色和Sum(v1)=n+1+1=n+2,对vn求色和Sum(vn)=n+2,对路图中i=2,3,…,n-1的任意一个顶点求色和Sum(vi)=(n-i)+1+[i+[1+(-1)i-1]/2+i+1+[1+[1+(-1)i]/2]/2]/2．

当i≡0(mod 2)时,Sum(vi)=(n-i)+1+(i+i+1+1)/2=n+2．

当i≡1(mod 2)时,Sum(vi)=(n-i)+1+(i+1+i+1+0)/2=n+2．

即

Sum(vi)=n+2.

(2)

因此,Sum(v1)=Sum(vi)=Sum(vn)=n+2,路图中所有顶点的色和相同,满足点魔幻全染色,有χVMTC(Pn)=n+1 (n≥3),证毕．

定理2对于星图Sn(n≤3),当n≤3时有χVMTC(Sn)=n(n+1)/2;当n≥4时不存在χVMTC(Sn)．

证明设星图的点集V(Sn)={v0,v1,v2,v3,…,vn},对点进行染色:

f(v0)=1;

f(v1)=n(n+1)/2;

f(vi)=f(v1)=(i-1)=n(n+1)/2-i+1.

对边进行染色:

f(v0vi)=i(i=1,2,3).

对v0求色和Sum(v0)=1+n+n(n-1)/2=1+(n2+n)/2,对v1求色和Sum(v1)=1+n(n+1)/2=1+(n2+n)/2,对v2求色和Sum(v2)=2+n(n+1)/2-2+1=1+(n2+n)/2,对v3求色和Sum(v3)=3+n(n+1)/2-3+1=1+(n2+n)/2.因此,Sum(v0)=Sum(v1)=Sum(v2)=Sum(v3)=1+(n2+n)/2,星图中所有顶点的色和相同,满足点魔幻全染色,有χVMTC(Sn)=n(n+1)/2 (n≤3).当n≥4时,无论如何对点和边进行染色,都会出现色数不连续或所有点色和不相同的情况,无法满足点魔幻全染色的定义,因此找不到满足点魔幻全染色的星图,χVMTC(Sn)不存在,证毕.

定理3对于扇图Fn(n≥3),有

(3)

证明设扇图的点集V(Fn)={v0,v1,v2,v3,…,vn},对扇图分奇偶性进行讨论.

情况1当n≡0(mod 2)时,

对点进行染色:f(u0)=n+1;

f(u1)=n;

f(ui)=n-(i-1) (2≤i≤n-1);

f(un)=n/2+1.

对边进行染色:f(u0ui)=1 (i=1,2,3,…,n);

f(u1u2)=n;

f(u2u3)=1.

对u0求色和Sum(u0)=n+1+n=2n+1,对u1求色和Sum(u1)=n+1+n=2n+1,对un求色和Sum(un)=n/2+1+1+n+(i-1)/2,又因为i=n-1,所以Sum(un)=n/2+1+1+n+(n-2)/2=2n+1.对扇图中i=2,3,…,n-1的任意一个顶点求色和Sum(ui)．

当i≡1(mod 2)时,Sum(ui)=1+n-(i-1)+n+(i-1)/2+1+(i-1-2)/2=2n+1;

当i≡0(mod 2)时,Sum(ui)=1+n-(i-1)+1+(i-2)/2+n+(i-1-1)/2=2n+1.

即

Sum(ui)=2n+1.

(4)

因此,Sum(u0)=Sum(u1)=Sum(un)=Sum(ui)=2n+1,扇图中所有顶点的色和相同,满足点魔幻全染色,有χVMTC(Fn)=(3n-2)/2,证毕．

情况2当n≡1(mod 2)时,

对点进行染色:f(u0)=n+1;

f(u1)=n;

f(ui)=n-(i-1) (2≤i≤n-1);

f(un)=5+[(n-1)/2-1]×3.

对边进行染色:f(u0ui)=1 (i=1,2,3,…,n);

f(u1u2)=n;

f(u2u3)=1;

对u0求色和Sum(u0)=n+1+n=2n+1,对u1求色和Sum(u1)=n+1+n=2n+1,对un求色和Sum(un)=1+5+3×[(n-1)/2-1]+1+(i-2)/2,因为i=n-1,所以Sum(un)=2n+1.同理,对ui求色和,按照奇偶性进行讨论,可得Sum(ui)=2n+1．

因此,Sum(u0)=Sum(u1)=Sum(un)=Sum(ui)=2n+1,扇图中所有顶点的色和相同,满足点魔幻全染色,有χVMTC(Fn)=(3n+1)/2,证毕.

定理4对于友谊图T(2,n)=2n(n≥2),有

χVMTC(T(2,n))=2n(n≥2).

(5)

证明设友谊图的点集为V=V(T(2,n))={v0,v1,v2,v3,…,v2n},对点进行染色:

f(v0)=2;

f(v1)=2n;

f(vi)=2n-(i-1)/2 (2≤i≤2n).

对边进行染色:f(v0vi)=1 (i=1,2,3,…,2n);

f(vivi+1)=(i+1)/2 (i=1,3,5,…,2n-1).

对v0求色和Sum(v0)=2+2n,对友谊图中i=2,3,…,2n的任意一个顶点求色和Sum(vi)=1+(i+1)/2+2n-(i-1)/2．

当i≡1(mod 2)时,Sum(vi)=2n+1+(i+1)/2-(i-1)/2=2n+2;

当i≡0(mod 2)时,Sum(vi)=2n+2.

即

Sum(vi)=2n+2.

(6)

因此,Sum(v0)=Sum(vi)=2n+2,友谊图中所有顶点的色和相同,满足点魔幻全染色,有χVMTC(T(2,n))=2n,证毕．

如图10所示,为n=4,5,6时,满足VMTC的友谊图部分染色结果．

图10 友谊图示例Fig.10 Friendship graoh example

定理5对于联图Cm↑Sn(m≥4,n≥2且m-n=2),有

χVMTC(Cm↑Sn)=m(m≥4,n≥2且m-n=2).

(7)

证明设联图点集V=V(Cm)∪V(Sn)={u1,u2,…,um,w0,w1,…,wn},其中u1=w0,对点进行染色:

f(v1/w0)=1;

f(u2)=2;

f(u3)=1 (m≥5);

f(um)=m-1;

f(um-1)=3 (m≥5);

f(um-2)=1 (m≥7);

f(ui)=m-i(4≤i

f(um-3)=[(m-2)+[1+(-1)m-3]/2]/2(m≥9);

f(wi)=m(1≤i≤n).

对边进行染色:f(u1u2)=1;

f(u1um)=1;

f(w0wi)=1 (i=1,2,…,n);

f(u2u3)=n;

f(u3u4)=2;

f(uiui+1)=[(i+1)+[1+(-1)i]/2]/2

(m-5≤i≤m-4且m≥8);

f(um-2um-1)=n-1 (m≥6);

f(um-3um-2)=3 (m≥7);

f(um-1um)=1.

对u1求色和Sum(u1)=3+n,对u2求色和Sum(u2)=1+2+n=n+3,对w3求色和Sum(w3)=1+m,因为m-n=2所以Sum(w3)=n+3,对um求色和Sum(um)=1+1+m-1=n+3,对ui求色和Sum(ui)=m-i+[(2i+1)+[1+(-1)i]/2+[1+(-1)i-1]/2]/2．

当i≡0(mod 2)时,Sum(ui)=m-i+(2i+1+1)/2=m-i+i+1=m+1=n+3;

当i≡1(mod 2)时,Sum(ui)=m+1=n+3.

即

Sum(ui)=n+3.

(8)

因此,Sum(u1)=Sum(u2)=Sum(w3)=Sum(um)=Sum(ui)=n+3,联图中所有顶点的色和相同,满足点魔幻全染色,有χVMTC(Cm↑Sn)=m,证毕．

如图11所示为m=6,n=4;m=8,n=6;m=9,n=7时,满足VMTC的联图部分染色结果．

图11 满足VMTC联图示例Fig.11 Linkage graph satisfies VMTC example

定理6对于风筝图(n,t)-K(n≥4,t≥3且n-t=1),有

χVMTC(n,t)-K=n(n≥4,t≥3且n-t=1).

(9)

证明设(n,t)-K点集为V=V(Cn)∪V(Pt)={u1,u2,…,un,v1,v2,…,vt},其中u1=v1,对点进行染色:

f(u1/v1)=t;

f(v2)=t;

f(vt)=n;

f(vi)=(t-i)+2 (2≤i≤t-2);

f(vt-1)=[(n+1)+[1+(-1)n]/2]/2;

f(u2)=3;

f(un)=n;

f(ui)=i+[1+(-1)i]/2 (2≤i≤n-1).

对边进行染色:f(u1u2)=f(u1un)=f(un-1un)=1;

f(vt-1vt)=2;

f(vivi+1)=[(i+1)+[1+(-1)i]/2]/2

(1≤i≤t-2).

当n≡0(mod 2)时,f(vivi+1)=[(i+1)+[1+(-1)i]/2]/2 (1≤i≤t-2);

当n≡0(mod 2)时,

f(uiui+1)=

当n≡1(mod 2)时,

f(uiui+1)=

对u1求色和Sum(u1)=1+1+1+t=3+t,对un求色和Sum(un)=n+1+1=t+3,对vt求色和Sum(vt)=n+2=t+3．

对ui求色和Sum(ui),分四种情形进行讨论．

情形1当n≡0(mod 2)且i≡1(mod 2)时,Sum(ui)=i+[1+(-1)i]/2+1+n-(i-1)=n+2,又因为n=t+1,所以Sum(ui)=t+3．

情形2当n≡0(mod 2)且i≡0(mod 2)时,Sum(ui)=i+[1+(-1)i]/2+n-i+1=n+1+1=t+3.

情形3当n≡1(mod 2)且i≡0(mod 2)时,Sum(ui)=i+[1+(-1)i]/2+n-i+1=n+1+1=t+3．

情形4当n≡1(mod 2)且i≡1(mod 2)时,

Sum(ui)=i+[1+(-1)i]/2+1+n-i+1=
n+2=t+3．

即

Sum(ui)=t+3.

(10)

对un-1求色和Sum(un-1),对其分奇偶性讨论．

当n≡1(mod 2)时,Sum(un-1)=1+1+i+[1+(-1)i]/2=1+1+n-1+(1+1)/2=n+2=t+3．

当n≡0(mod 2)时,Sum(un-1)=1+i+[1+(-1)i]/2+n-i=n+1+[1+(-1)i]/2=n+2=t+3．

即

Sum(un-1)=t+3.

(11)

对vi求色和Sum(vi),对其分奇偶性讨论．

当i≡0(mod 2)时,Sum(vi)=(t-i)+2+[(i+1)+[1+(-1)i]/2]/2+[i+[1+(-1)i-1]/2]/2=t-i+2+(2i+1+1-1)i]/2]/2+[i+[1+(-1)i-1]/2]/2=t-i+2+(2i+1+1+0)/2=t-i+2+t+1=t+3．

当i≡1(mod 2)时,Sum(vi)=t+3．

即

Sum(vi)=t+3.

(12)

因此,Sum(u1)=Sum(un)=Sum(vt)=Sum(ui)=Sum(un-1)=Sum(vi)=t+3,风筝图中所有顶点的色和相同,满足点魔幻全染色,有χVMTC(n,t)-K=n,证毕．

如图12所示,为n=4,t=3;n=5,t=4;n=7,t=6时,满足VMTC的风筝图部分染色结果．

图12 满足VMTC的风筝图Fig.12 Kite graph satisfies VMTC

4 结语

本文在已有的点魔幻标号和点可区别染色研究基础之上,提出了图的点魔幻全染色新概念,针对该染色设计了一种新的VMTC算法,该算法对路、星、扇等特殊图以及随机图的染色进行研究,给出了6个定理及证明.从算法效率看,VMTC算法可快速完成一些点数较小的图集染色,但当顶点数较大时仍然会花费较多的时间.从算法结果看,目前只是对特殊图和一小部分联图进行了结果分析,关于其他随机图的点魔幻全染色还需要进一步研究,希望各位读者在以后能给予改进．