折疊交叉立方體的3-額外邊連通度

蔡學鵬， 徐剛剛， 史 偉

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

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

設G＝（V（G），E（G））是一個圖，則對于圖G中任意頂點u∈V（G），設集合

和

分別表示頂點u的鄰點集和鄰邊集，記為NG（u）和NEG（u）.d G（u）＝ ｜NG（u）｜稱為圖G中頂點u的度.對于圖G的子圖K，設

和

分別表示子圖K在G中的鄰點集和子圖K在G中的鄰邊集.設Kr，s＝ （V1∪V2，E）表示一個完全二部圖，其中V1和V2分別是由r個點和s個點構成的不交點集.Kr，s的點集V（Kr，s）＝V1∪V2，邊集E＝｛（u，v）｜u∈V1，v∈V2｝.Pn＝ 〈u1，u2，…，u n〉表示圖G中一條具有n個頂點和n－1條邊的路，Cn表示具有n個頂點的圈.

圖G的經典連通度κ（G）和邊連通度λ（G）是衡量網絡可靠性和容錯性的2個重要參數［3］.連通度κ（G）和邊連通度λ（G）越大，網絡的可靠性就越高，但也有明顯的不足之處.比如，在互連網絡的實際應用中，與一個處理器相連接的所有處理器（鏈路）同時發(fā)生故障可能性較低，所以這2個參數衡量網絡可靠性和容錯性是不精確的.為克服這些不足，可以通過對G-S的每一個分支強加一些限制條件來推廣圖G的經典連通度（邊連通度），這里S?V（G）（S?E（G））.

設P是圖G所具有的一種性質.Harary［4］首先提出圖G的條件連通度（邊連通度）概念.如果G中存在某種點子集（邊子集），使得G刪除這種點子集（邊子集）后得到的圖不連通且每個連通分支都具有性質P，則所有這種點子集（邊子集）中基數最小的點子集（邊子集）的基數稱為圖G的條件連通度（邊連通度），記為 κ（G：P）（λ（G：P））.隨后，Fàbrega等［5-6］研究了下面所述的一種條件連通度（邊連通度）.

設S?V（G）（S?E（G））且g是一個非負整數，若G-S不連通且G-S的每個連通分支中至少有g＋1個頂點，則稱S是G的一個Rg-割（Rg-邊割）.如果G存在Rg-割（Rg-邊割），則G中基數最小的Rg-割（Rg-邊割）的基數稱為G的g-額外連通度（g-額外邊連通度），記為 κg（G）（λg（G））.明顯的，如果G不是完全圖，則 κ0（G）＝κ（G）且

因此，g-額外連通度（g-額外邊連通度）可以認為是經典連通度（邊連通度）的一種推廣形式，并且它能更加精確地衡量大型并行處理系統(tǒng)的可靠性和容錯性.網絡（圖）的g-額外連通度（g-額外邊連通度）［7-22］已被許多學者研究.

在平行計算系統(tǒng)中，n維交叉立方體CQ［23-25］

n和n維折疊超立方體FQn［26］是最重要且最流行的2個互連網絡.基于交叉立方體和折疊超立方體，Zhang［27］介紹了n維折疊交叉立方體，記作FCQn.FCQn具有許多重要的特性，比如短的直徑、短的平均距離和非常低的消息流量密度.Pai等［28］研究了FCQn的點傳遞性.對于FCQn的詳細結果可參看文獻［7，28-30］.

Adhikari等［29］證明 κ（FCQn）＝ κ0（FCQn）＝λ（FCQn）＝ λ0（FCQn）＝n＋1，n≥2.Cai等［7，30］分別確定了

下面將證明

1 預備知識

定義1.1設x＝x1x0和y＝y(tǒng)1y0是2個二進制字符串，如果

則稱x和y是相關的，記作x～y；否則，x和y是不相關的，記作x

n維交叉立方體CQn的頂點集

它的遞歸定義如下.

