交叉立方体连通圈网络的Hamilton分解

交叉立方体连通圈网络CQCC(n)(n≥3)是一类典型的互连网络,它是3正则的.在2010年,师海忠提出如下猜想:CQCC(n)(n≥3)是Hamilton可分解的.也就是说,交叉立方体连通圈网络CQCC(n)(n≥3)可分解为边不交的一个Hamilton圈和一个完美对集的并.在这篇文章中,证明了当n=3;4;5;6时猜想成立,即交叉立方体连通圈网络CQCC(n)(n=3;4;5;6)可分解为边不交的一个Hamilton圈和一个完美对集的并。

交叉立方体圈嵌入的一个新算法(英文)

交叉立方体互联网络有不少独特的性质。已经证明当3n时n维交叉立方体nD是Hamilton连通的,一个将长度)24(,nll的圈以扩张1嵌入nD的)log(llO算法。本文利用交叉立方体的Hamilton连通性给出了一个将长度nll24,的圈以扩张1嵌入nD的新的算法也被给出,其时间复杂度为)(lO。

交叉扭立方体互联网络及其性质

扭N立方体是近年来提出的一种新型变体网络结构.通过X-变换操作使得存在2n个顶点的超立方体的网络直径从N减少到N-1,减少了网络规模增大时所需要的网络开销,从而受到了广泛的欢迎.与超立方体一样,扭N立方体也存在缺点,如果增加扭N立方体的维数,会成倍增加扭N立方体的顶点个数.为了解决这一问题,本文通过扭N立方体的结构,提出了交叉扭立方体的定义,并给出了相应的拓扑结构网络图,证明了交叉扭立方体的部分子网与超立方体网络同构,同时研究了交叉扭立方体的网络直径、连通度等问题.通过上述拓扑结构的基本性质的研究,得到了交叉扭立方体的性能优于扭N立方体的重要结论.

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

g-外边连通度是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且g是非负整数,如果G中存在某种边子集使得G删除这种边子集后得到的图不连通并且每个分支至少有g+1个点,则所有这种边子集中基数最小的边子集的基数称为图G的g-外边连通度,记作λ_(g)(G).由定义可知λ_(0)(G)=λ(G)并且λ_(1)(G)是图G的超边连通度.n维折叠交叉立方体FCQ_(n)是由交叉立方体CQ_(n)增加2^(n-1)条边后所得.证明了λ_(2)(FCQ_(n))=3n-1,n≥5.

交叉立方体的限制性连通度（英文）

G是一个图,h是一个正整数,一个图G的h-限制性连通度是使得G删除G中的某个点集使得G不连通且每个分支中点的度数至少是h的最小点集的基数.交叉立方体网络是超立方体的一个变形,在平行计算系统当中交叉立方体是最重要的网络之一.该文证明了n维交叉立方体2-和3-限制性连通度分别是4n-8(n≥4)和8n-24(n≥5).

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

g-额外边连通度是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且g是非负整数,如果G中存在某种边子集使得G删除这种边子集后得到的图不连通,且每个分支至少有g+1个点,则所有这种边子集中基数最小的边子集的基数称为图G的g-额外边连通度,记作λ_(g)(G).由定义可知,λ_(0)(G)=λ(G)且λ_(1)(G)是图G的超边连通度,n-维折叠交叉立方体FCQ_(n)是由交叉立方体CQ_(n)增加2^(n-1)条边后所得.因此,证明λ_(3)(FCQ_(n))=4n-4,n≥5;分析说明对折叠交叉立方体互连网络的可靠性评价时,3-额外边连通度较之经典的边连通度更具优势性.

折叠交叉立方体的分支连通度

r-分支连通度(边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且r是非负整数,如果G中存在某种点子集(边子集)使得G删除这种点子集(边子集)后得到的图至少有r个连通分支.则所有这种点子集(边子集)中基数最小的点子集(边子集)的基数称为图G的r-分支连通度(边连通度),记作cκr(G)(cλr(G)).n-维折叠交叉立方体FCQn是由交叉立方体CQn增加2n-1条边后所得.这篇文章确定了折叠交叉立方体FCQn的r-分支连通度,其中r=2,3.

折叠交叉立方体的限制连通度

限制性连通度作为评估互联网络容错性的最佳参数之一,在多处理器系统中对可靠性计算起着重要作用.给定一个连通图G=(V,E)和一个非负整数h,子集F■V(G)(F■E(G))(如果存在)称为h-限制点割(h-限制边割),如果G-F不连通,并且G-F中的每个连通分支至少有h+1个顶点,其中最小的h-限制点割(h-限制边割)的基数称为图G的h-限制连通度(h-限制边连通度),记为κ_(h)(G)(λ_(h)(G)).本文确定了h=2时n-维折叠交叉立方体FCQ_(n)的κ_(h)(G)和λ_(h)(G).

折叠交叉立方体的分支边连通度

r-分支连通度(边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且r是非负整数,如果G中存在某种点子集(边子集)使得G删除这种点子集(边子集)后得到的图至少有r个连通分支.则所有这种点子集(边子集)中基数最小的点子集(边子集)的基数称为图G的r分支连通度(边连通度).n-维折叠交叉立方体FCQn是由交叉立方体CQn增加2^(n−1)条边后所得.该文利用r-分支边连通度作为可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,得到了折叠交叉立方体网络的2-分支边连通度,3-分支边连通度,4-分支边连通度.确定了折叠交叉立方体FCQn的r-分支边连通度.

折叠交叉立方体的2-限制性边通度

h-限制性边连通度是衡量大型互连网络可靠性和容错性的一个重要参数。设G是连通图且h是非负整数,如果G中存在某种边子集,使得G删除这种边子集后得到的图不连通并且每个分支中点的度至少是h,则所有这种边子集中基数最小的边子集的基数称为图G的h-限制性边连通度。n-维折叠交叉立方体是由n-维交叉立方体增加一些补边后所得。对于此类问题,首先利用2-限制性边连通度作为可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,然后得到折叠交叉立方体的2-限制性边连通度,最后证明并确定n-维折叠交叉立方体的2-限制性边连通度等于4n-4(n≥4)。这个结果意味着,为了使n-维折叠交叉立方体不连通且每个分支中没有度数小于2的点,至少应有4n-4条边同时发生故障。

交叉立方体的可靠性分析

h-限制性边连通度是衡量大型互连网络可靠性和容错性的一个重要参数.交叉立方体网络是超立方体网络的一个变形,在平行计算系统当中交叉立方体网络是最重要的网络之一.该文研究了交叉立方体网络的限制性边连通度.

基于FQn和圈的细胞分裂生长网络FQCC(n,k)及其性质

折叠立方体连通圈网络FQCC(n) (n >1)是一类典型的互连网络,它是3正则的。师海忠根据折叠立方体连通圈网络i>FQCC(n) (n >1)和细胞分裂生长图模型设计出了一种新的互连网络——FQCC(n,k) (n >1,k是非负整数):用三长的圈代替FQCC(n)的每个顶点且圈中每个顶点恰位于折叠立方体连通圈网络FQCC(n) (n >1)中与该顶点关联的一条边上,得到新的网络FQCC(n,1);再类似的用三长的圈代替FQCC(n,1)的每个顶点得FQCC(n,2),循环执行上述方法k次得到的新网络称为FQCC(n,k) (n >1,k是非负整数)。该网络FQCC(n,k)在保持了FQCC(n)的小的固定的度(为3)的特性外,还有比FQCC(n)更好的扩展性。进而提出了猜想:FQCC(n,k)是Hamilton图。赵媛证明了FQCC(2,k)是平面图和Hamilton图,还证明了FQCC(n,k) (k >1)不是点可迁的。