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

扭立方体是超立方体的一类变体,它具有比超立方体更好的性质。但是,同超立方体一样,它也是具有2n个顶点的n-正则图,故要使一个扭立方体的维数(即顶点度数)增加1(称为升级),就必须成倍地增加扭立方体中的顶点个数。为了解决这一问题,将具有2n个顶点的扭立方体的拓扑结构加以改变,得到了包含任意多个顶点的互连网络——超级扭立方体(STN)。证明了超级扭立方体保持了扭立方体的最高连通度、对数级的直径和顶点度数、Hamilton性质、连通度级的tp-可诊断度等方面的优良性质,更进一步地,由于它包含了任意多个顶点,所以对它的升级只需增加任意多个顶点,从而克服了扭立方体的升级必须成倍增加其顶点个数的缺点。     

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

局部扭立方体是近年来提出的超立方体的一个变型,由于它的许多优越性质(如低直径),在并行处理领域越来越受到人们的重视.然而,像超立方体一样,它也有一个缺点,即要使局部扭立方体升级,就必须成倍地增加其顶点个数.为了解决这一问题,文中将顶点个数为2的次幂的局部扭立方体推广到具有任意个顶点的互连网络,提出了超级局部扭立方体(SLTC)的定义,并证明它保持了局部扭立方体的最高连通度、对数级的直径和顶点度数、Hamilton性质等方面的优良性质,从而证明了超级局部扭立方体是既保持了局部扭立方体的多种优越性质又易于升级的互连网络.     

LHL-立方体互连网络及其性质

并行计算系统一直是计算机科学中的重要研究领域,其互连网络的拓扑性质对整个网络的性能起着非常重要的作用.目前已经提出多种互连网络,其中超立方体具有对数级的直径、高连通度、对称性等很好的性质,故被用作多种并行机的处理器连接的拓扑结构.然而,超立方体并非所有性质都是最优的互连网络,且超立方体的许多变型结构具有许多比超立方体更好的性质,其中已经证明了局部扭立方体在直径、Hamilton连通性等方面都优于超立方体.给出在超立方体与局部扭立方体的顶点间的一种连接方式--超连接,从而得到一种称为LHL-立方体的新型网络,并对这种网络的以下性质进行了研究:顶点连通度、边连通度、Hamilton连通性、直径.研究结果表明,一个n维LHL-立方体是一个具有2n个顶点和n2n-1条边的n-正则图,n维LHL-立方体的顶点连通度和边连通度均为n,且是Hamilton连通的,直径上界为[n/2 ]+3.     

超级交叉立方体互连网络及其拓扑性质

交叉立方体是近年提出的超立方体的一种变种。由于它的许多优越性质（如直径、嵌入性等）,在并行处理领域越来越受到人们的重视。然而,像超立方体一样,它也有一个缺点,即要使交叉立方体升级,就必须成倍地增加其顶点个数。为了解决这一问题,本文将顶点个数的２的次幂的交叉立方体推广到具有任意个顶点的互连网络,提出了超级交叉立方体的定义,并证明它保持了交叉立方体在高速通度、对数级的直径和顶点度数等方面的优良性质,从     

局部扭立方体环互连网络及其性质

优化网络的拓扑结构是互连网络研究的重要研究方向。局部扭立方体（locally twisted cube,LTQn ）是对超立方体（hypercube,Qn ）互连网络的优化变种,然而当对LTQn 升级时,需要成倍地增加网络的节点,这不利于LTQn的应用和发展。为了克服LTQn 这一缺陷,提出了一种新的互连网络拓扑结构：局部扭立方体环互连网络（locally twisted cube-connected ring interconnect network,LRN）,给出了LRN的定义及其拓扑结构,并研究了LRN的网络直径、连接度、汉密尔顿连通性、泛圈性、路由等问题,证明了LRN是一种易于升级又具有LTQn 许多优良性质的层次环互连网络（hierarchical ring interconnection networks,HRN）。     

扭立方体连接网络结构的研究与分析

根据交叉立方体（CQn）的结构与关联对的概念,对扭立方体连接网络（TNn）的结构特性进行了分析,证明了当[n5]时,TNn是不连通的,并且不连通的结点数占整个网络结点数的一半。通过分析扭立方体连接网络的错误所在,提出了一种新型网络结构——扭交叉立方体（TCQn）,证明了该网络结构是完全连通的,初步研究了其基本网络性质,如正则性,连通度,容错度,递归性等,表明TCQn具有与CQn同样优秀的网络性质。     