定義1.2［23］CQ1是2個頂點標為0和1的完全圖.當n≥2時，CQn是由2個n－1維子交叉立方體中的每個頂點最左面的第一個字符分別是0和1.和中的2個頂點u＝0u n－2…u0和v＝1vn－2…v0是相鄰的，當且僅當

1）如果n是偶數時，則u n－2＝vn－2；

通過以上定義，可得下面的推論.

推論1.1［23］CQn中的2個頂點

是相鄰的，當且僅當存在整數l，1≤l≤n，滿足下面4個條件：

由定義可知，CQn是有2n個頂點和n2n－1條邊的n－正則圖.當n≥2時，CQn可分解成2個子交叉立方體是由點集｛iu n－2…u0｝，i∈｛0，1｝誘導的CQn的子圖.和是由一個完美匹配相連.

下面給出n維折疊交叉立方體的定義.

定義1.3［29］n維折疊交叉立方體，記為FCQn.它是由交叉立方體CQn中的任意2個互補的點x＝x n－1x n－2…x0和增加一條邊后得到的，其中這些新增加的邊稱為FCQn的補邊，它們構成的集合記為中的邊稱為FCQn的交叉邊.

圖1表示CQ3和FCQ3的圖.由定義可知，FCQn是有2n個頂點和（n＋1）2n－1條邊的（n＋1）-正則圖.

圖1 CQ 3和FCQ 3Fig.1 CQ 3 and FCQ 3

對于FCQn＋1，如果FCQn＋1中的2個頂點是通過交叉邊相鄰的，且它們最左面的第i（0≤i≤n）個字符是不同的，則稱它們是沿著維數i相鄰，也稱v是u的i-鄰點，記作v＝u i.由定義可知，u ij是u i的j-鄰點.明顯地，u ii＝u.FCQn＋1－中的邊（u，u i）定義為頂點u的i-邊，記作ei（u）.設

表示與頂點u關聯(lián)的補邊.

由定義1.3可知，FCQn＋1（n≥2）可以分解成2個子交叉立方體是由點集｛iu n－1…u0｝，i∈｛0，1｝誘導的FCQn＋1的子圖.和之間通過2個完美匹配和M0是連通的，其中設

引理1.1［25］κ1（CQn）＝ λ1（CQn）＝2n－2，n≥3.

引理1.2［19］κ2（CQn）＝ λ2（CQn）＝3n－4，n≥4.

引理1.3［3］CQn（n≥3）中不含3長圈.

文獻［7］中，證明了下面的引理.

引理1.4［7］設u和v是CQn中2個不同的頂點，則｜NCQn（u）∩NCQn（v）｜≤2.

引理1.5［7］FCQn（n≥4）中不含3長圈.

引理1.6［7］設u和v是FCQn中2個不同的頂點，則｜NFCQn（u）∩NFCQn（v）｜≤2.

由CQn的定義可知，CQn中包含C4、P4和K1，3.通過引理1.3和1.4，很容易得到下面3個引理.

引理1.7設C4是CQn（n≥2）中的一個4長圈，那么｜NECQn（C4）｜＝4n－8.

引理1.8設P4是CQn（n≥3）中的一個4長路，那么｜NECQn（P4）｜＝4n－6.

引理1.9設K1，3是CQn（n≥3）中的子圖，那么｜NECQn（K1，3）｜＝4n－6.

方便起見，下面的討論中考慮FCQn＋1.

通過引理1.5和1.6，可得下面的引理.

引理1.10設C4是FCQn＋1（n≥2）中的一個4長圈，那么｜NEFCQn＋1（C4）｜＝4n.

2 主要結論

引理2.1設A是由CQn（n≥3）中的4個頂點誘導的子圖.若u∈V（CQn－A），則｜NA（u）｜≤2.

證明很容易知道，A與P4同構，或者A與C4同構，或者A與K1，3同構.通過反證法，假設｜NA（u）｜≥3.因此，要么CQn中包含3長圈，要么CQn中的任意2個不同頂點的公共鄰點個數至少是3個，這與引理1.5和1.6的結論矛盾.

引理2.2設K?E（CQn）且｜K｜≤2n－2（n≥4），則CQn－K滿足下面3種情形之一：

