馬芳玲,原 軍

(太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院,太原 030024)

1 介紹

本文用具有頂點(diǎn)集V(G)和邊集E(G)的無(wú)向簡(jiǎn)單圖G來(lái)表示互連網(wǎng)絡(luò)。對(duì)于簡(jiǎn)單圖而言,定義為沒(méi)有環(huán),且其中任意兩條連桿沒(méi)有同時(shí)連接在相同的一對(duì)頂點(diǎn)。完全圖定義為任意一對(duì)不同的頂點(diǎn)它們之間總會(huì)有一條邊連接的簡(jiǎn)單圖。從同構(gòu)的角度分析,由n個(gè)頂點(diǎn)組成的完全圖,有且只有一個(gè),記作Kn.完全圖K5如圖1(a)所示。由頂點(diǎn)集X1,X2,…,Xl組成的簡(jiǎn)單圖定義為完全l部圖,圖中的所有的頂點(diǎn),均與在不同子集中的其他頂點(diǎn)相互連接;若|X1|=x1,|X2|=x2,…,|Xl|=xl,則這樣的圖記為T(mén)(x1,x2,…,xl).圖1(b)是完全二部圖T(3,3).

圖1 完全圖Fig.1 A complete graph

對(duì)于兩個(gè)頂點(diǎn)u,v∈V(G), 如果u和v是彼此相鄰的,那么存在一條邊e,使得e=uv.對(duì)于任意頂點(diǎn)v,它的度dG(v)是與v本身相關(guān)聯(lián)的邊數(shù)。一個(gè)圖G,如果對(duì)于任何頂點(diǎn)v,都有dG(v)=k,則這個(gè)圖為k正則的。對(duì)于圖G中任意頂點(diǎn)v,鄰集NG(v)被視作為v的鄰點(diǎn)的集合。如果鄰集和度的記號(hào)未出現(xiàn)符號(hào)混淆,則可以省略其下標(biāo)。V中的一個(gè)子集S,在G中如果滿足任意兩個(gè)頂點(diǎn)都不相鄰,那么稱(chēng)S是G中的一個(gè)獨(dú)立集。G中的一個(gè)獨(dú)立集S被稱(chēng)為G中的最大獨(dú)立集,則滿足不再存在獨(dú)立集S′,使得|S′|>|S|成立。這里沒(méi)有定義的圖的術(shù)語(yǔ)和符號(hào)將遵循文獻(xiàn)[1].

設(shè)V(G)中任一子集V′,用G-V′來(lái)表示,從G中刪去V′的全部頂點(diǎn)所得到的圖。在連通圖G中,使得G-V′不連通的頂點(diǎn)集V′,為圖G的一個(gè)頂點(diǎn)割。 其中含k個(gè)元素的頂點(diǎn)割,被稱(chēng)為k頂點(diǎn)割。完全圖是沒(méi)有頂點(diǎn)割的;在有一對(duì)以上相異的且不相鄰頂點(diǎn)的G中,G的連通度為k頂點(diǎn)割中最小的k,記作к(G);若G的連通度不為最小的k值,則к(G)定義為|V(G)|-1.

連通度是度量互連網(wǎng)絡(luò)的可靠性的一個(gè)重要參數(shù)指標(biāo)。通常,互連網(wǎng)絡(luò)的可靠性程度可以用它所對(duì)應(yīng)的圖的連通性來(lái)衡量。但是,用連通度衡量互連網(wǎng)絡(luò)的可靠性某種程度上是存在缺陷的[2],因?yàn)檫B通度假設(shè)圖的任何子集中的所有元素都可能同時(shí)失效。鑒于此,Harary在文獻(xiàn)[3]中通過(guò)提出條件連通度的概念,對(duì)這些缺陷進(jìn)行了彌補(bǔ)。為了讓他們擁有預(yù)先得到的性質(zhì),Harary的條件連通度的理念是限制G-V′的分支?；谶@一思想,研究人員對(duì)經(jīng)典的連通度進(jìn)行了推廣,提出了超連通度。

