星网的4-限制边连通度

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (13): 71-74.

星网的4-限制边连通度

赵元庆1，金显华2

1.安阳师范学院计算机与信息工程学院，河南安阳 455002
2.安阳师范学院公共计算机教学部，河南安阳 455002

出版日期:2012-05-01 发布日期:2012-05-09

The 4-restricted edge connectivity of star networks

ZHAO Yuanqing1, JIN Xianhua2

1.School of Computer and Information Engineering, Anyang Normal University, Anyang, Henan 455002, China
2.Computer Teaching Department, Anyang Normal University, Anyang, Henan 455002, China

Online:2012-05-01 Published:2012-05-09

摘要/Abstract

摘要： 星网是并行与分布式处理系统中最流行的互连网络之一，它以n维星图作为拓扑结构。k-限制边连通度是衡量网络可靠性的重要参数之一；一般地，网络的k-限制边连通度越大，它的连通性就越好。研究了星网的k-限制边连通度，证明了当n≥4时，n维星网的4-限制连通度为4n－10。

关键词: 互连网络, k-限制边连通度, 可靠性, 星型网络

Abstract: The n-dimensional star graph, which is denoted by Sn is one of the most popular interconnection networks and the k-restricted edge connectivity of a graph G is the minimum cardinality of a set of edges, if any, whose deletion disconnects G and every remaining component has at least k vertices. The k-restricted edge connectivity is one of the most parameters to evaluate the reliability of a network. In general, the larger the k-restricted edge connectivity of a network, the more reliable the network. The k-restricted edge connectivity of n-dimensional star graph is investigated and the result that the 4-restricted edge connectivity of Sn is 4n－10 for n≥4 is proved.

Key words: interconnection networks, k-restricted edge connectivity, reliability, star graph networks

赵元庆1，金显华2. 星网的4-限制边连通度[J]. 计算机工程与应用, 2012, 48(13): 71-74.

ZHAO Yuanqing1, JIN Xianhua2. The 4-restricted edge connectivity of star networks[J]. Computer Engineering and Applications, 2012, 48(13): 71-74.

[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.