張其凡，徐麗瓊

(集美大學(xué)理學(xué)院，福建 廈門 361021)

0 引言

互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)通常用一個連通圖來表示,其中用頂點來代表處理器,邊來代表連接線。連通度與邊連通度是衡量網(wǎng)絡(luò)容錯性的重要參量。但是，隨著大規(guī)模網(wǎng)絡(luò)的不斷發(fā)展,傳統(tǒng)的連通度與邊連通度已經(jīng)不能準(zhǔn)確地衡量網(wǎng)絡(luò)的容錯性。利用傳統(tǒng)的連通度來衡量網(wǎng)絡(luò)的容錯性有以下3個缺點：首先,對于兩個不同的網(wǎng)絡(luò),即使它們具有相同的連通度或者邊連通度,它們也不一定具有相同的網(wǎng)絡(luò)可靠性,因為對于不同的網(wǎng)絡(luò)而言,每條邊或每個頂點可能有不同的故障概率；其次,在一個圖中刪除同樣階數(shù)的頂點集或邊集,其產(chǎn)生的分支情況可能會有很大的區(qū)別，即傳統(tǒng)的連通度與邊連通度不能準(zhǔn)確地衡量網(wǎng)絡(luò)的損壞程度；最后,在用傳統(tǒng)連通度來衡量網(wǎng)絡(luò)的可靠性時,是在假定一個頂點的所有鄰點(或關(guān)聯(lián)這個頂點的所有邊)同時出現(xiàn)故障,即最壞情況下評估特定規(guī)模網(wǎng)絡(luò)的可靠性,而這一情況在現(xiàn)實世界里是幾乎不可能發(fā)生的,因此具有一定的局限性。

為了解決這一參數(shù)不足的問題,Harary[1]在1983年提出了條件連通度的概念。而后,Chartrand等[2]和Sapmpathkumar[3]在1984年又分別提出了分支連通度與分支邊連通度的概念,它們在本質(zhì)上就是對傳統(tǒng)(邊)連通度的推廣,因此也可以看作一種條件連通度。一個非完全圖G的r分支(邊)連通度cκr(G)(cλr(G))指的是在圖G中刪除最少的頂點(邊)數(shù)使一個圖不連通,并且至少有r個連通分支。其中,cκ2(G)(cλ2(G))就是所研究的傳統(tǒng)連通度與邊連通度。關(guān)于分支連通度,許多互連網(wǎng)絡(luò)已被研究,包括超立方體[4-5]、折疊超立方體[6]、扭立方體[7]、對偶立方體[8]、交錯群圖[9]等。

增廣立方體是超立方體的眾多變形網(wǎng)絡(luò)中的一種,它不僅保持了超立方的一些優(yōu)秀屬性,比如高對稱性和遞歸性等,而且擁有某些比超立方體更好的性質(zhì),比如它的連通度幾乎是超立方體的兩倍。增廣立方體連通度的優(yōu)越性能吸引了不少專家與學(xué)者對其可靠性的廣泛研究?；诖?本文主要研究了增廣立方體的分支連通度。

1 預(yù)備知識

設(shè)G=(V(G),E(G))是一個無向連通圖,其中V(G)和E(G)分別表示圖G的頂點集和邊集，用κ(G)表示圖G的連通度。對于圖G中任意兩點u、v，e=uv∈E(G)表示圖G中的任意一條邊,其中u、v稱為邊e的端點,邊e稱為與u、v關(guān)聯(lián)的邊。對于圖G中任意一個非空頂點集F,用G-F表示從G中刪去F中的頂點以及與這些頂點相關(guān)聯(lián)的邊所得到的子圖。任取圖G中的一個頂點u,用NG(u)表示G中與u相鄰的所有頂點的集合,記為NG(u)={v∈V(G)：uv∈E(G)},dG(u)=|NG(u)|表示頂點u在圖G中的度。對于圖G中任意一個非空頂點集S,用|S|表示集合S中元素的個數(shù),用NG(S)表示G中與S相鄰的頂點的集合,記為NG(S)=∪v∈SNG(v)S。本文未予定義而直接使用的符號和術(shù)語見文獻(xiàn)[10]。下面給出一些基本定義、引理及定理。

定義1[11]n維超立方體Qn的點集是定義在集合{0,1}上的n元數(shù)組,即V(Qn)={v1v2…vn:ui∈{0,1}}。Qn中的兩個頂點u=u1u2…un與v=v1v2…vn之間有邊當(dāng)且僅當(dāng)u與v的坐標(biāo)中有且僅有一個不相同。

增廣立方體是超立方體的一個變形,其遞歸定義為定義2。

下面也給出n維增廣立方體AQn的非遞歸定義3。

性質(zhì)2[14]當(dāng)n≥3時,AQn中的任意兩個頂點至多有4個公共鄰點。