超連通度的定義是Francis T.Boesch[4]和A.-H.Esfahanian[5]提出的。如果頂點(diǎn)割S被稱(chēng)為超頂點(diǎn)割,當(dāng)且僅當(dāng)G-S斷開(kāi)連接且沒(méi)有孤立頂點(diǎn)。這個(gè)定義意味著對(duì)于任意u∈V(G-S),有NG(u)?S.超連通度κ′是所有超頂點(diǎn)割的最小基數(shù),如果有的話,κ′(G)=min{|S|):S?V(G)是G的超頂點(diǎn)割}.Fébrega和Fiol在文獻(xiàn)[6]中對(duì)具有大圍長(zhǎng)圖的超連通度進(jìn)行了深入的剖析。圖的超連通度已經(jīng)被一大批學(xué)者所研究與探索,參見(jiàn)文獻(xiàn)[7-8].

給定任意兩個(gè)圖G1和G2,G1和G2的Kronecker積G1×G2是具有頂點(diǎn)集V(G1×G2)=V(G1)×V(G2)和邊集E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)}的圖。圖2為一個(gè)圖G和K2的Kronecker積,其中V(G)={u1,u2,u3,u4,u5},V(K2)={v1,v2}.

圖2 Kronecker積(G×K2)Fig.2 The Kronecker product (G×K2)

圖的Kronecker積在圖著色、圖識(shí)別和分解、圖嵌入、匹配理論和圖的可靠性等方面有著廣泛的應(yīng)用[9-10]。因此,圖的Kronecker積得到了很多學(xué)者的關(guān)注。

在圖的Kronecker積的連通度這一研究領(lǐng)域,Miller[11]和Weichsel[12]對(duì)兩個(gè)連通圖的Kronecker積的連通度問(wèn)題開(kāi)展了研究,對(duì)于兩個(gè)完全圖,其Kronecker積的連通度被Mamut和Vumar[13]確定,完全圖和二部圖的Kronecker積的連通度已由Guji和Weichsel給出[14]。

這些結(jié)果在文獻(xiàn)[15]中得到了推廣。文獻(xiàn)[14]還推導(dǎo)出了任意圖與階大于等于3的完全圖的Kronecker積的連通度公式。有關(guān)圖的Kronecker積的更多報(bào)告參考文獻(xiàn)[16-19].

2 圖的Kronecker積的超連通度

在本節(jié)討論了完全圖和完全多部圖的Kronecker積的超連通度。

對(duì)于劃分為(X1,X2,…,Xl)的多部圖G和完全圖Kn(n≥2), 令V1=V(G)={u1,u2,…,um},V2=V(Kn)={v1,v2,…,vn}.對(duì)于1≤i≤m,1≤j≤n,令Sj=V1×{vj},X1j=X1×{vj},X2j=X2×{vj},…,Xij=Xi×{vj},…,Xlj=Xl×{vj}.頂點(diǎn)(ui,vj)簡(jiǎn)寫(xiě)為wij,其中i∈{1,2,…,m},j∈{1,2,…,n}.這意味著對(duì)于任意j∈{1,2,…,n},集合Sj=X1j∪X2j∪…∪Xlj={w1j,w2j,…,wij,…,wmj}是G×Kn中的一個(gè)獨(dú)立集,且V(G×Kn)有一個(gè)劃分V(G×Kn)=S1∪S2∪S3∪…∪Sn.

定理1[12]設(shè)G1和G2為連通圖。圖H=G1×G2是連通的當(dāng)且僅當(dāng)G1或G2包含一個(gè)奇圈。

引理1[12]設(shè)G連通圖。如果G沒(méi)有奇圈,那么G×K2恰好有兩個(gè)同構(gòu)于G的連通分支。

完全l部圖是頂點(diǎn)集劃分為X1,X2,…,Xl的一個(gè)簡(jiǎn)單圖,設(shè)T(x1,x2,…,xl)是滿足|Xi|=xi的完全多部圖,Kn為V(Kn)={v1,v2,…,vn}的完全圖。

引理3設(shè)S是V(T(x1,x2,…,xl)×Kn)的子集,至少三個(gè)不同的i值,i∈{1,2,…,n},使得SiS≠?.如果(T(x1,x2,…,xl)×Kn)-S沒(méi)有孤立的頂點(diǎn),則它是連通的。

證明假設(shè)存在滿足給定條件的S,至少三個(gè)不同的i值,i∈{1,2,…,n},使得SiS≠?.(T(x1,x2,…,xl)×Kn)-S不存在孤立頂點(diǎn),且是不連通的。

