完全图强乘积的强半径和强直径_刘树洋.pdf

2 0 2 3年河北大学学报(自然科学版)2 0 2 3第4 3卷 第2期J o u r n a l o f H e b e i U n i v e r s i t y(N a t u r a l S c i e n c e E d i t i o n)V o l.4 3 N o.2D O I:1 0.3 9 6 9/j.i s s n.1 0 0 0 1 5 6 5.2 0 2 3.0 2.0 0 2完全图强乘积的强半径和强直径刘树洋 1,2,李峰1,2,阴浩然1(1.青海师范大学 计算机学院,青海 西宁 8 1 0 0 0 8;2.藏语智能信息处理及应用国家重点实验室,青海 西宁 8 1 0 0 0 8)摘 要:首先证明2个非平凡完全图强乘积是完全图且具有强定向性,然后确定了完全图强乘积的最小强半径和最小强直径的精确值,给出了最大强直径和最大强半径的范围.最后通过利用强乘积的结合性,将上述结论推广到多个完全图的强乘积.关键词:完全图;强乘积;强定向;强半径;强直径中图分类号:O 1 5 7.5 文献标志码:A 文章编号:1 0 0 0 1 5 6 5(2 0 2 3)0 2 0 1 2 1 0 6S t r o n g r a d i u s a n d s t r o n g d i a m e t e r o f s t r o n g p r o d u c t o f c o m p l e t e g r a p h sL I U S h u y a n g1,2,L I F e n g1,2,Y I N H a o r a n1(1.C o l l e g e o f C o m p u t e r S c i e n c e,Q i n g h a i N o r m a l U n i v e r s i t y,X i n i n g 8 1 0 0 0 8,C h i n a;2.T h e S t a t e K e y L a b o r a t o r y o f T i b e t a n I n t e l l i g e n t I n f o r m a t i o n P r o c e s s i n g a n d A p p l i c a t i o n,X i n i n g 8 1 0 0 0 8,C h i n a)A b s t r a c t:I t i s p r o v e d t h a t t h e s t r o n g p r o d u c t o f t w o n o n-t r i v i a l c o m p l e t e g r a p h s i s a c o m p l e t e g r a p h a n d h a s s t r o n g o r i e n t a t i o n.A n d t h e n t h e e x a c t v a l u e s o f t h e m i n i m u m s t r o n g r a d i u s a n d t h e m i n i m u m s t r o n g d i a m e t e r o f t h e s t r o n g p r o d u c t o f t h e c o m p l e t e g r a p h a r e d e t e r m i n e d,a n d t h e r a n g e s o f t h e m a x i m u m s t r o n g d i a m e t e r a n d t h e m a x i m u m s t r o n g r a d i u s a r e a l s o g i v e n.B e s i d e s,t h e a b o v e c o n c l u s i o n i s e x t e n d e d t o s t r o n g p r o d u c t s o f m u l t i p l e c o m p l e t e g r a p h s.K e y w o r d s:c o m p l e t e g r a p h;s t r o n g p r o d u c t;s t r o n g o r i e n t a t i o n;s t r o n g r a d i u s;s t r o n g d i a m e t e r强乘积作为4种标准乘积之一,在互连网络设计中有着广泛的运用.其概念是S a b i d u s s i1于1 9 5 9年首次提出.对于2个图G1和G2的强乘积用G1G2表示.顶点集V(G1G2)=(x,y)xV(G1),yV(G2),2个不同的顶点(x1,y1)和(x2,y2)(其中x1,x2V(G1),y1,y2V(G2)相邻当且仅当x1=x2 且y1,y2E(G2)或者y1=y2 且x1,x2E(G1)或者x1,x2E(G1)且y1,y2E(G2),并且将G1和G2称为强乘积图G1G2的因子图.现在关于强乘积性质的研究非常多,如独立控制数2、W i e n e r指数3-4等.其他3种标准乘积也是图论中重要的研究方向,相关研究结果可见文献5-6.1 预备知识1个图G是指1个有序二元组(V(G),E(G),其中V(G)是非空的顶点集,E(G)是边集.本文考虑的 收稿日期:2 0 2 2 0 4 2 5 基金项目:国家自然科学基金资助项目(1 1 5 5 1 0 0 2);青海省自然科学基金资助项目(2 0 1 9-Z J-7 0 9 3)第一作者:刘树洋(1 9 9 7),男,江西抚州人,青海师范大学在读硕士研究生,主要从事组合网络理论及优化方向研究.E-m a i l:l i u s h u y a n g 2 0 2 11 6 3.c o m 通信作者:李峰(1 9 8 1),男,安徽芜湖人,青海师范大学教授,博士,博士生导师,主要从事图与网络优化设计方向研究.E-m a i l:l i 2 0 0 6 3 6 91 2 6.c o mG 均为简单无向图,即没有自环和重杆.有向图D同样是指1个有序的二元组,V(D)是非空的顶点集,A(D)是弧集.若有向图D中存在有向路u v,则称在 D中从顶点u出发可达到顶点v,如果这2个顶点在D中同时互相可达,就称其相互可达.若D中的任意2个顶点都相互可达,则称D是强有向图.若D的基础图G是1个简单图,则D是G的1个强定向图,并且表示G具有强定向性.强定向是图论中一个重要的研究方向.L a d i n e k等7做了有关强乘积的强定向研究,其他图的强定向研究见文献8-1 2.近年来,单纯基于无向图的计算机网络已经不能满足现在计算机网络的发展需求,更多需要的是有向图和无向图结合的复杂网络.那么直径、半径等图参数不适合衡量有向图拓扑结构的优良,需要1个结合无向和有向图的图参数来衡量网络结构的优良.C h a r t r a n d等1 3在强定向图的基础上提出了强距离的概念.设G是一个二边连通图,D是G的一个强定向.顶点u和顶点v之间的强距离为D中包含该2点的最小强有向子图的弧的数目,用s d(u,v)来表示.类似无向图中的离心率等概念,强定向图D中顶点v的强离心率、强半径、强直径的概念如下:s e(v)=m a xs d(v,x)xV(D),s r a d(D)=m i ns e(v)vV(D),s d i a m(D)=m a xs e(v)vV(D).后来在强距离的概念的基础上,针对简单连通无向图,定义了G的最小强半径s r a d(G)、最大强半径S R AD(G)、最小强直径s d i a m(G)、最大强直径S D I AM(G)4个参数,其中D(G)是指G的所有强定向构成的集合.现将4个参数的定义整理如下:s r a d(G)=m i ns r a d(D)DD(G),S R AD(G)=m a xs r a d(D)DD(G),s d i a m(G)=m i ns d i a m(D)DD(G),S D I AM(G)=m a xs d i a m(D)DD(G).目前关于乘积图的强距离问题的结果十分丰富,黄怡1 4给出了路与路笛卡尔乘积的最小强半径和最大强直径.张果香1 5给出了路与路强乘积的最小强半径.C h e n等1 6-1 7得出了完全图的笛卡尔乘积的最大强半径和最大强直径,并进一步给出了笛卡尔乘积图最小强半径与其因子图半径的关系.本文研究的强乘积图的因子图都是完全图.由于强乘积的连接方式,所得到的强乘积图同样是完全图,并进一步确定出完全图强乘积的最小强半径和最小强直径.此外根据强乘积图与因子图的顶点关系,得到了完全图的强乘积的最大强直径以及最大强半径的范围.2 主要结果和证明并不是所有的简单无向图都具有强定向性,例如树(不存在圈的无向简单图)、路、单星图等.只有当判断出1个图G具有强定向性时本文的研究才有意义.下面给出强乘积边连通度定理和著名的R o b b i n s定理,并得到关于强乘积的强定向定理.引理11 8令Gi是非平凡连通图,顶点数vi,边数ei,最小度i(i=1,2),G1和G2的强乘积图G1G2的连通度的边连通度(G1G2)=m i n1(v2+2e2),2(v1+2e1),1+2+12,其中,为图的边连通度,v为顶点数,e为边数,为最小度.引理21 91个无向图G具有强定向性当且仅当G是二边连通图.定理1若G1和G2分别为m阶和n阶非平凡连通简单图,则强乘积图G1G2具有强定向性.证明:设G1和G2分别为m阶和n阶非平凡连通简单图,那么由引理1知当G1和G2的边连通度、顶点数、边数、最小度都最小时,强乘积图G1G2的边连通度最小,即G1=G2=K2时最小,代入引理1,得(G1G2)(K2K2)=32.221河北大学学报(自然科学版)第4 3卷第2期刘树洋等:完全图强乘积的强半径和强直径再结合引理2,得到强乘积图G1G2具有强定向性.上面的定理1已经给了研究强乘积的强半径、强直径的基础.下面给出关于有向完全图强乘积的定理并推广到多个有向完全图.定理2若Km和Kn分别是m阶和n阶完全有向图,则强乘积图G1G2是m n阶完全有向图Km n.证明:设(x1,y1)和(x2,y2)是强乘积有向图 G1G2 中的任意2顶点,其中x1,x2V(Km),y1,y2V(Kn).由于Km和Kn为完全有向图,则有x1=x2 或(x1,x2)E(Km)y1=y2 或(y1,y2)E(Kn)x1=x2,y1=y2或x1=x2,(y1,y2)E(Kn)或y1=y2,(x1,x2)E(Km)或(x1,x2)E(Km),(y1,y2)E(Kn)|(x1,y1)=(x2,y2),或(x1,y1),(x2,y2)E(KmKn),这说明强乘积有向图KmKn中的任意2个顶点相同或者相邻,即为完全有向图.由强乘积有向图的顶点公式可知,V(KmKn)=V(Km)V(Kn),定理得证.同理上述结果对无向图也同样成立,见图1.图1 2个3阶完全图的强乘积K3K3=K9F i g.1 S t r o n g p r o d u c t o f t w o c o m p l e t e g r a p h s o f o r d e r 3 K3K3=K9定理3若G1,G2,Gn分别是v1,v2,vn阶简单完全图,则G1G2Gn是v1v2vn阶完全有向图Kv1 v2vn.证明:对n2做归纳.当n=2 时,由定理2知结论成立.假设2kn,G2G3Gk=Kv2v3vn,再根据归纳假设,有G1G2Gk=Kv1 v2vn.定理3给了研究强乘积图的基础,可以发现通过强乘积得到的强乘积图,既保留了一些特殊图的性质,又多了新的性质.下面给出完全图强乘积的最小强半径和最小强直径.引理32 0若G为n阶完全图,则当n4时,s r a d(G)=