（n，k）--冒泡排序網(wǎng)絡(luò)的結(jié)構(gòu)連通度和子結(jié)構(gòu)連通度

張國(guó)珍，楊偉麗

（山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）

0 引言和術(shù)語(yǔ)

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

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

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

設(shè) u 是 Bn，k中一個(gè)點(diǎn)，不妨設(shè) u=1 2 3 4 5…(k-1)k。對(duì)應(yīng)類型（1），u 在 Bn，k中有 k-1 個(gè)鄰點(diǎn)，分 別 記 為 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)。 對(duì) 應(yīng) 類 型（2），u 在 Bn，k中 有 n-k個(gè) 鄰 點(diǎn) ，分 別 記 為 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。設(shè)p，q是正整數(shù)，滿足1≤p＜q-1≤k-1，令 up，q=1 2 3…(p+1)p…(q+1)q…(k-1)k。設(shè) s，t是正整數(shù)，滿足 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)-冒泡排序網(wǎng)絡(luò) 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中，如果存在兩個(gè)非空集合X，Y，使得V(G)=X∪Y，X∩Y=?且G中的任意一條邊的兩個(gè)端點(diǎn)不能同時(shí)屬于X或Y，則稱圖G為二部圖或者偶圖。若X的每個(gè)頂點(diǎn)和Y的每個(gè)頂點(diǎn)相連，稱G為完全偶圖。若|X|=m，|Y|=n，對(duì)應(yīng)的完全偶圖記為Km，n。當(dāng)m=1時(shí)，我們把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。假設(shè)V1是V的一個(gè)非空子集，以V1為頂點(diǎn)集，以兩端點(diǎn)均在V1中的邊的全體為邊集所構(gòu)成的子圖，稱為G的由V1導(dǎo)出的子圖，記為G[V1]。若圖G和圖H同構(gòu)，記為G?H。設(shè)v是圖G的一個(gè)頂點(diǎn)，G中所有與v相鄰的點(diǎn)的集合記為N(v)。

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

4 結(jié)論

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