交換折疊超立方體的2-外連通度①

蔡學(xué)鵬， 劉夢瑤， 杜濛雨

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

在本文中， 術(shù)語圖和網(wǎng)絡(luò)可以互換使用． 所有的圖都認(rèn)為是無向的簡單連通圖， 對于未說明的圖論符號和術(shù)語， 可參見文獻(xiàn)[1-3]．

設(shè)G=(V(G)，E(G))是一個圖． 對于圖G中的任意頂點u∈V(G)， 設(shè)集合{v∈V(G){u}： (u，v)∈E(G)}和集合{(u，v)∈E(G)：v∈V(G){u}}分別表示頂點u的鄰點集和鄰邊集， 記作NG(u)和NEG(u)．dG(u)=|NG(u)|稱為圖G中頂點u的度． 對于圖G的子圖K， 設(shè)

分別表示子圖K在G中的鄰點集和鄰邊集．

圖G的經(jīng)典連通度κ(G)和邊連通度λ(G)是衡量網(wǎng)絡(luò)可靠性和容錯性的兩個重要參數(shù)[4-5]． 連通度κ(G)和邊連通度λ(G)越大， 網(wǎng)絡(luò)的可靠性就越高． 但是， 這兩個參數(shù)有明顯的不足之處， 比如， 在互連網(wǎng)絡(luò)的實際應(yīng)用當(dāng)中， 與一個處理器相連接的所有處理器(鏈路)同時發(fā)生故障的可能性較低， 所以用這兩個參數(shù)衡量網(wǎng)絡(luò)可靠性和容錯性是不精確的． 為克服這些不足之處， 可以通過對G-S的每一個分支強(qiáng)加一些限制條件來推廣圖G的經(jīng)典連通度(邊連通度)， 這里S?V(G)(S?E(G))． 文獻(xiàn)[6]首次考慮了這個問題并且提出了圖G的條件連通度(邊連通度)的概念．

設(shè)S?V(G)(S?E(G))且g是非負(fù)整數(shù)， 如果G-S是不連通的， 且G-S的每個連通分支中至少有g(shù)+1個頂點， 則稱S是G的一個Rg-割(Rg-邊割)． 若G存在Rg-割(Rg-邊割)， 則G的所有Rg-割(Rg-邊割)中基數(shù)最小的Rg-割(Rg-邊割)的基數(shù)稱為G的g-外連通度(g-外邊連通度)， 記為κg(G)(λg(G))． 明顯地， 如果G不是完全圖， 則κ0(G)=κ(G)且λ0(G)=λ(G)． 因此，g-外連通度(g-外邊連通度)可以認(rèn)為是經(jīng)典連通度(邊連通度)的一種推廣形式， 并且能更加精確地衡量大型并行處理系統(tǒng)的可靠性和容錯性． 網(wǎng)絡(luò)(圖)的g-外連通度(g-外邊連通度)已被許多學(xué)者研究， 詳細(xì)結(jié)果可參見文獻(xiàn)[6-16]及相關(guān)文獻(xiàn)．

在平行計算系統(tǒng)中，n維超立方體Qn[17]、n維折疊超立方體FQn[16]和交叉超立方體EH(s，t)[18]是3個重要的互連網(wǎng)絡(luò)． 基于這3個網(wǎng)絡(luò)， 文獻(xiàn)[19]提出了一個新的網(wǎng)絡(luò)交換折疊超立方體EFH(s，t)，EFH(s，t)是在EH(s，t)的基礎(chǔ)上增加了一些邊獲得的， 并且這些邊稱為補(bǔ)邊． 交換折疊超立方體有許多重要的特性， 比如它有短的直徑和低消費(fèi)因子．

文獻(xiàn)[20-21]探究了交換折疊超立方體EFH(s，t)的連通度和邊連通度， 并且證明了

κ(EFH(s，t))=λ(EFH(s，t))=s+2 1≤s≤t

文獻(xiàn)[22]證明了

λ2(EFH(s，t))=3s+2 6≤s≤t

本文將探討交換折疊超立方體EFH(s，t)的2-外連通度， 最終確定了

κ2(EFH(s，t))=3s+2 5≤s≤t

1 預(yù)備知識

一個n元二進(jìn)制字符串x=xn-1xn-2…x0的第i個字符記為x[i]， 0≤i≤n-1．

定義1[19]設(shè)交換超立方體EH(s，t)=G(V，E)，s，t是正整數(shù)． 交換超立方體的點集V(EH(s，t))={as-1as-2…a1a0bt-1bt-2…b1b0c：ai，bj，c∈{0， 1}， 0≤i≤s-1， 0≤j≤t-1}， 交換超立方體的邊集E(EH(s，t))={(u，v)： (u，v)∈V(EH(s，t))×V(EH(s，t))}由3種類型的邊E1，E2，E3構(gòu)成． 其中

圖1 EH(1， 2)和EFH(1， 2)

設(shè)u∈V(EFH(s，t))． 通過定義2， 如果u[0]=0， 則d(u)=s+2， 否則d(u)=t+2．

下面給出EH(s，t)和EFH(s，t)的一些結(jié)論， 主要結(jié)果的證明將會用到這些結(jié)論．

引理1[4]κ(EH(s，t))=λ(EH(s，t))=s+1， 1≤s≤t．

引理2[10]κ1(EH(s，t))=λ1(EH(s，t))=2s， 1≤s≤t．

引理3[10]EH(s，t)同構(gòu)于EH(t，s)．

引理4[23]EFH(s，t)同構(gòu)于EFH(t，s)．

