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

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

关于Mbius立方体网格的连通度(英文)

图的连通度、超连通性和限制连通度是度量互连网络容错性的重要参数 .该文考虑n维M bius立方体网络MQn,证明了它的点和边连通度都为n ,当n是任何正整数时它是超连通的 ,当n≠ 2时它是超边连通的 ,当n≥ 3时它的限制点连通度和当n≥ 2时的限制边连通度都为 2n- 2 .     

互连网络的向量图模型

n-超立方体,环网,k元n超立方体,Star网络,煎饼(pancake)网络,冒泡排序(bubble sort)网络,对换树的Cayley图,De Bruijn图,Kautz图,Consecutive-d有向图,循环图以及有向环图等已被广泛的应用做处理机或通信互连网络.这些网络的性能通常通过它们的度,直径,连通度,hamiltonian性,容错度以及路由选择算法等来度量.在本文中,首先,我们提出了有向向量图和向量图的概念;其次,我们开发了有向向量图模型和向量图模型来更好地设计,分析,改良互连网络;我们进一步证明了上述各类著名互连网络都可表示为有向向量图模型或向量图模型;更重要的是该模型能够使我们设计出了新的互连网络---双星网络和三角形网络.     

依赖团数的有向图极大与超级边连通的度序列条件

互连网络通常以有向图为模型,有向图的弧连通度是网络可靠性的一个重要参数.给出了依赖团数的有向图极大和超级边连通的度序列条件.     

点可迁图的限制边连通度

设S是连通图G的边子集.如果G-S不连通而且不含孤立点,那么称S是G的一个限制边割.G中所有限制边割中最小边数称为G的限制边连通度,记为′(G).限制边连通度是对传统边连通度的推广,而且是计算机互连网络容错性的一个重要度量.点可迁图是一类重要的网络模型.本文证明了如下结论 设G是连通的点可迁图.如果G的点数n4,而且点度k2,那么或者′(G)=2k-2,或者n是偶数,G含三角形且存在整数m2,使得k′(G)=n/m2k-3.     

完全对换网络的限制连通度

完全对换网络是基于 Cayley 图模型的一类重要互连网络. 一个图 G 的 k-限制点(边)连通度是使得 G-F 不连通且每个分支至少有 k 个顶点的最小点(边)子集 F 的基数, 记作 \kappa_{k}(\lambda_{k}). 它是衡量网络可靠性的重要参数之一, 也是图的容错性的一种精化了的度量. 一般地, 网络的 k-限制点(边)连通度越大, 它的连通性就越好. 证明了完全对换网络 CT_{n} 的 2-限制点(边)连通度和 3-限制点(边)连通度, 具体来说: 当 n\geq4 时, \kappa_{2}(CT_{n})=n(n-1)-2, \kappa_{3}(CT_{n})=\frac{3n(n-1)}{2}-6; 当 n\geq3 时, \lambda_{2}(CT_{n})=n(n-1)-2, \lambda_{3}(CT_{n})=\frac{3n(n-1)}{2}-4.     

两类网络的2-限制连通度

给定图G=(V,E)和非负整数h,图G的h-限制点割S是V(G)的一个子集(如果存在)使得G-S不连通且G-S中任一点的度数至少为h.图G的h-限制连通度κ~h(G)是G的最小h-限制点割的阶数.本文中,我们证明了κ~2(FCQ_n)=4n-4 (n≥8),κ~2(SQn)=4n-8(n≥4),其中FCQ_n和SQ_n分别是n维折叠交叉超立方体和n维spined cube.     

连通无向图Rabin数的一个界

可靠性和有效性是互连网络设计的重要标准,而Rabin数是度量网络容错性和传输延迟的重要参数.将通过图的容错直径给出2- 连通无向图和~3- 连通无向图的~Rabin 数r_2(G)和r_3(G)的界;同时也得到r_2(G) = D_2(G)成立的一个条件.     

点可迁图的限制边连通度

设Ｓ是连通图Ｇ的边子集．如果Ｇ－Ｓ不连通而且不含孤立点，那么称Ｓ是Ｇ的一个限制边割，Ｇ中所有限制边割中最小边数称为Ｇ的限制边连通度，记为λ＇（Ｇ）．限制边连通度是对传统边连通度的推广，而且是计算机互连网络容错性的一个重要度量．点可迁图是一类重要的网络模型．本文证明了如下结论： 设 Ｇ是连通的点可迁图．如果 Ｇ的点数ｎ≥ ４，而且点度ｋ≥ ２，那么或者λ＇（Ｇ）＝ ２ｋ－２，或者ｎ是偶数，Ｇ含三角形且存在整数ｍ≥２，使得ｋ≥λ＇（Ｇ）＝ｎ／ｍ≤２ｋ－３．关     

Star图互连网络的容错性分析

限制连通度和限制容错直径是衡量互连网络可靠性的两个重要参数。当考察这两个参数时，总假设网络中和一台计算机相连接的所有计算机不会同时出现故障。该文证明了Star图互连网络的极小分离集和极小限制分离集的唯一性，然后得到了Star图的限制连通度是2n-4，当n=3,5和n≥7时，它的限制容错直径是|_3(n-1)/2_|+2，对于n =4, 6，限制容错直径是|_3(n-1)/2_|+3，即限制容错直径只比它的容错直径大1。     

