（n，k）--冒泡排序網絡的結構連通度和子結構連通度

張國珍，楊偉麗

（山西大學 數學科學學院，山西 太原 030006）

0 引言和術語

在許多并行計算機系統中，處理器通過互連網絡連接。例如：超立方體［1-2］，星圖［3］，平衡超立方體［4］，冒泡排序圖［5-9］，排列圖［10-11］，k元 n立方體［12-13］?；ミB網絡通常用簡單無向圖 G=(V，E)表示，V中每個頂點代表一個處理器，每條邊對應一條通信路線。連通度是衡量互連網絡可靠性和容錯性最重要的參量。作為經典連通度的推廣，Fàbrega和Fiol［14］引入g-超連通度，用κg(G)表示，是使得圖G不連通所需刪除的最少頂點的個數，并且刪除頂點后G中每個分支的點數大于g。許多研究者主要研究單個節點故障對網絡的可靠性和容錯性的影響，然而，頂點之間是互相關聯的，一個故障點的鄰點可能更容易受到攻擊并且有更高的概率發生故障。于是Lin等[1]提出了結構連通度和子結構連通度的概念。令H是G的一個連通子圖，圖G的H-結構連通度定義為κ(G；H)是指子圖集合F={H1，H2，…，Ht}的最小基數，其中每一個Hi與H同構，且G-F是不連通的。圖G的H子結構連通度定義為κs(G；H)，是指子圖集合F={J1，J2，…，Jt}的最小基數，其中每一個Ji與H的子圖同構，且G-F是不連通的。已有學者研究了超立方體［1］，折疊立方體［2］，紐立方體［15-16］，冒泡排序網絡［17］和交換群網絡［18］的結構連通度和子結構連通度。(n，k)-冒泡排序網絡是n維冒泡排序網絡的推廣，它保留了n維冒泡排序網絡的層次性和正則性，比n維冒泡排序網絡更加靈活與實用。

（1）存在整數m∈[1，k-1]使得am=bm+1，am+1=bm且對于任意i∈[1，k]{m，m+1}有ai=bi；

（2）對于任意的 i∈[2，k]有 ai=bi并且 a1≠b1。

設 u 是 Bn，k中一個點，不妨設 u=1 2 3 4 5…(k-1)k。對應類型（1），u 在 Bn，k中有 k-1 個鄰點，分 別 記 為 u1， u2， … ， uk-1， 其 中 u1=2 1 3 4 5…(k-1)k， u2=1 3 2 4 5…(k-1)k，uk-1=1 2 3 4 5…k(k-1)。 對 應 類 型（2），u 在 Bn，k中 有 n-k個 鄰 點 ，分 別 記 為 uk+1=(k+1)2 3 4 5…(k-1)k，uk+2=(k+2)2 3 4 5…(k-1)k，un=n 2 3 4 5…(k-1)k。設p，q是正整數，滿足1≤p＜q-1≤k-1，令 up，q=1 2 3…(p+1)p…(q+1)q…(k-1)k。設 s，t是正整數，滿足 2≤s≤k-1 且 k+1≤t≤n，令 uts=t 2 3…(s+1)s…(k-1)k，utp，q=t 2 3…(p+1)p…(q+1)q…(k-1)k。圖 1 畫出了 (n，k)-冒泡排序網絡 B4，1，B4，2和 B4，3。

圖1 (n，k)-冒泡排序圖B4，1（a），B4，2（b）和B4，3（c）Fig.1 (n，k)-bubble-sort graph B4，1（a），B4，2（b）and B4，3（c）

在圖G中，如果存在兩個非空集合X，Y，使得V(G)=X∪Y，X∩Y=?且G中的任意一條邊的兩個端點不能同時屬于X或Y，則稱圖G為二部圖或者偶圖。若X的每個頂點和Y的每個頂點相連，稱G為完全偶圖。若|X|=m，|Y|=n，對應的完全偶圖記為Km，n。當m=1時，我們把K1，n稱為n爪。若 V(Pk)={u1，u2，u3，…，uk}(ui≠uj，1≤i＜j≤k)且 E(Pk)={u1u2，u2u3，…，uk-1uk}，稱 Pk為 一 條 k路。圖2給出了P4和K1，3。假設V1是V的一個非空子集，以V1為頂點集，以兩端點均在V1中的邊的全體為邊集所構成的子圖，稱為G的由V1導出的子圖，記為G[V1]。若圖G和圖H同構，記為G?H。設v是圖G的一個頂點，G中所有與v相鄰的點的集合記為N(v)。

圖2 （a）路P4；（b）爪 K1，3Fig.2 （a）Path P4；（b）Claw K1，3

4 結論

在這篇文章中，我們研究了(n，k)-冒泡排序網絡的H-結構連通度和H-子結構連通度，其中H∈{P3，P4，K1，3}。在此基礎上，我們還可以探究(n，k)-冒泡排序網絡中一般的路和爪的結構連通度和子結構連通度。通過類似方法也可以研究其他網絡的結構容錯性。