通過引理3和引理4， 可以在下面討論中設(shè)s≤t， 則δ(EH(s，t))=s+1且δ(EFH(s，t))=s+2．

引理5[10]EH(s，t)可分解成兩個EH(s-1，t)或兩個EH(s，t-1)．

根據(jù)EFH(s，t)的定義容易得出EFH(s，t)具有下面性質(zhì)：

性質(zhì)1交換折疊超立方體網(wǎng)絡(luò)EFH(s，t)可以分解成兩個子圖L和R， 其中

V(L)={0as-2…a0bt-1…b0c：ai，bj，c∈{0， 1}， 0≤i≤s-2， 1≤j≤t-1}

V(R)={1as-2…a0bt-1…b0c：ai，bj，c∈{0， 1}， 0≤i≤s-2， 1≤j≤t-1}

文獻(xiàn)[14]證明了折疊超立方體FQn(n≥4)中不含3圈， 并且任何不相鄰的兩個點的共同鄰點的個數(shù)不超過2． 因此容易得到下面的引理：

引理6交換折疊超立方體EFH(s，t)中不含3圈， 并且任何不相鄰的兩個點的共同鄰點的個數(shù)不超過2．

引理7若P為EFH(s，t)中任意一條長度是2的路， 則|NEFH(s， t)(P)|≥3s+1．

證由EFH(s，t)的定義及引理7， 容易證明|NEFH(s， t)(P)|≥3s+1．

引理8[10]設(shè)K?V(EH(s，t))并且|K|<2s，s≥2． 則EH(s，t)-K滿足下面兩種情形之一：

(i)EH(s，t)-K是連通的；

(ii)EH(s，t)-K有兩個分支， 其中一個分支是一個孤立點．

2 交換折疊超立方體網(wǎng)絡(luò)的2-外連通度

定理1設(shè)EFH(s，t)=L⊕R， 對于任意的F?V(EFH(s，t))． 令FL=F∩V(L)，F(xiàn)R=F∩V(R)． 如果|F|≤3s并且EFH(s，t)-F中既無孤立點也無孤立邊， 則R-FR(或L-FL)中每一個頂點均與L-FL(或R-FR)中的一個頂點連通．

證對于任意的頂點u=1as-2…a0bt-1…b0c∈V(R-FR)， 分以下兩種情形進(jìn)行討論：

情形1u=1as-2…a0bt-1…b00．

因為EFH(s，t)-F中不存在孤立邊， 我們令

使得(v，w)∈E(R)． 可以構(gòu)造連接w至L-FL的點不交路徑， 即路徑如下：

|F-(A∪B∪D)|=|F|-|A|-|B|-|D|≤3s-(s-1)-(s-2)-9=s-6

情形2u=1as-2…a0bt-1…b01．

若|B′|

其中1≤k′≤t且k′≠i′，j′．

|F-(A′∪B′∪C′)|≤3s-t-(t-1)-4≤s-3

而u通過w可構(gòu)造t-1條路徑， 因此至少存在1條路徑使得u與L-FL中的一個頂點相連接， 定理1得證．

定理2k2(EFH(s，t))=3s+1， 其中s≥5．

證設(shè)P為EFH(s，t)中一條長度為2的路徑， 由引理7可知|NEFH(s， t)(P)|≥3s+1． 通過EFH(s，t)的定義，EFH(s，t)-(NEFH(s， t)(P)∪V(P))既不包含孤立頂點也不包含孤立邊， 因此NEFH(s， t)(P)是EFH(s，t)的一個R2-外割， 進(jìn)一步可知k2(EFH(s，t))≤3s+1．

接下來只需證明k2(EFH(s，t))≥3s+1， 即證明對于任意的頂點集F?V(EFH(s，t))， 當(dāng)|F|=3s且不存在孤立頂點也不存在孤立邊時，EFH(s，t)-F是連通的． 設(shè)EFH(s，t)=L⊕R．

方便起見， 我們設(shè)

FL=F∩V(L)FR=F∩V(R)

情形1L-FL是連通的．

由定理1， 可知R-FR中任意一頂點與L-FL中一頂點連通． 因此EFH(s，t)-F是連通的．

情形2L-FL有兩個連通分支， 其中一個是孤立點．

設(shè)u=0as-2…a0bt-1…b0c是L-FL中的一個孤立點， 此時有|FL|≥|NL(u)|≥s． 接下來證明EFH(s，t)-F中的u與L-FL-{u}是連通的． 考慮下面兩種情形：

由于

|F-(NL(u)∪A∪{v0，vs+t})|≤3s-s-(s-1)-1=s

且u通過vi可構(gòu)造s+1條通向L-{u}的路徑， 故至少存在一條路徑使得u與L-FL-{u}連通， 定理2得證．

由于

且u通過v(或w)可構(gòu)造s+t(≥2s)條通向L-{u}的路徑， 故至少存在一條路徑使得u與L-FL-{u}連通， 定理2得證．

所以F中至多有2s-3個點在D中． 因此在D中至少存在一對點不屬于F． 即u與L-FL-{u}連通．

3 小結(jié)

本文在交換折疊超立方體網(wǎng)絡(luò)經(jīng)典連通度和超連通度的基礎(chǔ)上深入研究， 進(jìn)一步研究了其2-外連通度， 證明了： 當(dāng)t≥s≥5時，k2(EFH(s，t))=3s+1． 也就是說，EFH(s，t)中至少刪除3s+1個頂點， 才能得到不包含孤立頂點和孤立邊的非連通圖．