折疊交叉立方體的2-限制性邊通度

蔡學鵬， 樊丹丹， 徐剛剛

(新疆農(nóng)業(yè)大學數(shù)理學院，烏魯木齊 830052)

0 引言

眾所周知，互連網(wǎng)絡在并行計算及通信系統(tǒng)中發(fā)揮著重要作用。一個網(wǎng)絡的拓撲結構在數(shù)學上通常被抽象為一個圖G= (V(G)，E(G))，其中V(G)是圖G的頂點集，表示網(wǎng)絡處理器的集合，E(G)是圖G的邊集，表示網(wǎng)絡的通信鏈路集。在本文中，術語圖和網(wǎng)絡可以互換使用。本文中所有的圖都認為是無向的、簡單的和連通的，對于未說明的圖論符號和術語，可參考文獻[1—2]。

設S ?V(G)(S ?E(G))且h是非負整數(shù)，若G－S是不連通的并且每個連通分支的最小度至少是h，則稱S是圖G的一個h-割(h-邊割)。若G存在h-割(h-邊割)，則G的所有h-割(h-邊割)中基數(shù)最小的h-割(h-邊割)的基數(shù)稱為G的h-限制性連通度(h-限制性邊連通度)，記為κ(h)(λ(h))。特殊地，1-點割(1-邊割)又稱為超點割(超邊割)。1-限制性連通度(1-限制性邊連通度)又稱為超連通度(超邊連通度)。如果κ(h)和λ(h)(h ≥1)存在，那么有κ(h-1)≤κ(h)和λ(h-1)≤λ(h)。明顯地，如果G不是完全圖，則κ(0)(G) =κ(G)且λ(0)=λ(G)。因此，h-限制性連通度(邊連通度)可以認為是經(jīng)典連通度(邊連通度)的推廣形式且它能更加精確地衡量大型并行處理系統(tǒng)的可靠性和容錯性。所以圖的h-限制性連通度(邊連通度)已被許多學者研究，詳見文獻[6—15]。

在并行計算系統(tǒng)中，n維交叉立方體CQn[16–17]和n維折疊超立方體FQn[18]是最重要且最流行的兩個互連網(wǎng)絡?；诮徊媪⒎襟w和折疊超立方體，文獻[19—20]介紹了n維折疊交叉立方體網(wǎng)絡，記作FCQn。FCQn具有許多重要的特性，比如，短的直徑、短的平均距離和非常低的消息流量密度。Pai 等人[21]研究了FCQn的點傳遞性。對于FCQn的詳細結果可參看文獻[7]。

文獻[19]證明了

1 預備知識

定義1 設x=x1x0和y=y1y0是兩個二進制字符串，若

則稱x和y是相關的，記作x～y。

n維交叉立方體CQn的頂點集V(CQn) ={bn-1bn-2···b0|bi ∈{0，1}， 0≤i ≤n－1}，它的遞歸定義如下。

圖1 CQ3 和FCQ3 的說明

2 主要結論

引理9 設FCQn+1=L ⊕R，對于任意的兩個點u，v ∈V(CQn)(n ≥3)，并且u和v有兩個共同的鄰點，則下面兩條結論成立：

1) 如果u∈V(L)或者v∈V(R)，則u和v的一個共同鄰點在L中，另一個在R中；

2) 如果u，v ∈V(L)或者u，v ∈V(R)，則u和v的兩個共同鄰點，要么都在L中，要么都在R中。

引理10 設K ?E(CQn)，并且|K|≤2n－2(n ≥4)，則CQn－K滿足下面三個條件之一：

1) CQn－K是連通的；

2) CQn－K有兩個分支，其中一個分支是一個孤立頂點；

3) CQn－K有兩個分支，其中一個分支是一條孤立邊。

證明 下面的討論，我們假設n ≥4。

如果CQn－K是連通的，則條件1)成立?，F(xiàn)在可假設CQn－K是不連通的。文獻[15]中證明了FCQn至少刪除3n－4 條邊，才能得到不包含孤立頂點和孤立邊的非連通圖。因為|K|≤2n－2＜3n－4，所以CQn－K中至少包含一個孤立頂點或者一條孤立邊。另外，因為CQn中至少移除2n－1 條邊后才能產(chǎn)生兩個孤立頂點，并且又因|K|≤2n－2，所以CQn－K中至多包含一個孤立頂點。相反地，因為CQn中至少移除3n－4 條邊后才能產(chǎn)生一個至少有3 個頂點的孤立頂點集，并且又因為|K|≤2n－2＜3n－4，所以CQn－K要么包含唯一一個孤立頂點，要么包含唯一一條孤立邊。接下來，我們考慮兩種情形。

情形1 設u是CQn－K中唯一一個孤立頂點。因為

3 結束語

本文在折疊交叉立方體網(wǎng)絡經(jīng)典連通度和超連通度的基礎上，進一步研究了其2-限制性邊連通度：證明了當n ≥4 時，λ(2)(FCQn) = 4n－4。也就是說，F(xiàn)CQn至少刪除4n－4 條邊，才能得到最小度不小于2 的非連通圖。FCQn的經(jīng)典邊連通度是n+1。由此可以看出，2-限制性邊連通度幾乎是經(jīng)典邊連通度的4 倍，這使得FCQn可靠性的度量更加精確。因此，2-限制性邊連通度比經(jīng)典邊連通度更適合評價大規(guī)模折疊交叉立方體網(wǎng)絡的可靠性。另一方面，經(jīng)典邊連通度假定折疊交叉立方體網(wǎng)絡的任一頂點的所有鄰邊都可能同時故障，這種情況幾乎不可能發(fā)生。然而，2-限制性邊連通度假定折疊交叉立方體網(wǎng)絡的任一頂點的部分鄰邊不能同時故障，這更符合實際情況。因此，在評價折疊交叉立方體網(wǎng)絡的可靠性時，2-限制性邊連通度比經(jīng)典邊連通度更具優(yōu)勢性。