超级扭立方体互连网络及其性质  

THE SUPER TWISTED CUBE INTERCONNECTION NETWORKS AND THEIR PROPERTIES

作　　者：王喜[1] 樊建席[1] 

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006

出　　处：《计算机应用与软件》2011年第10期17-19,106,共4页Computer Applications and Software

基　　金：国家自然科学基金(60873047)

摘　　要：扭立方体是超立方体的一类变体,它具有比超立方体更好的性质。但是,同超立方体一样,它也是具有2n个顶点的n-正则图,故要使一个扭立方体的维数(即顶点度数)增加1(称为升级),就必须成倍地增加扭立方体中的顶点个数。为了解决这一问题,将具有2n个顶点的扭立方体的拓扑结构加以改变,得到了包含任意多个顶点的互连网络——超级扭立方体(STN)。证明了超级扭立方体保持了扭立方体的最高连通度、对数级的直径和顶点度数、Hamilton性质、连通度级的tp-可诊断度等方面的优良性质,更进一步地,由于它包含了任意多个顶点,所以对它的升级只需增加任意多个顶点,从而克服了扭立方体的升级必须成倍增加其顶点个数的缺点。The Twisted Cube is a hypercube variant.It has some superior properties to the hypercube.However,like the hypercube,it is also an n-regular graph with 2n nodes.In order to increase 1 dimension（i.e.upgrade one level）,the nodes of the Twisted Cube must be multiplied.In order to solve the problem,the topological structure of the Twisted Cube with 2n nodes is modified to create an interconnection network——the Super Twisted Cube（STN）,which contains an arbitrary number of nodes.It is proven that the STN maintains the greatest connectivity,numerical diameter node numbers,Hamilton property,connectivity level tp-diagnostic properties of the Twisted Cube.Moreover,since it contains an arbitrary number of nodes,it only needs to add an arbitrary number of nodes to upgrade.Therefore it overcomes the above mentioned drawback of having to multiply its nodes to upgrade the Twisted Cube.

关 键 词：扭立方体 超级扭立方体 升级 连通度 可诊断性 HAMILTON性质 直径 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]