蔡學(xué)鵬， 徐剛剛， 史 偉

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

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

設(shè)G＝（V（G），E（G））是一個(gè)圖，則對于圖G中任意頂點(diǎn)u∈V（G），設(shè)集合

和

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

和

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

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

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

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

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

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

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

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

下面將證明

1 預(yù)備知識

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

則稱x和y是相關(guān)的，記作x～y；否則，x和y是不相關(guān)的，記作x

n維交叉立方體CQn的頂點(diǎn)集

它的遞歸定義如下.

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

1）如果n是偶數(shù)時(shí)，則u n－2＝vn－2；

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

推論1.1［23］CQn中的2個(gè)頂點(diǎn)

是相鄰的，當(dāng)且僅當(dāng)存在整數(shù)l，1≤l≤n，滿足下面4個(gè)條件：

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

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

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

圖1表示CQ3和FCQ3的圖.由定義可知，F(xiàn)CQn是有2n個(gè)頂點(diǎn)和（n＋1）2n－1條邊的（n＋1）-正則圖.

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

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

表示與頂點(diǎn)u關(guān)聯(lián)的補(bǔ)邊.

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

引理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長圈.

文獻(xiàn)［7］中，證明了下面的引理.

引理1.4［7］設(shè)u和v是CQn中2個(gè)不同的頂點(diǎn)，則｜NCQn（u）∩NCQn（v）｜≤2.

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

引理1.6［7］設(shè)u和v是FCQn中2個(gè)不同的頂點(diǎn)，則｜NFCQn（u）∩NFCQn（v）｜≤2.

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

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

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

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

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

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

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

2 主要結(jié)論

引理2.1設(shè)A是由CQn（n≥3）中的4個(gè)頂點(diǎn)誘導(dǎo)的子圖.若u∈V（CQn－A），則｜NA（u）｜≤2.

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

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

1）CQn－K是連通的；

2）CQn－K有2個(gè)分支，其中一個(gè)分支是一個(gè)孤立頂點(diǎn)；

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

證明下面的討論假設(shè)n≥4.

如果CQn－K是連通的，則情形1）成立.現(xiàn)在可假設(shè)CQn-K是不連通的.因?yàn)?/p>

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

情形1 設(shè)u是CQn－K中唯一一個(gè)孤立頂點(diǎn).因?yàn)?/p>

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

情形2 設(shè)e＝（u，v）是CQn－K中唯一一條孤立邊.因?yàn)?/p>

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

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

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

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

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

條兩兩邊不交的連接A與R的路.但是，因?yàn)檫@些路至多包含K中的

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

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

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

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

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

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

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

方便起見，設(shè)

因此

不失一般性，假設(shè)｜KL｜≤｜KR｜，于是有

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

1）L－KL是連通的；

2）L－KL有2個(gè)分支，其中一個(gè)分支是一個(gè)孤立頂點(diǎn)；

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

情形1L－KL是連通的.通過引理2.3，容易得到R－KR中的每一個(gè)頂點(diǎn)與L－KL中的某個(gè)頂點(diǎn)是連通的.因此，F(xiàn)CQn＋1－K是連通的.

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

根據(jù)引理2.3相似的討論方法，可得

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

條邊.因此，F(xiàn)CQn＋1－K中u與L－KL－｛u｝是連通的.

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

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

條邊.因此，F(xiàn)CQn＋1－K中u與L－KL－｛u｝是連通的.

情形3L－KL有2個(gè)分支，其中一個(gè)分支是一條孤立邊.設(shè)e＝（u，v）是L－KL中一個(gè)孤立的邊，下面證明FCQn＋1－K中邊e與L－KL－｛u，v｝是連通的.因?yàn)?/p>

所以導(dǎo)致｜KL｜＝ ｜KR｜＝2n－2且｜KM0∪K｜＝3.現(xiàn)在可考慮兩兩邊不交的路的集合B＝｛〈e0（u），中的每一條路都是連接e到L－KL－｛u，v｝.因?yàn)闃?gòu)成B中每一條路的邊都屬又因?yàn)椋麭｜＝4且｜KM0∪K｜＝3，所以B中存在一條路P使得e通過P與L－KL－｛u，v｝連通.

3 結(jié)束語

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