增廣泡型網(wǎng)絡(luò)的邊連通性和限制邊連通性

　　目前，大數(shù)據(jù)的處理和復(fù)雜問題的解決對并行計算機的計算能力已近乎苛刻。為了大幅提高計算能力，并行計算機系統(tǒng)的處理器數(shù)目急劇增加，從而導(dǎo)致處理器之間的通信開銷越來越大。在超級并行計算機系統(tǒng)中，處理器之間的連接模式（即底層網(wǎng)絡(luò)）對整個系統(tǒng)的硬件消耗、通信性能等方面起著重要的、甚至是決定性的作用。

　　在實際的系統(tǒng)中，元器件和直連線路難免發(fā)生故障。在故障發(fā)生時，人們自然希望該系統(tǒng)的任意兩個節(jié)點之間依舊可以通信；反映在其底層網(wǎng)絡(luò)中，人們希望網(wǎng)絡(luò)依舊連通。連通度和邊連通度是度量網(wǎng)絡(luò)連通性和容錯能力的主要參數(shù)。然而，這兩個參數(shù)存在一個明顯的缺陷，它認(rèn)為“和同一個節(jié)點相關(guān)聯(lián)的所有邊”或“和一條邊相關(guān)聯(lián)的所有節(jié)點”很有可能同時發(fā)生故障。然而，在實際的系統(tǒng)中，同時故障幾乎是不可能的。為彌補這一不足，Esfahanian等對發(fā)生故障的系統(tǒng)的各個分支加以限制，提出了條件連通度和條件邊連通度的概念。自此，許多經(jīng)典網(wǎng)絡(luò)的條件連通度和條件邊連通度被相繼研究，其中，泡型網(wǎng)絡(luò)（ bubble-sort　network）是并行計算機系統(tǒng)的主要候選網(wǎng)絡(luò)之一，它具有正則性、點對稱性、二部性、層次性等優(yōu)秀的拓?fù)湫再|(zhì)。

　　n維泡型網(wǎng)絡(luò)的邊連通度僅為n-l，限制邊連通度僅為2n -4，從而導(dǎo)致其容錯能力不強。為此，在泡型網(wǎng)絡(luò)的基礎(chǔ)上設(shè)計了一種保留了泡型網(wǎng)絡(luò)的大多數(shù)優(yōu)秀拓?fù)湫再|(zhì)的增廣泡型網(wǎng)絡(luò)，并證明了n≥3時，n維增廣泡型網(wǎng)絡(luò)的邊連通度為n，限制邊連通度為2n -2。對比結(jié)果表明，增廣泡型網(wǎng)絡(luò)比泡型網(wǎng)絡(luò)具有更高的連通性和更強的容錯能力。