泡形互连网络的条件连通性度量

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (22): 13-16.

泡形互连网络的条件连通性度量

杨玉星1，3，王世英2

1.山西大学计算机与信息技术学院，太原 030006
2.山西大学数学科学学院，太原 030006
3.安阳师范学院计算机与信息工程学院，河南安阳 455002

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-08-01 发布日期:2011-08-01

Conditional vertex connectivity measures for bubble-sort networks

YANG Yuxing1，3，WANG Shiying2

1.School of Computer and Information Technology，Shanxi University，Taiyuan 030006，China
2.School of Mathematical Sciences，Shanxi University，Taiyuan 030006，China
3.School of Computer and Information Engineering，Anyang Normal University，Anyang，Henan 455002，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-08-01 Published:2011-08-01

摘要/Abstract

摘要： n维泡形网络是设计大规模多处理机系统时最常用的互连网络拓扑结构之一，它以n维泡形图Bn为数学模型。F是连通图G的顶点子集，使得G-F不再连通且G-F的每个连通分支都有至少有n个顶点的F的势叫做G的Rk连通度。Rk连通度是衡量网络可靠性的一个重要参数。一般来说，网络的Rk连通度越大，其可靠性越高。研究了n维泡形网络的 k连通性;证明了在n维泡形网络中，当n≥3时，其R1连通度为2n-4;当n≥4 时，其R2连通度为4n-12。

关键词: 互连网络, 条件点连通度, 泡形网络, 可靠性

Abstract: The n-dimensional bubble-sort network is one of the most popular interconnection networks in large-scale multiprocessor systems and it takes n-dimensional bubble-sort graph Bn as mathematical model.The Rk -vertex-connectivity of a connected graph G is the minimum cardinality of a set of vertices whose deletion disconnects G and any vertex of the remaining components has at least k neighbors.The Rk -vertex-connectivity is one of the most parameters to evaluate the reliability of a network.In general，the larger the Rk -vertex-connectivity of a network is，the more reliable the network is.The Rk -vertex-connectivity of n-dimensional bubble-sort graphs is investigated.The theorems that the R1 -vertex-connectivity of Bn is 2n-4 for n≥3 and R2 -vertex-connectivity of Bn is 4n-12 for n≥4 are proved.

Key words: interconnection networks, conditional vertex connectivity, bubble-sort graphs, reliability

杨玉星1，3，王世英2. 泡形互连网络的条件连通性度量[J]. 计算机工程与应用, 2011, 47(22): 13-16.

YANG Yuxing1，3，WANG Shiying2. Conditional vertex connectivity measures for bubble-sort networks[J]. Computer Engineering and Applications, 2011, 47(22): 13-16.

[1]	蒋斌，梁小安，张亮，高杨军. 基于改进修正权重的证据组合方法[J]. 计算机工程与应用, 2021, 57(24): 100-106.
[2]	冯凯，李婧. k元n方体网络的子网络可靠性[J]. 计算机工程与应用, 2021, 57(16): 83-89.
[3]	李锐，李晓会，陈鑫. 可靠性绿色物流配送选址-路径问题研究[J]. 计算机工程与应用, 2020, 56(23): 237-244.
[4]	任慧. 考虑运输中断的可靠三级供应链网络设计[J]. 计算机工程与应用, 2019, 55(6): 265-270.
[5]	单文波1，陈博伶2，钟秋浩1，王建新1. 基于终端数据的电信承载网异常节点定位方法[J]. 计算机工程与应用, 2019, 55(11): 85-92.
[6]	罗玲. 采用随机Petri网的嵌入式机载软件可靠性检测[J]. 计算机工程与应用, 2019, 55(1): 233-240.
[7]	荣宇音，徐罗山. 逻辑系统L和BL的广义演绎定理的逆定理[J]. 计算机工程与应用, 2019, 55(1): 47-49.
[8]	程红霞1，谭新莲2. 多次重传的链状无线传感网络可靠性分析[J]. 计算机工程与应用, 2018, 54(5): 79-84.
[9]	靖天才，方景龙，魏丹. 面向复杂UML的Markov建模方法研究[J]. 计算机工程与应用, 2018, 54(4): 60-65.
[10]	张国珍. 极大限制边连通网络的充分条件[J]. 计算机工程与应用, 2017, 53(8): 19-22.
[11]	王涛，蔡金燕，孟亚峰. 总线型细胞阵列设计与空闲细胞选择方法[J]. 计算机工程与应用, 2017, 53(8): 44-49.
[12]	任大勇. 用直觉模糊Petri网构建的供应链可靠性诊断模型[J]. 计算机工程与应用, 2017, 53(5): 260-265.
[13]	曹芳波，吕娜，陈柯帆，张步硕，刘创. 航空集群网络可靠性估计路由选择策略[J]. 计算机工程与应用, 2017, 53(24): 129-135.
[14]	管文慧，李晶，高晓慧. 边故障K元3立方体的二不交路覆盖[J]. 计算机工程与应用, 2017, 53(2): 72-78.
[15]	杨楠1，陈远波2，王燕杰2，李青2. 基于度约束最短传输树的多路径传输协议[J]. 计算机工程与应用, 2017, 53(11): 126-130.