增广泡型网络的边连通性和限制边连通性  

Link connectivity and restricted link connectivity of augmented bubble-sort networks

作　　者：邱亚娜[1] 杨玉星[1,2] 

机构地区：[1]河南师范大学数学与信息科学学院,河南新乡453007 [2]大数据统计分析与优化控制河南省工程实验室(河南师范大学),河南新乡453007

出　　处：《计算机应用》2016年第11期3006-3009,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(U1304601);河南省教育厅科学技术研究重点项目(14B520004)~~

摘　　要：针对泡型网络边连通度和限制边连通度小、容错能力弱的弊端,采用在泡型网络中增加通信线路的方法构建了高可靠性的增广泡型网络。通过构造最小边割的方法,证实了n维增广泡型网络中去除任意不多于n-1条边时,该增广泡型网络的任意两个节点之间依旧连通;通过构造最小限制边割的方法,证实了在不产生孤立节点的条件下,n维增广泡型网络中去除任意不多于2n-3条边时,该增广泡型网络的任意两个节点之间依旧连通。依据上述结果,通过实例证明增广泡型网络的容错能力优于泡型网络。In view of the disadvantages of small link connectivity, restricted edge connectivity and weak fault tolerance, a kind of augmented bubble-sort network was designed by adding some links to the original bubble-sort network. By constructing a minimum link cut of the n dimensional augmented bubble-sort network, the link connectivity of the n dimensional augmented bubble-sort network was proved to be n, which implied that any two nodes are still connected even deleting n - 1 links. The restricted link connectivity of the n dimensional augmented bubble-sort network was proved to be 2n - 2. Therefore, any two nodes of the n dimensional augmented bubble-sort network were still connected even deleting 2n - 3 links if the removal of these links doesn＇t result in singletons. Based on above results, the example rusuhs show that the augmented bubble-sort networks is better than bubble-sort network.

关 键 词：并行计算机 高性能网络 泡型网络 增广泡型网络 边连通度 限制边连通度 

分 类 号：TP302.01[自动化与计算机技术—计算机系统结构] TP393.02[自动化与计算机技术—计算机科学与技术]