增廣立方體的分支連通度

張其凡，徐麗瓊

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

0 引言

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

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

增廣立方體是超立方體的眾多變形網絡中的一種,它不僅保持了超立方的一些優秀屬性,比如高對稱性和遞歸性等,而且擁有某些比超立方體更好的性質,比如它的連通度幾乎是超立方體的兩倍。增廣立方體連通度的優越性能吸引了不少專家與學者對其可靠性的廣泛研究。基于此,本文主要研究了增廣立方體的分支連通度。

1 預備知識

設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關聯的邊。對于圖G中任意一個非空頂點集F,用G-F表示從G中刪去F中的頂點以及與這些頂點相關聯的邊所得到的子圖。任取圖G中的一個頂點u,用NG(u)表示G中與u相鄰的所有頂點的集合,記為NG(u)={v∈V(G)：uv∈E(G)},dG(u)=|NG(u)|表示頂點u在圖G中的度。對于圖G中任意一個非空頂點集S,用|S|表示集合S中元素的個數,用NG(S)表示G中與S相鄰的頂點的集合,記為NG(S)=∪v∈SNG(v)S。本文未予定義而直接使用的符號和術語見文獻[10]。下面給出一些基本定義、引理及定理。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 主要結果及其證明

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

證明對n進行歸納。當n=4時,由引理9知結論成立。假設當n≥5時,結論對n-1維增廣立方體成立。下面證明結論對n維增廣立方體成立。

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

證明對n進行歸納。當n=9時,由引理10知結論成立。假設當n≥10時,結論對n-1維增廣立方體成立。下面證明結論對n維增廣立方體成立。

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

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

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

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

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

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

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

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

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

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

3 結論

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