交換折疊超立方體的連通度

蔡學鵬，楊 偉，任佰通，馮苗苗

（新疆農業大學數理學院，新疆，烏魯木齊 830052）

0 引言

隨著計算機的飛速發展，信息化和數字化技術的不斷進步，許多實際問題的數學模型使離散型結構上的數字化技術得到了更多人的關注，圖的連通度理論[1-7]作為離散數學的一個重要的組成部分。多處理器系統由兩個或兩個以上的處理器構成，處理器交換各種信息是用消息協議通過互聯網絡傳播的。在大規模集成(VLSI)技術和圓片規模集成技術(WSI)領域的最新進步已經能使含有非常多的處理器數量的處理器系統實現信息交流。因為增加的多處理器系統中處理器的數量、多處理器系統的可靠性和容錯性的研究已經成為一個活躍的熱門的研究領域，因此受到了國際數學界與工程界越來越廣泛的重視。

本文僅考慮有限的、無向的、簡單的并且連通的圖[1,8-9]。

設G=G(V,E)是一個圖。對于圖G中兩個子圖H和K，記是點集誘導的子圖。設NH(K)是在H中且與K中的點相鄰的點的集合。特殊地，如果K={v}，可記作NH(v)。設是點v在圖G中的度，設NG[v]=NG(v)∪{v}。如果不產生歧義，我們可省略下標即記為d(v),N(v),N[v]。δ(G)=表示圖G的最小度。

設S?V(G)(或者S?E(G))，如果G-S是不連通的或者平凡的，則稱S是圖G的一個點割（或者邊割）。連通度（或者邊連通度）是衡量網絡可靠性的一個重要參數。圖G的連通度κ(G)（或者邊連通度λ(G)）是圖G中最小點割（或者邊割）的基數。我們知道κ(G)≤λ(G)≤δ(G)，并且κ(G)（或者λ(G)）越大圖G就越可靠。

互聯網絡的拓撲結構經常被表示成一個連通的圖，其中圖的點和邊分別表示互聯網絡的處理器和互聯網絡的連接線[9]。在平行計算系統中，n維超立方體Q[10]，n維折疊超立方體FQnn[11]和交叉超立方體EH(s,t)[12]是三個重要的互聯網絡?；谶@三個網絡，李[13]等人在2005年提出了一個新的網絡交換折疊超立方體EFH(s,t)。EFH(s,t)是在EH(s,t)的基礎上增加了一些額外的邊獲得的，并且這些邊稱為補邊。交換折疊超立方體有許多重要的特性，比如它有短的直徑和低消費因子。最近，K.Bhavani[14]等人研究了交換折疊超立方體中的短路徑問題。有關交換折疊超立方體的詳細內容參見文獻[13-14]。

我們都知道κ(Qn)=λ(Qn)=n。馬[2]證明了κ(EH(s,t))=λ(EH(s,t))=s+1，其中1≤s≤t。本文將證明κ(EFH(s,t))=λ(EFH(s,t))=s+2，1≤s≤t。

1 預備知識

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

定義1.1[2]設交換超立方體EH(s,t)=G(V,E)，s,t是正整數。交換超立方體EH(s,t)的點集

