共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
有向Kautz图是并行计算系统的一类重要网络。根据实际应用中并行计算系统的故障分布情况,提出了有向图的好邻连通度的概念,该连通度是比传统连通度更精确的网络可靠性指标,并证明了有向Kautz图K(d,n)的好邻连通度为2d-2。 相似文献
3.
《河南科学》2017,(3):345-349
笛卡尔积图是大型互联网络最重要的数学模型之一.有向图的k-限制弧连通度是弧连通度和限制弧连通度的推广,可用于度量网络的可靠性.强连通有向图D的弧子集S被称为D的一个k-限制弧割,若D-S有一个顶点数至少为k的强连通分支D_1,使得D-V(D_1)包含一个顶点数至少为k的连通子图.若这样的一个弧割存在,则称D是λ~k-连通的.D中最小k-限制弧割所含的弧数称为D的k-限制弧连通度,记做λ~k(D).在有向笛卡尔积图中,推广2-限制弧连通度的结论到k-限制弧连通度,得到有向笛卡尔积图的k-限制弧连通度的上界和3-限制弧连通度的下界,并用例子说明所得界是紧的. 相似文献
4.
《云南民族大学学报(自然科学版)》2016,(3):225-229
图的限制弧连通度是度量网络可靠性的一个重要指标.称强连通有向图D的弧割S是一个限制弧割,若D-S包含一个非平凡的强连通分支D'使得D-V(D')包含至少一条弧.限制弧连通度λ'(D)是指最小限制弧割的弧数.λ'最优有向图是使限制弧连通度尽可能大的一类有向图.定向图是一类重要的有向图.定向图和多部定向图是λ'最优的一些最小度条件将被给出.这些结果推广了Grüter等关于竞赛图的相关结论. 相似文献
5.
6.
互联网络常以有向图或无向图作为模型,有向图的限制弧连通性能精确度量网络的容错性和可靠性.称有向图D的一个弧子集S是D的限制弧割,如果D-S中存在一个非平凡的强连通分支D1使得D-V(D1)包含至少一条弧.若强连通的有向图D存在限制弧割,则称D是λ′-连通的.λ′-连通图D的最小限制弧割所含的弧数称为D的限制弧连通度,记λ′(D).设D的围长为g,任取长度为g的有向圈Cg=u1u2…ugu1,令ξ(Cg)=min{(sum from i=1 to g)d+(ui)-g,(sum from i=1 to g)d-(ui)-g}且ξ(D)=min{ξ(Cg)}.本文给出了强连通有向图D是λ′(D)≤ξ(D)的一个充分条件. 相似文献
7.
《太原师范学院学报(自然科学版)》2019,(4)
互连网络通常以有向图为模型.弧连通度是网络可靠性的一个重要参数.设D是一个有向图,δ(D)是最小度,弧连通度为λ(D),则λ(D)≤δ(D).当λ(D)δ(D)时,称有向图D是非极大弧连通的.本文给出了非极大弧连通图弧连通度的一些结果. 相似文献
8.
欧见平 《内蒙古师范大学学报(自然科学版)》2004,33(4):353-356
当n≥3时,无向二元Kautz图UK(2.n)被证明是极大限制边连通的.利用此结果确定了无向Kautz网络UK(2.N)的可靠多项式的前3项系数,给出第4项系数的一个下界,并且此下界是紧的. 相似文献
9.
范英梅 《广西师范学院学报(自然科学版)》2004,21(1):36-38
限制边连通度是传统边连通度的推广,而且是计算机互连网络容错性的一个重要度量.该文考虑Kautz无向图UK(3,n)的限制边连通度λ’,得到如下结果:λ'(UK(3,1))=4,n≥2时,λ'(UK(3,n))=8. 相似文献
10.
王晓丽 《太原师范学院学报(自然科学版)》2018,(1)
互连网络通常以有向图为模型,有向图的弧连通度λ(D)是网络可靠性的一个重要参数.设D是一个有向图,δ(D)是最小度,则λ(D)≤δ(D).文章给出了依赖于团数的有向图与度序列有关的弧连通度的下界. 相似文献
11.
作为超立方体网络的变形, n维变形超立方体VQ_n是Cheng和Chuang于1994年提出来的,它具有许多超立方体所具有的优良性质, 比如正则性和递归结构.证明了:VQ_n 的连通度和边连通度都等于n,限制连通度和限制边连通度都等于2n-2. 这个结果意味着,为了使VQ_n不连通且不含孤立点, 至少有2n-2个点或者边要同时发生故障. 相似文献
12.
《山西师范大学学报:自然科学版》2017,(3)
图D是带有两个弧轨道的强连通有向图,D1与D2是图D在自同构Aut(D)作用在边集E(D)上的两个弧轨道,有:D1=D[E1];D2=D[E2]为D的两个弧传递部分.我们证明,图D的弧连通度等于最小度,并且图D的点连通度,当加入围长条件,如果满足g(G)≥δ(D)-1/δ(Di)+1;则κ(D)=δ(D),这里我们只考虑δ(Di)≥0(i=1,2)的情况,并且δ(Di)是Di的最小度;κ(D)是有向图D的点连通度. 相似文献
13.
为精确估计网络的可靠度,我们需要最优化其图模型的限制边连通度,证明一个n≥11阶最小度δ(G)≥[n/2]-3的λ4-连通图G,在一定的条件下是λ4-最优的.进而,若n≥12,则G是超级-λ3图.并举例说明了最小度的下界是最好可能的. 相似文献
14.
《安徽师范大学学报(自然科学版)》2020,(3)
超连通度(超边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数。设G是连通图,图G的超连通度(超边连通度)是指从G中删除最小数目的点(边)使得G不连通,且G的每个连通分支中都至少包含两个顶点。李等人(2015)提出了一个新的网络交换折叠超立方体网络EFH(s,t)。该文利用超连通度和超边连通度作为评价可靠性的重要度量,对交换折叠超立方体网络的可靠性进行分析,得到了交换折叠超立方体网络的超连通度和超边连通度,证明了EFH(s,t)的超连通度和超边连通度等于2s+2,1≤s≤t。这个结果意味着,为了使EFH(s,t)不连通且不含孤立点,至少有2s+2个点(边)要同时发生故障。 相似文献
15.
设D是严格有向图(无环与重弧),λ(D)是有向图D的弧强连通度,α′(D)表示有向图D的匹配数.如果有向图D中含有一个生成欧拉子图反向一条弧的方向所得的子图,则称有向图D含有一个超欧拉bypass.证明了一个强连通有向图D满足λ(D)≥α′(D)≥5,则有向图D含有一个超欧拉bypass. 相似文献
16.
设S是连通图G的一个边割。若G-S不包含孤立点,则称S是G的一个限制边割。图G的最小限制边割的边数称为G的限制边连通度,记为λ'(G).如果图G的限制边连通度等于其最小度,则称图G是最优限制边连通的,简称λ'-最优的。设G是一个n阶的连通无三角图,且最小度δ(G)≥2.文章证明了,若最小边度ξ(G)≥(n/2-2 )(1+1/δ(G)-1),则G是λ'-最优的。并由此推出,若连通无三角图G的最小度δ(G)≥n/4+1,则G是λ'-最优的。最后给出例子说明这些结果给出的边界都是紧的。 相似文献
17.
有向图X的超弧连通性可以用严格弧连通度λ′(X)来表示,该文证明了在强连通弧对称的有向图类中,不是最优超弧连通的图只有有向图Cn。 相似文献
18.
一个图G的限制边连通度是使得G-F不连通且每个分支至少含有2个顶点的最小边子集F的基数.文章中,我们证明当n≥3时Bubble-sort图Bn的限制边连通度λ′(Bn)=2n-4. 相似文献
19.
文章研究了两连通图G1和G2的强乘积图G1G2的限制边连通度,给出了强乘积图的限制边连通度的一个上界,并确定一类特殊强乘积图的限制边连通度. 相似文献
20.
设D是一个有向图,δ(D)是最小度,弧连通度为λ(D),则λ(D)≤δ(D)。当λ(D)δ(D)时,称有向图D是非极大弧连通的。本文给出了非极大弧连通图的弧连通度的下界。 相似文献