完全二叉树到星连通圈网络的嵌入.pdf

《完全二叉树到星连通圈网络的嵌入.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)从根(