完全图强乘积的强半径和强直径_刘树洋.pdf
《完全图强乘积的强半径和强直径_刘树洋.pdf》由会员分享,可在线阅读,更多相关《完全图强乘积的强半径和强直径_刘树洋.pdf(6页珍藏版)》请在咨信网上搜索。
1、 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
2、 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
3、 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
4、 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
5、 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
6、 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
7、 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)或者y
8、1=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、 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中同时互相可达,
10、就称其相互可达.若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
11、的一个强定向.顶点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的所有强定向构成的集合
12、.现将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得出了完全图的笛卡尔乘积的最大强半径和最大强直径,并进一步给出了笛卡尔乘积图最小强半径与其因子图半径的关系.本文研究的强乘积图的
13、因子图都是完全图.由于强乘积的连接方式,所得到的强乘积图同样是完全图,并进一步确定出完全图强乘积的最小强半径和最小强直径.此外根据强乘积图与因子图的顶点关系,得到了完全图的强乘积的最大强直径以及最大强半径的范围.2 主要结果和证明并不是所有的简单无向图都具有强定向性,例如树(不存在圈的无向简单图)、路、单星图等.只有当判断出1个图G具有强定向性时本文的研究才有意义.下面给出强乘积边连通度定理和著名的R o b b i n s定理,并得到关于强乘积的强定向定理.引理11 8令Gi是非平凡连通图,顶点数vi,边数ei,最小度i(i=1,2),G1和G2的强乘积图G1G2的连通度的边连通度(G1G2
14、)=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,得到强乘积
15、图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,
16、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是v1
17、v2vn阶完全有向图Kv1 v2vn.证明:对n2做归纳.当n=2 时,由定理2知结论成立.假设2kn,G2G3Gk=Kv2v3vn,再根据归纳假设,有G1G2Gk=Kv1 v2vn.定理3给了研究强乘积图的基础,可以发现通过强乘积得到的强乘积图,既保留了一些特殊图的性质,又多了新的性质.下面给出完全图强乘积的最小强半径和最小强直径.引理32 0若G为n阶完全图,则当n4时,s r a d(G)=s d i a m(G)=3,当n=4时,s r a d(G)=3,s d i a m(G)=4.定理4若G1和G2分别为m阶和n阶非平凡完全图Km和Kn,强乘积图KmKn的最小强半径和最小强直径如下
18、:1)s r a d(KmKn)=3;2)s d i a m(KmKn)=3,m n4,4,m n=4.证明:由定理2知,2个完全图的强乘积图KmKn是完全图.结合引理3,得s r a d(KmKn)=3,s d i a m(KmKn)=3,m n4,4,m n=4.定理5若G1,G2,Gn分别为v1,v2,vn阶非平凡完全图,则强乘积图G1G2Gn的最小强半径和最小强直径:1)s r a d(G1G2Gn)=3;3212)s d i a m(G1G2Gn)=3,v1v2vn4,4,v1v2vn=4.下面介绍一个新的概念:线图.设G=(V,E)是一个不存在孤点的简单无向图,先将G的边变成顶点,
19、然后使G中任意2条变成顶点的边e1和e2相连,当其在G中有相同的端点,得到的新图就是G的线图,可以用L(G)表示并且容易得V(L(G)=E(G).通过线图的概念,显然可得星图的线图就是完全图,如图2所示.结合以上定理,还可以得到关于线图强乘积的最小强半径和最小强直径.图2 4阶的星图G及其线图L(G)=K3F i g.2 S t a r g r a p h G o f o r d e r 4 a n d i t s l i n e g r a p h L(G)=K3推论1当G1和G2分别为m阶和n阶(m2,n2)的星图,L(G1)、L(G2)为其线图,则2星图的线图如下:1)s r a d(L
20、(G1)L(G2)=s r a d(Km n-m-n+1)=3;2)s d i a m(L(G1)L(G2)=s d i a m(Km n-m-n+1)=3,m n-m-n+14,4,m n-m-n+1=4.证明:设G1和G2是顶点数不小于3的星图,则由星图和线图的定义得V(L(G1)=E(G1)=V1-1,即L(G1)是顶点数为V1-1的完全图,同理L(G2)是顶点数为V2-1 的完全图,代入定理2得:s r a d(L(G1)L(G2)=s r a d(Km n-m-n+1)=3;s d i a m(L(G1)L(G2)=s d i a m(Km n-m-n+1)=3,m n-m-n+14
21、,4,m n-m-n+1=4.推论2 若G1,G2,Gn分别是顶点数为v1,v2,vn的星图,L(G1),L(G2),L(Gn)为其线图:1)s r a d(L(G1)L(G2)L(Gn)=s r a d(Kni=1(vi-1)=3;2)s d i a m(L(G1)L(G2)L(Gn)=s d i a m(Kni=1(vi-1)=3,ni=1(vi-1)4,4,ni=1(vi-1)=4.关于完全图强乘积的最小强半径和最小强直径的相关结果已经给出,现在给出强距离参数中另外2个参数:最大强半径和最大强直径.引理42 1对于任意的二边连通图G,有s r a d(G)s d i a m(G)S D
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完全 乘积 半径 直径 刘树洋
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。