交换超立方体的拓扑性质与嵌入问题研究  

Research on Topological Properties and Embedding Issues of the Exchanged Hypercube

作　　者：王新阳[1] 梁家荣[1] 豆秋丽[1] 

机构地区：[1]广西大学计算机与电子信息学院,广西南宁530004

出　　处：《电子学报》2012年第4期669-673,共5页Acta Electronica Sinica

基　　金：国家自然科学基金(No.61064002);教育部"新世纪优秀人才支持计划"专项(No.NCET-06-0756)

摘　　要：交换超立方体(Exchanged hypercube)作为超立方体的一种变型网络,降低了网络规模增大时所需要的拓扑连接的开销.本文根据交换超立方体的图形化定义,得到交换超立方体的公式化定义,证明了交换超立方部分子网与超立方网同构,提出EHS(s,t)和EHT(s,t)的概念,并在此概念的基础上证明了交换超立方体中只存在长度不小于4的偶数圈,证明了交换超立方体的顶点连通度和边连通度都为min{s+1,t+1}.为使交换超立方体具有更广阔的应用范围,本文还提出了超立方体在交换立方网中的三种嵌入策略,证明了n=s+t+1时,n-1维超立方体Qn-1能够同胚地嵌入到交换超立方体EH(s,t)中.As a new variant of the hypercube,the exchanged hypercube reduces the cost of topology connecting when the scale of networks increases.According to the graphic definition of Exchanged Hypercube,in this paper,we obtain its formulized definition,prove that the subgraphs of exchanged hypercube are isomorphic to hypercubes,propose the concepts of EHS（s,t） and EHT（s,t）,and on the basis of these concepts,prove that there are only even circles with length no more than 4,and that the vertex connectivity and edge connectivity of exchanged hypercube are both min{s＋1,t＋1}.To enlarge the application range of the exchanged hypercube,we put forwards three strategies embedding hypercubes into exchanged hypercubes as well,and prove that,when n=s＋t＋1,Qn-1 can be embedded into the exchanged hypercube EH（s,t） homeomorphically.

关 键 词：互联网络 交换超立方体 超立方体 连通度 同构 同胚 嵌入 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]