1）CQn－K是連通的；

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

3）CQn－K有2個分支，其中一個分支是一條孤立邊.

證明下面的討論假設n≥4.

如果CQn－K是連通的，則情形1）成立.現在可假設CQn-K是不連通的.因為

所以CQn－K中至少包含一個孤立頂點或者一條孤立邊.另外，因為CQn中至少移除2n－1條邊后才能產生2個孤立頂點并且又因｜K｜≤2n－2，所以CQn－K中至多包含一個孤立頂點.相反地，因為CQn中至少移除3n－4條邊后才能產生一個至少有3個頂點的孤立頂點集，且｜K｜≤2n－2＜3n－4，所以CQn－K要么包含唯一一個孤立頂點，要么包含唯一一條孤立邊.下面考慮2種情形.

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

所以CQn－K－｛u｝是連通的.因此，可知引理中情形2）成立.

情形2 設e＝（u，v）是CQn－K中唯一一條孤立邊.因為

所以CQn－K－｛u｝是連通的.因此，可知引理中情形3）成立.

引理2.3設K?E（FCQn＋1）（n≥3），令FCQn＋1＝L⊕R，于是

如果｜K｜≤4n－1且FCQn＋1－K中不含任何孤立頂點、孤立P2和孤立P3，那么L－KL（R－KR）中的每一個頂點都與R－KR（L－KL）中的某個點連通.

證明設u∈V（L－KL）.若e0（u）?KM0或者（u）?K，則結論成立；否則，e0（u）∈KM0且（u）∈K.因為FCQn－K中不含孤立頂點，所以存在一個頂點v∈V（L－KL），使得v是u的鄰點.如果e0（v）?KM0或者（v）?K，則結論成立；否則，e0（v）∈KM0且（v）∈K.因為FCQn－K中不含孤立P2，所以存在一個頂點w∈V（L－KL），使得w是u或者v的鄰點.如果e0（w）?KM0或者（w）?K，則結論成立；否則，e0（w）∈KM0且（w）∈K.由于FCQn－K中不含孤立P3，所以存在一個頂點z∈V（L－KL），使得z是u或者v或者w的鄰點.如果e0（z）?KM0或者（z）?K，則結論成立；否則，可設e0（z）∈KM0且（z）∈K.方便起見，令A＝ ｛u，v，w，z｝，K′＝ ｛e0（u），（u），e0（v），（v），e0（w），（w），e0（z），（z）｝.

下面證明FCQn＋1－K′中存在｜NEL（A）｜條兩兩邊不交的連接A與R的路.設y∈NL（A）.由引理2.1可知，A與頂點y關聯(lián)的鄰邊至多有2條.如果與y關聯(lián)的A的鄰邊只有一條（可設為e），則可選擇〈e，e0（y）〉作為連接A與R的路；否則，設e1和e2是與y關聯(lián)的A的2條鄰邊.在這種情形下，可分別選擇〈e1，e0（y）〉和〈e2，e0（y）〉作為連接A與R的路.通過考慮NL（A）中的每一個頂點y.由引理1.7～1.9可知，FCQn＋1－K′中存在

條兩兩邊不交的連接A與R的路.但是，因為這些路至多包含K中的

條邊，所以至少存在一條連接u到R－KR中某個頂點的路.同理，可證明R－KR中的每一個頂點都與L－KL中的某個頂點連通.

定理2.1λ3（FCQn＋1）＝4n，n≥4.

證明假設n≥4，設C4是FCQn＋1中的一個4長圈.通過引理1.10可得｜NEFCQn＋1（C4）｜＝4n.令Y＝FCQn＋1－V（C4），因為 ｜V（C4）｜＝4且κ（FCQn＋1）＝n＋2≥6，所以Y是連通的.進一步，

所以NEFCQn＋1（C4）是FCQn＋1中的一個R3-邊割，即λ3（FCQn＋1）≤4n.

