若干联图的邻点和可约边染色_罗榕.pdf

第5 7卷第2期华中师范大学学报(自然科学版)V o l.5 7 N o.22 0 2 3年4月J OUR NA LO FC E N T R A LCH I NANO RMA LUN I V E R S I T Y(N a t.S c i.)A p r.2 0 2 3收稿日期:2 0 2 1-1 1-0 9.基金项目:国家自然科学基金项目(1 1 9 6 1 0 4 1,6 2 0 6 2 0 4 9,1 1 4 6 1 0 3 8).*通信联系人.E-m a i l:l i j i n g w e n 2 8 1 6 3.c o m.D O I:1 0.1 9 6 0 3/j.c n k i.1 0 0 0-1 1 9 0.2 0 2 3.0 2.0 0 3文章编号:1 0 0 0-1 1 9 0(2 0 2 3)0 2-0 2 0 1-0 7若干联图的邻点和可约边染色罗 榕,李敬文*,张树成,张荞君(兰州交通大学电子与信息工程学院,兰州7 3 0 0 7 0)摘 要:该文在已有的图染色概念基础之上,结合实际问题提出了邻点和可约边染色的新概念,设计了一种新型的邻点和可约边染色(a d j a c e n tv e r t e xs u mr e d u c i b l ee d g ec o l o r i n g,AV S R E C)算法,该算法采用迭代寻优方式针对有限点内的所有非同构图集进行求解,通过实验结果分析,总结得到了若干联图的定理并给出证明.关键词:联图;邻点和可约边染色;邻点和可约边色数;算法中图分类号:T P 3 0 1.5文献标志码:A开放科学(资源服务)标志码(O S I D):图染色问题向来是图论中的热门研究课题,染色问题在近年来有很多方面的应用,学者们在传统染色的基础上提出了可区别染色以及可约染色等新型染色概念1-9.B u r r i s1在1 9 9 3年提出了满足正常边染色的基础上要求任意两点的色集合不同的点可区别边染色的概念,又和S c h e l p在1 9 9 7年提出了点可区别边染色的相关猜想2.2 0 0 2年,张忠辅教授等提出了在正常边染色的基础上满足任意相邻点的色集合均不同的邻点可区别边染色5,后来Z h u等进一步研究和探讨了可区别染色1 0.2 0 0 6年,张忠辅等1 1提出了距离不大于的点可区别边染色的概念,又在2 0 0 9年在可区别染色的理论基础上提出了一系列图的可约染色概念1 2.后 来 开 启 图 的 色 和 可 区 别 染 色 研 究 先 河 的 是C h a r t r a n d1 3,定义是要求任意两点及其关联边的色和不同.F l a n d r i n等1 4在邻和可区别边染色的基础上提出了邻和可区别边染色猜想.P i l s n i a k等在2 0 1 5年的文献中提出了图的邻和可区别全染色的概念及猜想1 5.本文在上述提到的染色概念基础上提出邻点和可约边染色新概念,通过借鉴传统的遗传算法、蚁群算法、模拟退火算法等随机搜索的智能算法设计思路,设计一种新型的邻点和可约边染色(a d j a c e n tv e r t e xs u m r e d u c i b l ee d g ec o l o r i n g,AV S R E C)算法,得到了有 限 点 以 内 的 路 图、圈图、星图以及 这些 特 殊 图 组 合 得 到 的 联 图 的 结果.最后对实验结果进行分析,给出若干定理及证明.1基础知识本文主要研究随机图的邻点和可约边染色,涉及的图G(V,E)均表示具有p个顶点,q条边的简单无向连通图,d(x)表示点x的度,d(x,y)表示点x和点y之间的距离.定义1 设G(V,E)是一个简单图,若存在正整数k(1k|E|)和映射f:E(G)1,2,k,使得对任意两点u,vV(G),当d(u)=d(v)且u,vE(G)时,有S(u)=S(v),其中S(u)=u vE(G)f(u v),则称f为G的邻点和可约边染色,且a v s r(G)=m a xk|k-A V S R E C o fG为邻点和可约边色数.显然a v s r(G)是存在的.定义2 设Gn的顶点集为u1,u2,un,Hm的顶点集为v1,v2,vm.如果图Gn有中心节点,则用u1表示.GnHm表示将Gn的非中心顶点连接 到Hm的 任 意 一 个 顶 点 后 得 到 的 图,记 为GnHm.V(GnHm)=V(Gn)V(Hm),E(GnHm)=E(Gn)E(Hm)u1v1,|E(GnHm)|=|E(Gn)|+|E(Hm)|.如 图1(a)所示.定义3 设Gn的顶点集为u1,u2,un,Hm的顶点集为v1,v2,vm.如果图Gn和Hm有中心节点,则用u1或v1表示.GnHm表示将Gn的中心节点u1连接到Hm的任意一个 顶点后得到 的图,记 为GnHm.V(GnHm)=V(Gn)2 0 2 华中师范大学学报(自然科学版)第5 7卷V(Hm),E(GnHm)=E(Gn)E(Hm)u1v1,E(GnHm)=|E(Gn)|+|E(Hm)|.如图1(b)所示.图1 GnHm图与GnHm图F i g.1 GnHmg r a p ha n dGnHmg r a p h 定义4 设星图Sm的点集为V=w0,w1,wm,Gn的顶点集为u1,u2,un.SmGn表示将星图中除星心外的m个节点都连接一个Gn后得到的图.|V(SmGn)|=|V(Sm)|+|V(Gn)|-m,|E(SmGn)|=|E(Sm)|+|E(Gn)|.如图2(a)所示.图2 SmGn图与(n,t)-K图F i g.2 SmGng r a p ha n d(n,t)-Kg r a p h 定义56 风筝图(K i t e):(n,t)-K是包含一个顶点数为n的圈图Cn和长度为t路图Pt组成的图.如图2(b)所示.引理1 对于简单图G,当a v s r(G)=k存在而a v s r(G)=k+1不存在时,图G的点和可约边色数即为k.证明 根据定义1,此引理显然成立.2 A V S R E C算法2.1 A V S R E C算法基本原理AV S R E C算法是根据邻点和可约边染色的定义,通过调整函数依次破坏平衡,再通过平衡函数建立平衡的迭代方式,逐步地趋向最优解,来完成对图的染色.主要过程如下:1)预处理函数:输入图G(p,q)的邻接矩阵进行预处理.计算图G(p,q)中的边数、度序列、当前图的最大度,以及根据两点相邻划分的分类集合.2)染色开始前准备三个预备函数:平衡函数,调整函数,连续函数,设置一个中间矩阵A d j u s t.3)从矩阵上三角的第一个不为0的边色数开始染色,当染色完满足调整函数或者不满足连续函数,需要将上一次染色的边数的色数恢复到刚才的状态,从下一条边开始染,当分类集合中满足相邻的同度点满足平衡函数时,就用中间矩阵A d j u s t记录一下这个矩阵.当染色过程中出现最大色数等于边数并且此时矩阵处于平衡状态时,输出这个平衡的矩阵A d j u s t.4)当矩阵中的所有边数都不能增加色数的时候,输出那个中间的平衡矩阵A d j u s t.这个A d j u s t就是我们求得的邻点和可约边染色矩阵.2.2伪代码I n p u t:图G(p,q)的邻接矩阵MO u t P u t:满 足 邻 点 和 可 约 边 染 色 图 的 邻 接矩阵b e g i n根据M求出图G的距离矩阵M1,初始化一个记录矩阵R e c o r d M a t r i xw h i l e(G中的边没有全部染色完成)f o r i0t one i+i f(e i增加色数后不满足邻点和可约边染色条 第2期罗 榕等:若干联图的邻点和可约边染色2 0 3 件)e i-e n di fi f(M1满足平衡函数i sB a l a n c e)R e c o r d M a t r i xM1e n di fi f(M1满足平衡函数i sB a l a n c e且最大染色数k等于边数)输出平衡矩阵R e c o r d M a t r i xe n d f o re n d w h i l e输出最终满足 邻点和可区别边染色的邻接矩阵R e c o r d M a t r i xe n d2.3图3是A V S R E C算法得到的风筝图(4,4)-K的染色结果示例图3(4,4)-K示例F i g.3(4,4)-Ke x a m p l e3定理及证明定理1 设Pn是n(n2)顶点的一条路,有a v s r(Pn)=1,n=2;2,n3.定理2 设Sn是n+1(n2)顶点的星图,有a v s r(Sn)=n;定理3 设Cn是n(n3)顶点的圈图,有a v s r(Cn)=1,n1(m o d2);2,n0(m o d2).根据邻点和可约边染色的定义,即要保证距离小于等于1的同度点色数和相同,且色数集合连续,上述定理显然成立.定理4 对于风筝图(n,t)-K(n3,t3),设(n,t)-K图点集为V=V(Cn)V(Pt)=u1,u2,un,v1,v2,vm,其 中u1=v1.存 在a v s r(n,t)-K)=4.1)证明 a v s r(n,t)-K)满足f染色,f(u1un)=2,n0(m o d2);4,n1(m o d2).f(uiui+1)=2,i0(m o d2);4,i1(m o d2),i=1,2,n-1;f(vivi+1)=1,i1(m o d2);3,i0(m o d2),i=1,2,m-1.证得a v s r(n,t)-K)4,已知(n,t)-K有1个最大度顶点,n+t-3个2度顶点,1个1度顶点,根据AV S R E C定义,Cn、Pt中所有2度顶点色和必须各自相同.根据染色基本定理和k-A V S R E C定义可知,(n,t)-K图最多可染4种不同色.假设1-v s r(n,t)-K)5时,令任意一条边染色数为5,都会存在定义距离内同度顶点色和不同;如f(u2u3)=5,此时存在2个2度顶点u2,u3与n-3个2度顶点的色和不同,与假设矛盾.故根据引理1,a v s r(n,t)-K)=4.2)如图4所示为(n,t)-K图的部分染色示例.图4(n,t)-K的染色F i g.4(n,t)-Ke x a m p l e2 0 4 华中师范大学学报(自然科学版)第5 7卷定理5 对于联图(n,t)-KPm(n3,t3,m3),设(n,t)-K图点集为V=V(Cn)V(Pt)=u1,u2,un,v1,v2,vt,Pm的 点集为V=w1,w2,wm,其中,u1=v1=w1.存在a v s r(n,t)-KPm)=6.1)证明 联图(n,t)-KPm满足f染色,f(u1un)=4,n1(m o d2);2,n0(m o d2),f(uiui+1)=4,i1(m o d2);2,i0(m o d2),i=1,2,n-1;f(vivi+1)=1,i1(m o d2);3,i0(m o d2),i=1,2,t-1;f(wiwi+1)=5,i1(m o d2);6,i0(m o d2),i=1,2,m-1.证得a v s r(n,t)-KPm)6.已知(n,t)-KPm存在1个最大度顶点,m+n+t-5个2度顶点,2个1度顶点.根据k-A V S R E C定义,Cn、Pt、Pm中所有2度顶点色和必须各自相同.根据染色基本定理和k-A V S R E C定义可知,(n,t)-KPm图中最多可染6种不同色.假设a v s r(n,t)-KPm)7时,令任意一条边染色数为7,都会存在定义距离内同度顶点色和不同;如f(w2w3)=7,此时存在2个2度顶点w2,w3与m-4个2度顶点的色和不同,与假设矛盾.故根据引理1,a v s r(n,t)-KPm)=6.2)如图5所示为(n,t)-KPm图的部分染色示例.图5(n,t)-KPm的染色F i g.5(n,t)-KPme x a m p l e 定理6 对于联图(n,t)-KFm(