邊集E(EH(s,t))={(u,v)|(u,v)∈V(EH(s,t)×V(EH(s,t)}是由三種類型的邊E1,E2,E3構成。

其中

通過定義，立即可得EH(s,t)的點數EH(s,t)的邊數(s+t+2)2s+t+1。設(u,v)∈E(EH(s,t))，對 某 個i=1,2,3,???,s+t，u[i]=v[i]且u[j]≠v[j]，j≠i，此時稱邊(u,v)是i-邊。如果EH(s,t)中兩個點u和v通過i-邊相鄰，則稱u和v沿維數i相鄰。我們也稱u是v的i-鄰點，記作v=ni(u)。因為EH(s,t)是Qn的一個子圖，所以EH(s,t)是一個二部圖。

定義1.2[13]交換折疊超立方體，記為EFH(s,t)，它是由交換超立方體EH(s,t)中的任意兩個互補的點增加一條邊后得到的。這些新增加的邊稱為EFH(s,t)的補邊，它們構成的集合記為E4。

EH(1,2)和EFH(1,2)的圖見圖1。

圖1 EH(1,2)和EFH(1,2)Fig.1 EH(1,2) and EFH(1,2)

通過定義 1.2，EFH(s,t)中點數2s+t+1，EFH(s,t)包含四種不同類型的邊。E1型邊：條，E2型邊：條，E3型邊條，E4型邊條。EFH(s,t)中邊的總數如果u[0]=0，則d(u)=s+2，否則d(u)=t+2。

引 理 1.1[2]κ(EH(s,t))=λ(EH(s,t))=s+1，1≤s≤t。

引理1.2[12]EH(s,t)同構與EH(t,s)。

引理1.3[13]EFH(s,t)同構與EFH(t,s)。

通過引理1.2和引理1.3，我們可以在下面討論中設s≤t，則δ(EH(s,t))=s+1且δ(EFH(s,t))=s+2。

引理 1.4[12]EH(s,t)可分解成兩個EH(s-1,t)或兩個EH(s,t-1)。

引理1.5[12]EH(s,t)是2-連通的。

引理1.6[13]EFH(s,t)是2-連通的。

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

引理2.1κ(EFH(1,t))≥3，t≥1。

證明：設F是EFH(s,t)中的任意一個點集且我們將證明EFH(s,t)-F是連通的。

t=1時，結論明顯成立。

現設t2，EFH(s,t)可被分解成為子圖L1和子圖R1，其中

L1和R1分別是由點集V(L1)和V(R1)誘導的子圖。明顯地，L1和R1都同構于EH(1,t-1)，并且連接L1和R1的邊都是由E3和E4構成。

因為R1同構于EH(1,t-1)，由引理 1.1知，R1-FR1是連通的。下面證明L1-FL1中的任何一個點通過一條路與R1-FR1中的一個點連通?？紤]下面兩種情形：

情形 1.設u=abt-1…b101，則n2(u)=abt-1…b111是u在R1中的一個鄰點。如果n2(u)?FR1，則結論成立。因此假設n2(u)∈FR1，那么是u通過E4中的一條邊相連的鄰點。通過定義，則設是連接u到R1中點的一條路。

情形 2.設u=abt-1...b100，注意到如果結論成立。因此假設設NL1(u)=如果設是一條連接u到的路，如果設是一條連接u到的路，因此證明完成。

定理2.1κ(EFH(s,t))=s+2,1≤s≤t。

證明：EFH(s,t)可分解成兩個子圖L和R，其中L和R分別是由點集V(L)和V(R)誘導的子圖。明顯地，L和R都同構于,t)EH(s-1，并且L和R之間的邊是由E2和E4構成。

如果s=1，則δ(EFH(s,t))=s+2=3，由引理2.1，可以得到κ(EFH(s,t))=s+2=3。

設s1，由引理1.1，可知κ(L)=κ(R)=s。設S是EFH(s,t)的一個最小的點割，令

則有A∪B=V(L)且C∪D=V(R)。A與B（C與D）之間的邊位于E1中且構成由點集A∪B(C∪D)誘導的子圖的一個完美匹配。B與C之間的邊位于E2中且構成了由點集B∪C誘導的子圖的一個完美匹配。A與C（B與D）之間的邊位于E4中且構成了由點集A∪C(C∪D)誘導的子圖的一個完美匹配。

下面分兩種情形計算。

情形1.L-S和R-S都連通。

我們容易知E4中每條邊的至少一個端點都屬于S。即有此時EFH(s,t)-S是連通的，這與S是點割矛盾。

情形2.L-S或者R-S不連通。

不失一般性，假設L-S是不連通的。通過引理1.1，S在L中至少有s個點。方便起見設SL SL=∩且SR=S∩R。

圖2 定理2.1證明中情形2的解釋Fig.2 Illustration of the proof of Case 2 of Theorem 2.1

由于R同構于EH(s-1,t)并且EH(s-1,t)是2 -連通的，因此可知R-SR是連通的。因為B-H中的每一個點在R都有兩個鄰點，所以由點集V(R)∪(B-H)誘導的子圖Q是連通的。因此移除S必須使得K中的某個點v與 Q不連通。通過EFH(s,t)的定義，可知且如果那么點v與Q通過E4中的一條邊相連，矛盾產生?，F在假設則否則v在A-K-F中至少有一個鄰點w，并且v通過點w和E1中的邊與Q連通，因此與

由于δ(EFH(s,t))=s+2，則κ(EFH(s,t))≤s+2。又因為S是一個最小的點割且可得κ(EFH(s,t))≥s+2，即κ(EFH(s,t))=s+2。

由κ(EFH(s,t))≤λ(EFH(s,t))≤δ(EFH(s,t))，有以下的定理2.2。

定理2.2λ(EFH(s,t))=s+2，1≤s≤t。

3 小結

本文主要研究了衡量交換折疊超立方體網絡EFH(s,t)的可靠性的兩個重要參數連通度和邊連通度，最終決定了κ(EFH(s,t))=λ(EFH(s,t))=s+2,s≤t。