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

蔡學鵬， 樊丹丹， 徐剛剛

(新疆農業大學數理學院，烏魯木齊 830052)

0 引言

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

設S ?V(G)(S ?E(G))且h是非負整數，若G－S是不連通的并且每個連通分支的最小度至少是h，則稱S是圖G的一個h-割(h-邊割)。若G存在h-割(h-邊割)，則G的所有h-割(h-邊割)中基數最小的h-割(h-邊割)的基數稱為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-限制性連通度(邊連通度)可以認為是經典連通度(邊連通度)的推廣形式且它能更加精確地衡量大型并行處理系統的可靠性和容錯性。所以圖的h-限制性連通度(邊連通度)已被許多學者研究，詳見文獻[6—15]。

在并行計算系統中，n維交叉立方體CQn[16–17]和n維折疊超立方體FQn[18]是最重要且最流行的兩個互連網絡。基于交叉立方體和折疊超立方體，文獻[19—20]介紹了n維折疊交叉立方體網絡，記作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)成立。現在可假設CQn－K是不連通的。文獻[15]中證明了FCQn至少刪除3n－4 條邊，才能得到不包含孤立頂點和孤立邊的非連通圖。因為|K|≤2n－2＜3n－4，所以CQn－K中至少包含一個孤立頂點或者一條孤立邊。另外，因為CQn中至少移除2n－1 條邊后才能產生兩個孤立頂點，并且又因|K|≤2n－2，所以CQn－K中至多包含一個孤立頂點。相反地，因為CQn中至少移除3n－4 條邊后才能產生一個至少有3 個頂點的孤立頂點集，并且又因為|K|≤2n－2＜3n－4，所以CQn－K要么包含唯一一個孤立頂點，要么包含唯一一條孤立邊。接下來，我們考慮兩種情形。

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

3 結束語

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