【摘要】 Efe提出的交叉立方体(crossedcube)是超立方体(hypercube)的一种变型,其某些性质优于超立方体,比如其直径几乎是超立方体的一半.在高性能的并行计算机系统中,信息是通过若干条结点互不交叉的路径并行传输,并且网络中的结点和链路出错是不可避免的,因此这些路径的长度将直接影响并行计算的性能.本文对交叉立方体的内顶点互不交叉路径进行了研究,证明了以下结论:在n维交叉立方体CQn中任意两顶点u,v间存在n条内顶点互不交叉的路径,使得(1)最短路的长度=u和v之间的距离,(2)所有路中的最长路径长度≤u和v的距离+4.这说明交叉立方体互连网络具有很好的并行通信性能和容错性能.更多还原

【Abstract】 The crossed cube proposed by Efe is a variation of hypercube, but some properties of the former are superior to those of the latter. For example, the diameter of the crossed cube is approximately half that of the hypercube. The messages are simultaneously transmitted on some internally vertex-disjoint paths in the high performance parallel computing system, and the failures of nodes or links are inevitable, thus the lengths of those paths directly affect the performance of parallel computing. We prove the conclusion that for any pair of vertexes in an n-dimensional crossed cube CQn, there exist n internally vertex-disjoint paths, such that (1) the length of the shortest path= the distance of the pair vertexes, (2) the length of each path ≤the distance of the pair vertexes+4. Therefore, the interconnection network of crossed cube has high performance of communication and fault tolerance.更多还原