Abstract: 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 rusults show that the augmented bubble-sort networks is better than bubble-sort network.

Key words: parallel computer, high-performance interconnection network, bubble-sort network, augmented bubble-sort network, link connectivity, restricted link connectivity

摘要： 针对泡型网络边连通度和限制边连通度小、容错能力弱的弊端，采用在泡型网络中增加通信线路的方法构建了高可靠性的增广泡型网络。通过构造最小边割的方法，证实了n维增广泡型网络中去除任意不多于n-1条边时，该增广泡型网络的任意两个节点之间依旧连通；通过构造最小限制边割的方法，证实了在不产生孤立节点的条件下，n维增广泡型网络中去除任意不多于2n-3条边时，该增广泡型网络的任意两个节点之间依旧连通。依据上述结果，通过实例证明增广泡型网络的容错能力优于泡型网络。

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