增廣立方體的分支連通度

張其凡，徐麗瓊

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

0 引言

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

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

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

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

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

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

引理7 當(dāng)n≥3時(shí),設(shè)x、y是AQn中任意兩個(gè)不相鄰的頂點(diǎn),則|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í),設(shè)S是AQn的一個(gè)孤立集且滿(mǎn)足|S|=3,則|NAQn(S)|≥6n-12。

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

情形1S中的3個(gè)頂點(diǎn)屬于同一個(gè)n-1維增廣立方體。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

本文主要從分支連通度研究了增廣立方體的容錯(cuò)性,要使得增廣立方體不連通并且至少有3個(gè)連通分支,至少要從增廣立方體中刪去4n-6個(gè)頂點(diǎn)；要使得增廣立方體不連通并且至少有4個(gè)連通分支,至少要從增廣立方體中刪去6n-12個(gè)頂點(diǎn)。本文研究的是特殊情況,而對(duì)于一般情況,即：若要使得增廣立方體不連通并且至少有k個(gè)連通分支,至少要?jiǎng)h去多少個(gè)頂點(diǎn)？這是接下來(lái)該考慮的問(wèn)題。