不妨設(shè)i∈{1,2,3},S1S≠?,S2S≠?,S3S≠?和一些ji∈{1,2,…,m},存在頂點(diǎn)wjii∈SiS.為了便于表示,將wjii縮寫(xiě)為wi,并考慮關(guān)于這三個(gè)頂點(diǎn)的以下三種情形。

情形1頂點(diǎn)集{w1,w2,w3}在某Xi×V(Kn)中。

不妨設(shè){w1,w2,w3}?X1×V(Kn).由于(T(x1,x2,…,xl)×Kn)-S是不連通的,將進(jìn)一步劃分為兩種子情形。

情形1.1 三個(gè)頂點(diǎn){w1,w2,w3}并不都在同一個(gè)分支中。這意味著這些頂點(diǎn)中至少有一個(gè)頂點(diǎn)與其它兩個(gè)頂點(diǎn)在不同的分支中。設(shè)C是(T(x1,x2,…,xl)×Kn)-S的一個(gè)分支且w3∈C,w1?C,w2?C.頂點(diǎn)割S必須包含不同分支中頂點(diǎn)的公共鄰點(diǎn)。由Kronecker積定義得:

w1∈X1×{v1}=X11,

w2∈X1×{v2}=X12,

w3∈X1×{v3}=X13,

因此,

NT(x1,x2,…,xl)×Kn(w1)∩NT(x1,x2,…,xl)×Kn(w3)=

NT(x1,x2,…,xl)×Kn(w2)∩NT(x1,x2,…,xl)×Kn(w3)=

即:

在這種情況下,NT(x1,x2,…,xl)×Kn(w3)?S.因此(T(x1,x2,…,xl)×Kn)-S包含一個(gè)孤立頂點(diǎn)w3.這與假設(shè)的(T(x1,x2,…,xl)×Kn)-S不存在孤立頂點(diǎn)相矛盾。

情形1.2 三個(gè)頂點(diǎn){w1,w2,w3}在同一分支中,記為C.因?yàn)?T(x1,x2,…,xl)×Kn)-S不連通,存在一個(gè)頂點(diǎn)w∈(T(x1,x2,…,xl)×Kn)-S,使得w∈V(C′),其中C′≠C.現(xiàn)在,

NT(x1,x2,…,xl)×Kn(w1)∪NT(x1,x2,…,xl)×Kn(w2)∪

因此,w∈X1×V(Kn).w代替w3,變回情形1.1,由情形 1.1推出矛盾。

情形2{w1,w2,w3}中存在兩個(gè)頂點(diǎn)在某Xi×V(Kn)中,另一個(gè)頂點(diǎn)在Xj×V(Kn)中,其中j≠i.不妨設(shè){w1,w2}?X1×V(Kn),以及w3∈X2×V(Kn).在這種情況下,因?yàn)?

w1=wji1∈X1×{v1}=X11,

w2=wji2∈X1×{v2}=X12,

w3=wji3∈X2×{v3}=X23,

假設(shè):

w1=wj11=(uj1,v1),

w2=wj22=(uj2,v2),

w3=wj33=(uj3,v3),

其中uj1,uj2∈X1,uj3∈X2.所以{w1,w2}?NT(x1,x2,…,xl)×Kn(w3),顯然它們?cè)谕环种е?記為C.因?yàn)?T(x1,x2,…,xl)×Kn)-S不連通,故存在一個(gè)頂點(diǎn)w∈(T(x1,x2,…,xl)×Kn)-S,使得w∈V(C′),其中C′≠C.現(xiàn)在,因?yàn)?/p>

所以:

w?NT(x1,x2,…,xl)×Kn(w1)∪NT(x1,x2,…,xl)×Kn(w2)∪

這樣w∈X13?X1×V(Kn).w代替w3,變回情形1.1,由情形1.1推出矛盾。

情形3{w1,w2,w3}中的每個(gè)頂點(diǎn)都在不同的Xi×V(Kn).假設(shè){w1}?X1×V(Kn),

{w2}?X2×V(Kn),{w3}?X3×V(Kn).在這種情況下,因?yàn)?

w1=wji1=(uji,v1)∈X1×{v1}=X11,

w2=wji2=(uji,v2)∈X2×{v2}=X22,

w3=wji3=(uji,v3)∈X3×{v3}=X33,

3 結(jié)束語(yǔ)