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

2021-10-12 09:18:40蔡學鵬徐剛剛馮苗苗嚴玉茹

純粹數學與應用數學 2021年3期

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

(新疆農業大學數理學院,新疆烏魯木齊 830052)

1 引言

眾所周知,互連網絡在并行計算及通信系統中發揮著重要作用.一個網絡的拓撲結構在數學上通常被抽象的模型化為一個圖G=(V(G),E(G)),其中V(G)是圖G的頂點集來表示網絡處理器的集合,E(G)是圖G的邊集來表示網絡的通信鏈路集.在本文中,術語圖和網絡可以互換使用.本文中所有的圖都認為是無向的,簡單的和連通的,對于未說明的圖論符號和術語,可參考文獻[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是一個實數,[x]表示不超過x的最大整數.

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

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

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

在并行計算系統中,n維交叉立方體CQn[22-23]和n維折疊超立方體FQn[25]是最重要且最流行的兩個互連網絡.基于交叉立方體和折疊超立方體,文獻 [26-27]介紹了n維折疊交叉立方體網絡,記作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.這篇文章將證明