引理1[13]κ(AQ1)=1,κ(AQ2)=3,κ(AQ3)=4,當(dāng)n≥4時,κ(AQn)=2n-1。

引理4[15]當(dāng)n≥4時,設(shè)F是AQn的頂點子集滿足|F|≤4n-9,則AQn-F滿足下述條件之一:1)AQn-F是連通的;2)AQn-F有兩個分支,其中一個分支是孤立點。

引理5[15]當(dāng)n≥6時,設(shè)F是AQn的頂點子集滿足|F|≤6n-18,則AQn-F有一個連通分支H滿足|V(H)|≤2n-|F|-2。

引理6[16]當(dāng)n≥6時,設(shè)F是AQn的頂點子集滿足|F|≤8n-29,則AQn-F有一個連通分支H滿足|V(H)|≤2n-|F|-3。

引理7 當(dāng)n≥3時,設(shè)x、y是AQn中任意兩個不相鄰的頂點,則|NAQn({x,y})|≥4n-6。

證明根據(jù)AQn的定義知,AQn是(2n-1)-正則的。由性質(zhì)2知,|NAQn(x)∩NAQn(y)|≤4。故|NAQn({x,y})|≥2(2n-1)-4=4n-6。

引理8 當(dāng)n≥4時,設(shè)S是AQn的一個孤立集且滿足|S|=3,則|NAQn(S)|≥6n-12。

證明對n進(jìn)行歸納。當(dāng)n=4時,易知|NAQ4(S)|≥12,結(jié)論成立。假設(shè)當(dāng)n≥5時,結(jié)論對n-1維增廣立方體成立。下面證明結(jié)論對n維增廣立方體成立。

情形1S中的3個頂點屬于同一個n-1維增廣立方體。

情形2S中的兩個頂點屬于同一個n-1維增廣立方體,另一個頂點屬于另一個n-1維增廣立方體。

綜上可得,當(dāng)n≥4時,|NAQn(S)|≥6n-12。

引理9 設(shè)F是AQ4的頂點子集滿足|F|≤9,則AQ4-F至多有兩個連通分支。

引理10 設(shè)F是AQ9的頂點子集滿足|F|≤41,則AQ9-F至多有3個連通分支。

2 主要結(jié)果及其證明

定理1 當(dāng)n≥4時,設(shè)F是AQn的頂點子集滿足|F|≤4n-7,則AQn-F至多有兩個連通分支。

證明對n進(jìn)行歸納。當(dāng)n=4時,由引理9知結(jié)論成立。假設(shè)當(dāng)n≥5時,結(jié)論對n-1維增廣立方體成立。下面證明結(jié)論對n維增廣立方體成立。

定理2 當(dāng)n≥9時,設(shè)F是AQn的頂點子集滿足|F|≤6n-13,則AQn-F至多有3個連通分支。

證明對n進(jìn)行歸納。當(dāng)n=9時,由引理10知結(jié)論成立。假設(shè)當(dāng)n≥10時,結(jié)論對n-1維增廣立方體成立。下面證明結(jié)論對n維增廣立方體成立。

子情形1 |F1|≤4n-11。

子情形2 |F1|=4n-10。

定理3 當(dāng)n≥4時,cκ3(AQn)=4n-6。

證明首先通過在AQn中構(gòu)造一個3-分支割集F滿足|F|=4n-6來證明cκ3(AQn)≤4n-6。

下面要證明cκ3(AQn)≥4n-6。由定理1知,當(dāng)n≥4時,所有的3-分支割集的大小都要大于4n-7。根據(jù)3-分支連通度的定義知,cκ3(AQn)≥4n-6。

綜上可得,當(dāng)n≥4時,cκ3(AQn)=4n-6。

定理4 當(dāng)n≥9時,cκ4(AQn)=6n-12。

證明通過在AQn中構(gòu)造一個4-分支割集F滿足|F|=6n-12來證明cκ4(AQn)≤6n-12。

下面要證明cκ4(AQn)≥6n-12。由定理2知,當(dāng)n≥9時,所有的4-分支割集的大小都要大于6n-13。根據(jù)4-分支連通度的定義知,cκ4(AQn)≥6n-12。

綜上可得,當(dāng)n≥9時,cκ4(AQn)=6n-12。

3 結(jié)論

本文主要從分支連通度研究了增廣立方體的容錯性,要使得增廣立方體不連通并且至少有3個連通分支,至少要從增廣立方體中刪去4n-6個頂點；要使得增廣立方體不連通并且至少有4個連通分支,至少要從增廣立方體中刪去6n-12個頂點。本文研究的是特殊情況,而對于一般情況,即：若要使得增廣立方體不連通并且至少有k個連通分支,至少要刪去多少個頂點？這是接下來該考慮的問題。