欢迎来到天天文库
浏览记录
ID:53731093
大小:149.17 KB
页数:3页
时间:2020-04-20
《完全二叉树到星连通圈网络的嵌入.pdf》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、第26卷第3期甘肃科学学报Vo1.26NO.32014年6月Journa1ofGansuSciencesJun.20l4完全二又树到星连通圈网络的嵌入白亚兰,师海忠(西北师范大学数学与统计学院,甘肃兰州730070)摘要:依据对二叉树嵌入的研究,主要讨论了完全二叉树到星连通圈网络的嵌入,得出该嵌入的膨胀数为1,并且给出了完全二叉树嵌入星连通圈网络的构造算法.关键词:图的嵌入;互连网络;完全二叉树;星连通图网络中图分类号:O157.文献标志码:A文章编号:1004—0366(2O14)03—0007—0
2、3在互连网络中,一个结构能被另一个结构来模拟是重要的.网络模拟问题能归结为图的嵌入l1]问题.通过相关学者的研究,正则连通圈理论开始有了锥形并逐步完善起来,星连通圈是正则连通圈的特例,南于它是一类重要的互连网络,具有很多其他良f3,4231)(2,4231)3214)f2,1234)好的性质,从而受到很大的关注.我们给出了星连通图1高度为2的完全二叉树(4-SCC)网的一些基本性质,受到文献[2—5]的启发,总结出Fig.1Thecompletebinarytreewithaheightof2(4-S
3、CC)了完全二又树到星连通圈嵌入的一些结论及证.12345)明,以及完全二又树嵌入星连通圈网络的构造算法.1星连通圈的基本性质白星连通圈网络被提出后,由于它结构的特殊性,已有不少学者对星连通圈的各种性质作出探52341)(2,52:2;11)∽,:{2l1,5)(4I2345)讨ll7。。].星连通圈网络SCC是基于我们所熟知的星图2高度为2的完全二叉树(5-SCC)图.星连通圈网络的度为固定数3(r/≥4).”一3Fig.2Thecompletebinarytreewithaheightof2(5-
4、SCC)时,其容错度为1,当>3时,其容错度为2.星连通树可以嵌入到SCC中,该嵌入的膨胀数为1.圈网络是点对称,而且是点可迁的.证明T。相邻两点的表示对应6-SCC中相邻2完全二叉树到星连通圈网络的嵌入两点的表示,如图3所示.T。相邻两点的表示对应7-SCC中相邻两点的定理l当一4,5时,存在高度为2的完全二叉表示,如图4所示.树可以嵌入到SCC中,陔嵌入的膨胀数为1.定理3当一8,9时,存在高度为4的完全二叉证明T。相邻两点的表示对应4-SCC中相邻树可以嵌入到—SCC中,该嵌入的膨胀数为1.两点
5、的表示,如图1所示.证明丁I相邻两点的表示对应8-SCC中相邻T相邻两点的表示对应5-SCC中相邻两点的两点的表示,如图5所示.表示,如图2所示.T相邻两点的表示对应9-SCC中相邻两点的定理2当”一6,7时,存在高度为3的完全二叉表示,如图6所示.收稿日期:2O13一O917基金项目:甘肃省自然科学基金(ZS9c)1一A25—017G)作者简介:白亚兰(1990一),女,甘肃武威人,硕士研究生,主要研究方向为组合最优化.E—mail:baiyalan2008@163.com*通讯作者:E—mail:
6、shihaizhong@nwp_t1.edu.cn8甘肃科学学报2014年第3期(6,123456、23456)图3高度为3的完全二叉树(6scc)Fig·3ThecompletebinarYtreewithaheightof3f6.scc)7)234567)图4高度为3的完全二叉树(7.scc)Fjg·4ThecompletehinarYtreewithaheightof3f7.scc)f8.12345678(8,82345671)(3,1234567(3,823456711~,82345671)(
7、3,32145678)(4.12345678)。}//(4,82345671(2.28345.6(7,82345671、/‘舔踟’4)5(8.32145678\--/.12345678)(8.328~,71)\(4,4237.,5f~71)\(7,28.~567l;1)\(8,821~673)\(4,42l38)\(={,4231.~7(5,523418)’H471’辨)(828345671)(6.82345671)一(25)678)42s()78)_,.3214.4m图5高度为4的完全二叉树(8。s
8、cc)Fig·5ThecompletehinarYtreewithaheightof4f8scc)(9,123456789、图6高度为4的完全二叉树(9scc)Fjg·6ThecompletebinarYtreewithaheightof4f9.scc)以下给出一种构造完全二又树的算法,步骤个顶点如下:(3)因为星连通周的度为3(n≥4),即每~个(1)给定一顶点(,1234⋯”),并以它作为根.点的邻点有且仅有3个,故将第l层得到的2个顶点(2)从根(
此文档下载收益归作者所有