交叉立方体圈嵌入的一个新算法

交叉立方体互联网络有不少独特的性质。已经证明当n≥3时n维交叉立方体Dn是Hamilton连通的，一个将长度l,(4≤l≤2^n）的圈以扩张1嵌入Dn的O（llogl）算法。本文利用交叉立方体的Hamilton连通性给出了一个将长度l,4≤l≤2^n的圈以扩张1嵌入Dn的新的算法也被给出，其时间复杂度为O(l）。     

立方形递归网络中的Hamilton圈

立方形递归网络是一类具有良好拓扑性质的互连网络模型.运用立方形递归网络结构的递归性,证明了立方形递归网络存在Hamilton圈,同时给出了立方形递归网络中构造Hamilton圈的方法.     

折叠交叉立方体的3-额外边连通度

g-额外边连通度是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且g是非负整数,如果G中存在某种边子集使得G删除这种边子集后得到的图不连通,且每个分支至少有g+1个点,则所有这种边子集中基数最小的边子集的基数称为图G的g-额外边连通度,记作λg(G).由定义可知,λ0(G)=λ(G)且λ1(G)是图G的超边...     

关于加强超立方体互连网络的可诊断性的另一种证明方法

ｎ维加强超立方体是具有２＾ｎ个顶点，（ｎ＋１）２＾ｎ－１－正则图，它是通过对ｎ维超立方体增加２＾ｎ－１条边得到的。在「１」中证明了基于ＰＣＭ模型的ｎ维加强超立方体在精确诊断策略征是（ｎ＋１）－可诊断的，在悲观诊断策略下是（２ｎ）／（２ｎ）－可的，但在证明很繁琐。     

扭立方体连接网络的结构

提出了一种由３维扭立方体生成的新的互连网络－扭立方体连接网络,它是超立方体的一个变种,主要讨论它的递归结构及其子图的邻接关系。     

交叉立方体与其超图的逻辑等价性

交叉立方体是超立方体的一个变种,具有良好的图参数、拓扑性质和结构递归性.应用交叉立方体的代数表示法研究交叉立方体子图的邻接关系,并根据子图间的邻接关系研究交叉立方体与其某类超图在结构上的逻辑等价性.研究结果表明,交叉立方体是可重构性和容错性皆佳的网络.     

交叉超立方体网络的边泛圈性

作为超立方体Qn的变型，在点数和边数都相同的情况下，交叉超立方体CQn有比超立方体更好的性质．在已获证明的CQn包含所有长度(从4到2^n)的圈的基础上，进一步改进了这一结果，证明了CQn中每条边落在所有长度(从4到2^n)的圈中．     

超立方体网络的限制边连通性

m-限制边割将连通图分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图的m-限制边连通度.本文给出了n立方体的m-限制边连通度的表达式,由此推出：当m≤2（n/2）-1或m=2 k≤2n-1（k为任意正整数）时,超立方体Qn是极大m-限制边连通的.     

折叠交叉立方体的1-好邻诊断度

诊断度是多处理器系统互连网络能够诊断的最大故障结点的个数,它是度量多处理器系统故障诊断能力的一个重要参数.2012年,Peng等提出了一种新的诊断方法g-好邻诊断度,它要求每个非故障顶点至少有g个非故障邻点.n-维折叠交叉立方体网络FCQ_n是由交叉立方体网络CQ_n增加2^n-1条边后所得.该文利用1-好邻诊断度作为评价可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,得到折叠交叉立方体网络的1-好邻诊断度.证明了在PMC模型与MM^*模型下FCQ_n的1-好邻诊断度分别等于2n+1,n≥5和2n+1,n≥6.     

基于超立方体与交叉立方体的交叉连接的HC-立方体网络

给出了在超立方体与交叉立方体的顶点之间的一种连接——交叉连接,从而得到一种称为HC-立方体的新型网络,证明了HC-立方体不仅保持了超立方体和交叉立方体的低顶点度数和高连通度的优点,而且其直径至多比交叉立方体大2的性质;它克服了超立方体对圈模拟能力的不足。由于这种网络同时包含了超立方体和交叉立方体作为子网络,因此它既能实现超立方体的功能,又能实现交叉立方体的功能。     

交换折叠超立方体的连通度

P.K.K.Loh等人从超立方体Qn中系统地移除了一些边后获得了交换超立方体EH(s,t)。李等人在EH(s,t)的基础上增加了一些边获得了一个新的互联网络交换折叠超立方体EH(s,t)。连通度是衡量网络容错性的一个重要参数,并且连通度越大网络越可靠。本文证明了EH(s,t)的连通度等于其最小度。     

规则互连多处理器系统的容错性分析

多处理器系统中的互连网络为处理器之间相互通信提供了一种有效的机制,是决定系统性能的重要因素之一.互连网络的容错性可以用互连网络中设备出现故障时,网络保持正常工作的概率来刻画.笔者用概率方法对4种规则互连多处理器系统(超立方体,交叉立方体,M(o)bius立方体,局部扭曲立方体)的容错性进行了分析.通过仿真试验,得到结论:基于超立方体或其变体结构的多计算机系统均具有较好的容错性,其中,交叉立方体具有最好的容错性.     

HCH-立方体在比较模型下的可诊断性

新型并行处理系统的研制依赖于对新的互连网络的结构和它们的性质的研究,超立方体和交叉立方体是流行的互连网络,它们都有优点也有缺点.对由超立方体和交叉立方体构成的HCH-互连网络的可诊断性进行了研究,证明了当n≥4时,n维HCH-立方体互连网络在比较模型下的可诊断性为n,与超立方体和交叉立方体在比较模型下的可诊断性相同.     

有向树图的连通性及其算法

证明了树形图图的连通性，给出了求全部树形图的广探算法。     

交换折叠交叉立方体的连通度和超连通度

交叉立方体CQn和交换交叉立方体ECQ(s，t)是计算机系统里常用的2个拓扑结构.CQn中系统地移除了一些边后，获得了交换交叉立方体ECQ(s，t).在ECQ(s，t)的基础上增加了一些边，就获得了一个新的互连网络交换折叠交叉立方体EFCQ(s，t).连通度和超连通度是衡量互连网络可靠性和容错性的2个重要参数.证明了EFCQ(s，t)的连通度和超连通度分别等于其最小度和最小边度.     

基于交叉立方体环连接的Petersen图互联网络研究

利用环的简单扩展性以及Petersen图的短直径与交叉立方体节点的高可连接性,提出了一种新型互联网络RCP(n),并对其性质进行了一些研究,证明了RCP(n)网络不但具有正则性以及良好的可扩展性,同时还具有比Qn,HP(n),RHP(n)网络更短的直径和更小的构造开销。     

构造幻立方的一种方法

将“拉丁方”的概念拓广的“拉丁体”在此基础上给出了利用３个拉丁体构造ｎ阶幻方方的一种方法,其中ｎ不被２,３,５整除。     

扭立方体连接网络的几乎泛圈性

扭立方体连接网络是超立方体的一个变种,它是由扭立方体生成的一种新的互连网络结构·根据扭立方体连接网络的结构特点,证明了扭立方体连接网络的几乎泛圈性·这一结论说明关于线性阵列和环上的运算均可在扭立方体连接网络上实现·     

k连通［s,t］图的Hamiltion连通性

若图G的任意个s顶点的导出子图至少有t条边,则称图G为[s,t]图．[s,t]图的概念可视为图的独立数概念的推广．本文证明：若图G是k连通[k＋1,2]（k≥2）图,则G或者是Hamilton连通的或者同构于Kk∨Gk．由此可以推出,若图G的阶是n（n≥3）,α（G）≤κ（G）－1,则G是Hamilton连通的．