折疊交叉立方體的分支邊連通度

蔡學(xué)鵬,徐剛剛,馮苗苗,嚴(yán)玉茹

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

1 引言

眾所周知,互連網(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ù)語(yǔ)圖和網(wǎng)絡(luò)可以互換使用.本文中所有的圖都認(rèn)為是無向的,簡(jiǎn)單的和連通的,對(duì)于未說明的圖論符號(hào)和術(shù)語(yǔ),可參考文獻(xiàn)[1-2].

G=(V(G),E(G))是一個(gè)圖.對(duì)圖G中任意頂點(diǎn)u,設(shè)集合

分別表示頂點(diǎn)u的鄰點(diǎn)集和鄰邊集,記為NG(u)和NEG(u).dG(u)=|NG(u)|稱為圖G中頂點(diǎn)u的度.對(duì)圖G的子圖K,設(shè)

分別表示子圖K在G中鄰點(diǎn)集和子圖K在G中的鄰邊集.設(shè)u,v∈V(G),dG(u,v)表示G中連接u與v的一條最短路.對(duì)圖G的點(diǎn)集X和Y,

圖G中一條具有n個(gè)頂點(diǎn)n?1條邊的路用Pn=〈u1,u2,···,un〉表示.設(shè)x是一個(gè)實(shí)數(shù),[x]表示不超過x的最大整數(shù).

圖G的經(jīng)典連通度κ(G)和邊連通度λ(G)是衡量網(wǎng)絡(luò)可靠性和容錯(cuò)性的兩個(gè)重要參數(shù)[3].連通度κ(G)和邊連通度λ(G)越大,網(wǎng)絡(luò)的可靠性就越高.但是,這兩個(gè)參數(shù)有明顯的不足之處,比如,在一個(gè)圖中刪除相同階數(shù)的點(diǎn)集(邊集)后得到的圖的分支情況可能會(huì)有很大的區(qū)別,并且在互連網(wǎng)絡(luò)的實(shí)際應(yīng)用當(dāng)中,與一個(gè)處理器相連接的所有處理器(鏈路)同時(shí)發(fā)生故障是不可能的,所以這兩個(gè)參數(shù)衡量網(wǎng)絡(luò)可靠性和容錯(cuò)性是不精確的.為克服這些不足之處,自然要去推廣圖G的經(jīng)典連通度(邊連通度),通過對(duì)G-S的每一個(gè)分支強(qiáng)加一些限制條件,這里S?V(G)(S?E(G)).文獻(xiàn)[4]首次考慮了這個(gè)問題并且提出了圖G的條件連通度(邊連通度)的概念.

設(shè)P是圖G所具有的一種性質(zhì).文獻(xiàn)[4]定義了圖G的條件連通度(邊連通度):如果G中存在某種點(diǎn)子集(邊子集),使得G刪除這種點(diǎn)子集(邊子集)后得到的圖不連通且每個(gè)連通分支都具有性質(zhì)P,則所有這種點(diǎn)子集(邊子集)中基數(shù)最小的點(diǎn)子集(邊子集)的基數(shù)稱為圖G的條件連通度(邊連通度),記為κ(G:P)(λ(G:P)).隨后,文獻(xiàn)[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的所有Rg-割(Rg-邊割)中基數(shù)最小的Rg-割(Rg-邊割)的基數(shù)稱為G的g-額外連通度(g-額外邊連通度),記為κg(G)(λg(G)).有關(guān)網(wǎng)絡(luò)(圖)的g-額外連通度(g-額外邊連通度)的更多結(jié)論可參看文獻(xiàn)[7-15].

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

在并行計(jì)算系統(tǒng)中,n維交叉立方體CQn[22-23]和n維折疊超立方體FQn[25]是最重要且最流行的兩個(gè)互連網(wǎng)絡(luò).基于交叉立方體和折疊超立方體,文獻(xiàn) [26-27]介紹了n維折疊交叉立方體網(wǎng)絡(luò),記作FCQn.FCQn具有許多重要的特性,比如短的直徑、短的平均距離和非常低的消息流量密度.文獻(xiàn) [28]研究了FCQn的點(diǎn)傳遞性.文獻(xiàn) [7]證明了κ1(FCQn)=λ1(FCQn)=2n,n≥4.文獻(xiàn) [14]證明了λ2(FCQn)=3n?1,n≥5.對(duì)于FCQn的詳細(xì)結(jié)果可參看文獻(xiàn)[7,26-28].

文獻(xiàn)[19]研究了n-維交叉立方體CQn的分支連通度和分支邊連通度.文獻(xiàn)[29]證明了cκ2(FCQn)=κ(FCQn)=n+1,n≥3和cκ3(FCQn)=2n,n≥4.這篇文章將證明

2 預(yù)備知識(shí)

3 主要結(jié)論

4 結(jié)束語(yǔ)

本文在折疊交叉立方體網(wǎng)絡(luò)經(jīng)典連通度和2-額外連通度的基礎(chǔ)上深入研究,進(jìn)一步研究了其分支邊連通度.證明了:

(1)cλ2(FCQn)=n+1;

(2)cλ3(FCQn)=2n+1,n≥3;

(3)cλ4(FCQn)=3n+1,n≥7.

也就是說,

(1)FCQn至少刪除n+1條邊才能得到兩個(gè)連通分支;

(2)FCQn至少刪除2n+1條邊才能得到3個(gè)連通分支;

(3)FCQn至少刪除3n+1條邊才能得到4個(gè)連通分支.