蔡學鵬,徐剛剛,馮苗苗,嚴玉茹

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

1 引言

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

G=(V(G),E(G))是一個圖.對圖G中任意頂點u,設集合

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

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

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

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

設P是圖G所具有的一種性質(zhì).文獻[4]定義了圖G的條件連通度(邊連通度):如果G中存在某種點子集(邊子集),使得G刪除這種點子集(邊子集)后得到的圖不連通且每個連通分支都具有性質(zhì)P,則所有這種點子集(邊子集)中基數(shù)最小的點子集(邊子集)的基數(shù)稱為圖G的條件連通度(邊連通度),記為κ(G:P)(λ(G:P)).隨后,文獻[5-6]研究了下面所述的一種條件連通度(邊連通度).

設S?V(G)(S?E(G))且g是一個非負整數(shù),如果G-S是不連通的且G-S的每個連通分支中至少有g+1個頂點,則稱S是G的一個Rg-割(Rg-邊割).若G存在Rg-割(Rg-邊割),則G的所有Rg-割(Rg-邊割)中基數(shù)最小的Rg-割(Rg-邊割)的基數(shù)稱為G的g-額外連通度(g-額外邊連通度),記為κg(G)(λg(G)).有關網(wǎng)絡(圖)的g-額外連通度(g-額外邊連通度)的更多結論可參看文獻[7-15].

文獻[16-17]各自介紹了經(jīng)典連通度和經(jīng)典邊連通度另外一種推廣形式,即r-分支連通度和r-分支邊連通度.設S?V(G)(S?E(G))且r是一個非負整數(shù),如果G-S至少有r個連通分支,則稱S是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-分支邊連通度)可以認為是經(jīng)典連通度(邊連通度)的一種推廣形式并且它能更加精確地衡量大型并行處理系統(tǒng)的可靠性和容錯性.網(wǎng)絡(圖)的r-分支連通度(r-分支邊連通度)已被許多學者所研究,詳細結果可參看文獻[18-21]及相關文獻.

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

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

2 預備知識

3 主要結論

4 結束語

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

(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條邊才能得到兩個連通分支;

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

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