依赖团数的有向图极大弧连通的充分条件

互连网络通常以有向图为模型,有向图的弧连通度是网络可靠性的一个重要参数.设D是一个有向图,δ(D)是最小度,弧连通度为λ(D),则λ(D)≤δ(D).当λ(D)=δ(D)时,称有向图D是极大弧连通的.本文给出了依赖团数的有向图极大弧连通的一些充分条件.     

ʣ��h-�ɻ��������������������Ȩ�͵���������

设{Xni,un≤i≤vn,n≥1}与{ani,un≤i≤vn,n≥1}分别为一个随机阵列和一个常数阵列.本文首先引入了随机阵列{Xni,un≤i≤vn,n≥1}关于常数阵列{ani,un≤i≤vn,n≥1}剩余h-可积的概念,它是弱于h-可积,Cesaroα-可积等其它相关可积的定义.然后在这一可积的定义和适当的条件下,我们研究了相依随机序列加权和的强收敛性和平均收敛性,推广并改进了相关文献已有结果.     

给定团数的连通图的最小代数连通度

图G的拉普拉斯矩阵的第二小特征值称为图G的代数连通度.在给定团数ω的n阶连通图中,本文刻画了具有最小代数连通度的图为风筝图PK_(n-ω,ω),其中风筝图PK_(n-ω,ω)是由完全图K_ω在某一点上引出一条悬挂路P_(n-ω)而得到的图.同时,对风筝图PK_(n-ω,ω)的代数连通度的一些性质也做了讨论.     

Bubble-sort网络的连通度和超连通度

Bubble-sort网络Bn是(n-1)-正则,点传递的二部图.在这篇文章中,我们确定了当n≥2时,Bn的(边)-连通度为n-1;当n≥3时,Bn的超(边)-连通度为2n-4.     

可迁图的超常边连通度的最优性

图的超常边连通度是图的边连通度概念的推广.对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λh一定存在(1≤h≤n/2).本文证明了当dr正则的n-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d-正则的n-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h1≤h≤min{g-1,n/2},λh达到其最大可能值,即λh=hd-2(h-1).     

纽立方体网络的容错泛圈性

互连网络包含所有可能长度的圈是一个重要的拓扑性质。纽立方体网络TOn是超立方体网络Qn的一种变型,其中n≥3是奇数。Chang等人[Information Science,113(1999),147-167]证明了TOn中包含任意长度为l的圈,其中4≤l≤2n。如果TOn中的故障点数和故障边数之和不超过(n-2),Huang等人[J.Parallel andDistributed Computing,62(2002),591-640]证明了:TQn中包含长度为2n-fv的圈,其中fv是故障点数。这篇文章改进这些结果为:TQn中包含任意长度为l的圈,其中4≤l≤2n-fv。     

(n,k)-排列图的条件连通度(英文)

点连通度是衡量互联网络容错性的一个重要参数.尽管点连通度能正确地反映了系统的容错性能,但是不能正确反映大规模网络的健壮性能.条件连通度通过对各分支附加一些要求(当整个网络被破坏时)来克服这个缺点.给定一个基于图G的网络和一个正整数l,G的R~l-连通度,记为k~l(G),定义为图G的最小节点子集的节点数,使其去掉后,G是不连通的,且每个分支的最小度至少是l.在本文中,我们得到了(n,k)-排列图的条件连通度k~l(A(_n,k))=[(l+1)k-l](n-k)-l,其中k≥l+2,n≥k+l.     

极大限制边连通超图的两个充分条件

图的限制边连通度是经典边连通度的推广,可用于精确度量网络的容错性.极大限制边连通图是使限制边连通度达到最优的一类图.首先将图的限制边连通度和最小边度的概念推广到r一致线性超图H,证明当H的最小度δ(H)≥r+1时,H的最小边度ξ(H)是它的限制边连通度λ′(H)的一个上界,并将满足ξ(H)=λ′(H)的H称为极大限制边连通超图,然后证明n个顶点的r一致线性超图H如果满足δ(H)≥(n-1)/(2(r-1))+(r-1),则它是极大限制边连通的,最后证明直径为2,围长至少为4的一致线性超图是极大限制边连通的.所得结论是图中相关结果的推广.     

n维超立方体中边不交的汉密尔顿圈

n维超立方体在并行计算领域有着广泛的应用,其特殊的拓扑结构对大规模的多处理器系统的性能具有重要的影响.在选择互连网络时,汉密尔顿性是评估网络性能的一个重要指标.本文研究n维超立方体Q_n中的汉密尔顿圈,采用构造的方法证明了以下结论:当n是2的幂次方时,Q_(2n)中有且仅有n个边不交的汉密尔顿圈.     

h-可积条件下混合随机阵列的Lr收敛性

在h-可积的条件下,利用(ρ)混合、(Ψ)混合序列矩不等式和截尾法,探讨了(ρ)混合、(Ψ)混合阵列行和的Lr收敛性,获得了一些新结果并推广了有关结论.