下面證明 λ3（FCQn＋1）≥4n，n≥4.設K?E（CQn）使得｜K｜＝4n－1，且FCQn＋1－K中不含任何孤立頂點、孤立P2和孤立P3.為了證明λ3（FCQn＋1）≥4n，只需證明FCQn＋1－K是連通的，設FCQn＋1＝L⊕R.

設Mi（i＝1，2…，n）是FCQn＋1－ （M0∪）中的一邊集且Mi中每條邊的2個頂點最左面的第i個字符是不同的，于是M0，M1，…，Mn和形成了E（FCQn＋1）的一個劃分.對每個i∈｛0，1，…，n｝，如果有｜Mi∩K｜≤2且｜∩K｜≤2，則

因此，存在某個i∈｛0，1，…，n｝，使得｜Mi∩K｜≥3或者另外，對FCQn＋1的頂點重新標號使得

方便起見，設

因此

不失一般性，假設｜KL｜≤｜KR｜，于是有

由引理2.2可知，L－KL滿足下面3種情形之一：

1）L－KL是連通的；

2）L－KL有2個分支，其中一個分支是一個孤立頂點；

3）L－KL有2個分支，其中一個分支是一條孤立邊.

情形1L－KL是連通的.通過引理2.3，容易得到R－KR中的每一個頂點與L－KL中的某個頂點是連通的.因此，FCQn＋1－K是連通的.

情形2L－KL有2個分支，其中一個分支是一個孤立頂點.設u是L－KL中一個孤立的頂點.接下來證明FCQn＋1－K中u與L－KL－｛u｝是連通的.注意到｜KL｜≥｜NEL（u）｜＝n.因為FCQn＋1－K中不含任何孤立點，所以e0＝（u，u0）?KM0或者考慮下面2種情形.

根據引理2.3相似的討論方法，可得

中存在｜NE R（A）｜＝2（n－1）＋n＝3n－2條兩兩邊不交的連接A與L－KL－｛u｝的路，但是這些路至多包含K中的

條邊.因此，FCQn＋1－K中u與L－KL－｛u｝是連通的.

根據引理2.3的證明中相似的討論方法，可得FCQn＋1－（K′∪｛e0（u）｝）中存在

條兩兩邊不交的連接A與L－KL－｛u｝的路，但是這些路至多包含K中的

條邊.因此，FCQn＋1－K中u與L－KL－｛u｝是連通的.

情形3L－KL有2個分支，其中一個分支是一條孤立邊.設e＝（u，v）是L－KL中一個孤立的邊，下面證明FCQn＋1－K中邊e與L－KL－｛u，v｝是連通的.因為

所以導致｜KL｜＝ ｜KR｜＝2n－2且｜KM0∪K｜＝3.現在可考慮兩兩邊不交的路的集合B＝｛〈e0（u），中的每一條路都是連接e到L－KL－｛u，v｝.因為構成B中每一條路的邊都屬又因為｜B｜＝4且｜KM0∪K｜＝3，所以B中存在一條路P使得e通過P與L－KL－｛u，v｝連通.

3 結束語

本文在折疊交叉立方體網絡經典連通度和超連通度的基礎上，進一步研究3-額外邊連通度，證明了當n≥5時，λ3（FCQn）＝4n－4.也就是說，FCQn至少刪除4n－4條邊，才能得到不包含孤立頂點、孤立P2和孤立P3的非連通圖.FCQn的經典邊連通度是n＋1.由此可知，3-額外邊連通度幾乎是經典邊連通度的4倍，這使得FCQn可靠性的度量更加精確.因此，3-額外邊連通度比經典邊連通度更適合評價大規(guī)模折疊交叉立方體網絡的可靠性.另一方面，經典邊連通度假定折疊交叉立方體網絡的任一頂點的所有鄰邊都可能同時故障，這種情況幾乎不可能發(fā)生.然而3-額外邊連通度假定折疊交叉立方體網絡的任一頂點的部分鄰邊不能同時故障，這更符合實際情況.因此，在評價折疊交叉立方體網絡的可靠性時，3-額外邊連通度比經典邊連通度更具優(yōu)勢性.