交叉立方体互联网络的容错性研究

提出了交叉立方体网络的局部连通性和限制容错度概念,讨论了n维交叉立方体的局部k维子立方体连通性和局部子立方体连通性。利用这些结果,可以大大提高交叉立方体网络的容错能力。     

一种新的交叉立方体最短路径路由算法

Efe提出的交叉立方体(crossed cube)是超立方体(hypercube)的一种变型.交叉立方体的某些性质优于超立方体,比如其直径几乎是超立方体的一半.Efe提出了时间复杂度为O(n2)的交叉立方体最短路径路由算法.Chang等人扩展了Efe的算法,时间复杂度为O(n),它在路由的每一步有更多条边作为最短路径可供寻路选择.但这些边并没有包含全部可进行最短路径路由的边.文中给出了结点各边可进行最短路径路由的充要条件,并在此基础上提出了一种时间复杂度为O(n2)的交叉立方体最短路径路由算法,它在路由的每一步都将所有的最短路径边作为候选边.理论分析和实例表明它可输出任意一条最短路径.     

交叉立方体中嵌入超立方体的研究

Efe提出的交叉立方体(crossedcube)是超立方体(hypercube)的一种变型。但是,交叉立方体的某些性质却优于超立方体,其直径几乎是超立方体的一半。在本文中,研究了用交叉立方体互连网络来模拟超立方体互连网络,其实质是图嵌入问题,得出了以下结论:当n≤2,2n维交叉立方体CQ2n可同构嵌入两个n 1维立方体Qn 1。当n≥3,2n维交叉立方体CQ2n可同胚嵌入n 1维超立方体Qn 1。     

局部扭立方体网络中网络嵌入问题的研究

局部扭立方体网络LTQ_n(Locally Twisted Cube)作为超立方体网络Q_n(Hypercube)的优化变种网络,具有很多优良的特性。依据局部扭立方体网络的性质及图嵌入的理论提出二项树、交换超立方体网络和超立方体网络嵌入到局部扭立方体网络的方案,并严格证明了这几种嵌入映射的扩张率、拥塞度及负载等都是最小的,这说明了局部扭立方体网络具有很好的通用性。     

BC互连网络及其性质

提出一种称为一一对应连接（BC）图的互连网络族，使其包含超立方体、交叉立方体和Mobius立方体作为基具子集，同时又使其具有与超立方体、交叉立立体和Mobius立方体相同的对数级的直径和顶点度数、最高连通（容错）度和相同的可诊断性等性质，从而使对超立方体及与其结构相似的大量互连网络的某些性质的研究合而为一，证明了BC互连网络族中包含一类Hamilton连通图并给出了BC互连网族中的图的直径的一个猜想。     

交叉立方体内顶点不交叉路径长度的研究

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

基于局部扭曲立方体的多播路由算法

局部扭曲立方体是一种新提出来用于并行计算的互联网络。经研究发现,局部扭曲立方体中已有最小路由算法存在着死锁。因此,在原有算法的基础上,提出了一种新的无死锁路由算法并给出了无死锁证明。利用将物理通道分成两条虚拟通道进而形成两个不相交的虚拟网络,将不同的点对之间的路由限定在某一个虚拟网络中,从而有效地避免了死锁的产生。同时,利用一个局部扭曲立方体可由两个低维子立文体和2-扭曲立方体构成这一性质,在局部的低维子立方体和2-扭曲立方体中均采用自适应路由,从而提高了算法的自适应性。在此基础上提出了一种多播路由算法。     

HCH-立方体的Hamilton连通性

新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究。超立方体及其变型——交叉立方体具有优点,也具有缺点。文献[1]给出了在超立方体与交叉立方体的顶点之间的一种连接——超连接,从而得到了一种称为HCH-立方体的互连网络,文章证明了当n≥4,HCH-立方体任意两个顶点之间存在Hamilton路径,即HCH-立方体是Hamilton连通的,而超立方体不是Hamilton连通的。这表明HCH-立方体具备了交叉立方体在Hamilton连通性方面的性质。文章还给出了在n维HCH-立方体中构造任意两个顶点之间Hamilton路径的算法,该算法的时间复杂度为O(N),其中N=2n,为n维HCH-立方体的顶点个数。