羅祖文,徐麗瓊

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

0 引言

互連網絡通常以圖為模型,其中圖的頂點和邊分別對應互連網絡的處理器和通信線路。設G=(V(G),E(G))是一個無向圖,其中V(G)和E(G)分別表示圖G的頂點集和邊集。對于圖G中任意一頂點u,用NG(u)表示G中與u相鄰的頂點的集合。頂點u的度dG(u)表示在G中與u相鄰的頂點的數目,度為0的頂點稱為孤立點,δ(G)表示圖G的最小度。設x,y是圖G中兩個不相鄰的頂點,則x-y-點割是指V(G){x,y}的一個頂點子集S,使得x和y屬于G-S的不同連通分支。圖G的連通度κ(G)是指最小的頂點數k使得刪除這些頂點后圖G不連通或者只有一個頂點。若κ(G)≥k,則稱G是k連通。若κ(G)=δ(G),則稱G為極大連通圖。k-樹圖是k連通圖的一種,其有著諸多有趣的組合性質。很多NP-困難問題在有限的k-樹圖中都有多項式算法。n階k-樹圖Tk,n的遞歸定義[1]為:k個兩兩相鄰的頂點構成k-樹圖Tk,k,在k-樹圖Tk,n-1上任取k個兩兩相鄰的頂點,添加一個新的頂點與這k個兩兩相鄰的頂點都相鄰得到一個k-樹圖Tk,n。k-樹圖是樹的推廣,k=1時,即為樹。本文未予定義而直接使用的符號和術語見文獻[2]。

關于容錯極大局部連通和容錯一對多極大局部連通,許多互連網絡已被研究,包括超立方體[3]、折疊超立方體[4]、星圖[5]、冒泡排序圖[6]、由對換樹生成的Cayley圖[7]、冒泡排序星圖[8]和交錯群圖[9]等。

通常衡量一個互連網絡好壞的標準是:對稱性,可擴展性,短直徑,簡單方便的最優(yōu)路由,遞歸結構,平行路的存在性等。Cayley網絡作為一種正則、點對稱的互連網絡倍受人們的青睬,它在計算機互連網絡的設計與分析中起著重要的作用?；诖?本文主要研究由2-樹生成的Cayley圖的容錯極大局部連通性和容錯一對多極大局部連通性。

1 預備知識

在設計和選擇互連網絡拓撲結構時,要考慮的一個重要問題是它的可靠性,而圖的連通度是衡量網絡可靠性的最重要參數之一。對于圖的連通度,Menger[10]從局部的角度出發(fā),定義任意兩個頂點的局部連通度κ(u,v)為這兩個頂點之間內部頂點不交路的數目的最大值,并給出關于局部連通度的一個經典的結果,即Menger定理。

定理1[10]設x和y是圖G中兩個不相鄰的頂點,則x和y的局部連通度等于x-y-頂點割所含的最小頂點數。

結合極大連通圖和局部連通度的定義,Oh等[5，11]給出了關于極大局部連通和f-容錯極大局部連通的概念。

定義1[11]若對于圖G中任意兩個頂點u和v，都有κ(u,v)=min{d(u),d(v)},則稱圖G是極大局部連通的。

定義2[5]設f是正整數,對于圖G的任意階不超過f的頂點子集F,有G-F是極大局部連通的,則稱G是f容錯極大局部連通的。

上述定義可推廣至一個頂點對多個頂點的情況。

在G中,給定一個頂點x和一個頂點子集Y，滿足|Y|≥k,稱x到Y之間的k條終點兩兩不同的內部頂點不交路為x到Y的一個k扇。設F?V(G),G-F中存在頂點集Y，滿足|Y|≤dG-F(x),并且對任一頂點v∈Y,有{v}∪NG-F(v)Y,則稱Y為關于x和F的條件終點集,簡稱條件終點集。文獻[2]推廣Menger定理,得到如下結果。

定理2[2]設G是k連通的,x∈V(G),Y?V(G){x}滿足|Y|≥k,則在G中存在x到Y的一個k扇。

結合上述定理,Shih等[6]給出一對多形式的容錯極大局部連通的定義。

定義3[6]設F是G的頂點子集滿足|F|≤f,x∈V(G-F),Y是G-F中關于x的任意條件終點集,若在G-F中x和Y之間存在|Y|條終點兩兩不同的內部頂點不交路,則稱G為一對多f容錯極大局部連通的。

設Γ是一個有限群,Δ是Γ不含單位元的子集,定義一個有向圖G如下：它的頂點集是Γ,弧集是{(g,gs):g∈Γ,s∈Δ}。

如此定義的有向圖G稱為群Γ關于子集Δ的Cayley圖,記為Γ(Δ)。若對任意的s∈Δ,有s-1∈Δ,則此時Cayley圖為無向Cayley圖。當Γ是交錯群An,Δ={(1,2,3),(2,1,3),(1,2,4),(2,1,4),…,(1,2,n),(2,1,n)}時,稱Γ(Δ)為交錯群圖,記為AGn。方便起見,用階為n的圖來描述AGn的生成集,生成集里的每一個元素(abc)及它的逆(bac)用一個三角形K3表示,如圖1所示。這種通過K3來表示生成集的元素的圖稱為AGn的3循環(huán)生成圖,或簡稱為AGn的生成圖。AGn的生成圖是一棵特殊的2-樹。

當Γ是交錯群An,生成圖是一般的2-樹時,稱Γ(Δ)為由2-樹T2,n生成的Cayley圖,記為An(Δ)[12]。由2-樹生成的Cayley圖是交錯群圖的推廣。由2-樹生成的Cayley圖的生成集Δ里有2n-4個3循環(huán),所以Γn(Δ)是一個階為n!/2的(2n-4)正則圖。當n=4時,A4(Δ)為交錯群圖AG4,如圖2所示。

在證明本文的主要結果之前,首先引用一些已證明的結論。

引理1[13]當n≥4時,由2-樹T2,n生成的Cayley圖An(Δ)是(2n-4)連通的。

引理2[13]設T是An(Δ)的頂點子集滿足|T|≤4n-12。當n≥5時,An(Δ)-T滿足下述條件之一：1)An(Δ)-T是連通的；2)An(Δ)-T有2個分支,其中一個分支是孤立點。

引理3[13]設T是An(Δ)的頂點子集滿足|T|≤6n-20。當n≥5時,An(Δ)-T滿足下述條件之一：1)An(Δ)-T是連通的；2)An(Δ)-T有2個分支,其中一個分支是孤立點或者K2;3)An(Δ)-T有3個分支,其中2個分支是孤立點。

引理4[12]當n≥4時,An(Δ)不包含K4-e和K2,3作為其子圖。

2 主要結果及其證明

由引理1知，n≥4時,An(Δ)是極大連通圖,結合定理1可知，An(Δ)中任意一對頂點都被2n-4條內部頂點不交路連接。由于網絡中故障的發(fā)生是不可避免的,下面對An(Δ)的極大局部連通性進行容錯性分析。

引理5 設F是G=An(Δ)的頂點子集滿足|F|≤4n-13,e是G的一條邊,當n≥5時,G-F-{e}滿足下列條件之一：1)G-F-{e}是連通的；2)G-F-{e}有2個分支,其中一個分支是孤立點。

證明在G中任取一條邊e=xy,由引理2,可得x,y?F,否則引理成立。假設G-F-{e}不連通,令F′=F∪{x},則|F′|≤4n-12。由引理2,若G-F′連通,則G-F-{e}有2個分支,其中一個分支是孤立點x,滿足條件2);若G-F′不連通,由引理2,G-F′有2個分支,其中一個分支是孤立點，設為u,另一個大分支設為C,此時NG(u)?F′。下面分2種情況考慮。

情況1ux∈E(G)。

由引理4,|NG(x)∩NG(u)|≤1,從而dF(x)≤|F|-dG(u)+1+1≤2n-7,因此dC(x)≥2n-4-1-(2n-7)=2。又G-F-{e}不連通,顯然y?C。此時u=y,G-F-{e}有2個分支,其中一個分支是孤立點u,滿足條件2)。

情況2ux?E(G)。

由引理4,|NG(x)∩NG(u)|≤2,從而dF(x)≤|F|-dG(u)+2≤2n-7,因此dC(x)≥2n-4-(2n-7)=3,顯然y∈C,此時G-F-{e}有2個分支,其中一個分支是孤立點u,滿足條件2)。

定理3 設F是G=An(Δ)的頂點子集滿足|F|≤2n-7,當n≥5時,G-F中任意一對頂點u和v都被min{dG-F(u),dG-F(v)}條內部頂點不交路連接,即G是(2n-7)容錯極大局部連通的。

證明當n≥5時,設u和v是G-F中任意2個不同的頂點,令m=min{dG-F(u),dG-F(v)},則m≤2n-4。下面分2種情況用反證法證明。

情況1uv?E(G)。

假設在G-F中u和v之間不存在m條內部頂點不交路,由定理1可知,在G-F中存在一頂點子集T滿足|T|≤m-1,使得刪去這個頂點集后,得到的子圖G-F-T中u和v不連通。又|F|+|T|≤2n-7+m-1≤4n-12,由引理2知G-F-T或者連通,或者有2個分支,其中一個是孤立點。當G-F-T連通時,與u和v在G-F-T中不連通矛盾。當G-F-T不連通時,則G-F-T有2個分支,其中一個是孤立點,設為x,又在G-F-T中u和v不連通,則u=x或v=x。不失一般性，設u=x,則NG-F(u)?T,從而|T|≥dG-F(u)≥m,這與|T|≤m-1矛盾。

情況2uv∈E(G)。

假設在G-F-uv中u和v之間不存在m-1條內部頂點不交路,由定理1可知,在G-F-uv中存在一個頂點集T滿足|T|≤m-2,使得刪去這個頂點集后,得到的子圖G-F-T-uv中u和v不連通。又|F|+|T|≤2n-7+m-2≤4n-13,由引理5知,G-F-T-uv或者是連通的,或者有2個分支,其中一個是孤立點。當G-F-T-uv連通時,與u和v在G-F-T-uv中不連通矛盾。當G-F-T-uv不連通時,它有2個分支,其中一個是孤立點,設為y,又因為u和v在G-F-T-uv中不連通,則u=y或v=y。不失一般性，設u=y,則NG-F-uv(u)?T,從而|T|≥dG-F-uv(u)≥m-1,這與|T|≤m-2矛盾,定理得證。

當n≥5時,給出一個例子說明定理3中的容錯極大局部連通性的結果是緊的。由2-樹生成的Cayley圖G的構造可知G包含K3作為其子圖,如圖3所示,設u,v,w是G中兩兩相鄰的3個頂點,由引理4可知u,v只有一個公共鄰點w。令F=NG(u){w,v},x∈V(G)-(NG(u)∪NG(v)),則|F|=2n-6,m=min{dG-F(x),dG-F(v)}=2n-4。此時令T=NG(v){u},顯然T?G-F滿足|T|=2n-5=m-1,且在G-F-T中x和v不連通。由定理1,在G-F中x和v之間不存在min{dG-F(x),dG-F(v)}=2n-4條內部頂點不交路。

定理4 設F是G=An(Δ)的頂點子集滿足|F|≤2n-7,x∈V(G-F),Y是G-F-{x}中關于x的任一條件終點集,滿足|Y|=t≤dG-F(x)≤2n-4。當n≥5時,G-F中x和Y之間存在t條終點兩兩不同的內部頂點不交路,即G是一對多(2n-7)容錯極大局部連通的。

證明當n≥5時,由定理2,只需證明對于任意的T?V(G-F)滿足|T|≤t-1,在G-F-T中x與Y-T之間有一條路即可。用反證法證明,假設在G-F-T中x與Y-T不連通,則G-F-T不連通,又|F|+|T|≤4n-12,由引理2，G-F-T包含一個大分支C和一個孤立點u。所以NG-F(u)?T,如果x=u,則|T|≥dG-F(x)≥t,與|T|≤t-1矛盾。如果x∈C,則u∈Y-T。如果|Y∩T|=t-1,有T?Y,則{u}∪NG-F(u)?Y,與Y是一個條件終點集矛盾。所以|Y∩T|≤t-2,則(Y-T)∩C≠?。令u′∈(Y-T)∩C,然而在G-F-T中x與u′之間存在一條路,與在G-F-T中x與Y-T不連通矛盾。證畢。

當n≥5時,給出一個例子說明定理4中的一對多容錯極大局部連通性的結果是緊的。如圖3所示,設u,v,w是由2-樹生成的Cayley圖G中兩兩相鄰的3個頂點,由引理4可知，u,v只有一個公共鄰點w。令F′=NG(u) {w,v},Y={v}∪(NG(v){w}),x∈V(G)-(NG(u)∪NG(v)),則|F′|=2n-6,Y?G-F′滿足|Y|=t=dG-F′(x)=2n-4。顯然Y是關于x和F′的條件終點集,此時令T′=(Y{u,v})∪{w},則|T′|=t-1且在G-F′-T′中x與{u,v}不連通。由定理2,在G-F′中x和Y之間不存在t=2n-4條終點兩兩不同的內部頂點不交路。

由定理3可知,An(Δ)是(2n-7)容錯極大局部連通的,但是若在同一頂點處存在2n-6個故障點,結果并不能被保證。在大多數情況下,所有故障都發(fā)生在一個頂點身上概率很小,所以限制每個頂點有至少3個無故障相鄰頂點。在此條件限制下,證明了由2-樹生成的Cayley圖An(Δ)是(4n-15)容錯極大局部連通的。

引理6 設F是G=An(Δ)的頂點子集滿足|F|≤6n-21,e是G的一條邊,當n≥5時,G-F-{e}滿足下列條件之一：1)G-F-{e}是連通的；2)G-F-{e}有2個分支,其中一個分支是孤立點或者K2;3)G-F-{e}有3個分支,其中2個分支是孤立點。

證明在G中任取一條邊e=xy,由引理3,可得x,y?F,否則定理成立。假設G-F-{e}不連通,令F′=F∪{x},|F′|≤6n-20。若G-F′連通,則G-F-{e}有2個分支,其中一個分支是孤立點x,滿足條件2)。若G-F′不連通,由引理3,下面分3種情況考慮。

情況1G-F′有2個分支,其中一個是孤立點u,另一個是大分支C。

若ux∈E(G)。由于dG(x)=2n-4,此時對dC(x)進行討論。若dC(x)=0,此時u=y,則G-F-{e}有3個分支,其中2個分支分別是孤立點x和孤立點u,滿足條件3)。若dC(x)=1,當u=y時,G-F-{e}有2個分支,其中一個分支是孤立點u,滿足條件2),當u≠y時,則y∈C,此時G-F-{e}有2個分支,其中一個分支是K2,滿足條件2)。若dC(x)≥2,由于G-F-{e}不連通,則u=y,此時G-F-{e}有2個分支,其中一個分支是孤立點u,滿足條件2)。

若ux?E(G)。由于ux?E(G),則y∈C,此時dC(x)≥1。若dC(x)=1,則G-F-{e}有3個分支,其中2個分支分別是孤立點x和孤立點u,滿足條件3)。若dC(x)≥2,則G-F-{e}有2個分支,其中一個分支是孤立點u,滿足條件2)。

情況2G-F′有2個分支,其中一個是K2,記為uv,另一個大分支是C。

若ux∈E(G),vx?E(G)或vx∈E(G),ux?E(G)。不失一般性,設ux∈E(G),vx?E(G)。由引理4,|NG(u)∪NG(v)|≥4n-11,則dF(x)≤|F|-(4n-11-1)+1+1≤2n-7,因此dC(x)≥2n-4-(2n-7)-1=2。由于G-F-{e}不連通,則y=u,此時G-F-{e}有2個分支,其中一個分支是K2,即uv。滿足條件2)。

若ux∈E(G)且vx∈E(G)。由引理4,dF(x)≤|F|-(4n-11-1)≤2n-9,因此dC(x)≥2n-4-2-(2n-9)=3。此時G-F-{e}連通,與假設矛盾。

若ux?E(G)且vx?E(G)。由引理4,dF(x)≤|F|-(4n-11)+2×2≤2n-6,因此dC(x)≥2n-4-(2n-6)=2。此時G-F-{e}有2個分支,其中一個分支是K2,即uv,滿足條件2)。

情況3G-F′有3個分支,其中2個是孤立點u和孤立點v,另一個大分支是C。

若ux∈E(G),vx?E(G)或vx∈E(G),ux?E(G)。不失一般性,設ux∈E(G),vx?E(G)。由引理4,|NG(u)∪NG(v)|≥4n-10,則dF(x)≤|F|-(4n-10-1)+1+2≤2n-7,因此dC(x)≥2n-4-(2n-7)-1=2。若y∈C,則G-F-{e}有2個分支,其中一個分支是孤立點v,滿足條件2)。若y=u,則G-F-{e}有3個分支,其中2個是孤立點u和v,滿足條件3)。

若ux∈E(G)且vx∈E(G)。由引理4,dF(x)≤|F|-(4n-10-1)+1+1≤2n-8,因此dC(x)≥2n-4-(2n-8)-2=2。由于G-F-{e}不連通,則y∈{u,v},不失一般性,令y=u,此時G-F-{e}有2個分支,其中一個分支是孤立點u,滿足條件2)。

若ux?E(G)且vx?E(G)。由引理4,dF(x)≤|F|-(4n-10)+2×2≤2n-7,因此dC(x)≥2n-4-(2n-7)=3。顯然y∈C,則G-F-{e}有3個分支,其中2個分支是孤立點u和v,滿足條件3)。

定理5 設F是G=An(Δ)的頂點子集滿足δ(G-F)≥3且|F|≤4n-15,當n≥5時,G-F中任意一對頂點x和y都被min{dG-F(x),dG-F(y)}條內部頂點不交路連接。

證明當n≥5時,設x和y是G-F中任意2個不同的頂點,令m=min{dG-F(x),dG-F(y)},則3≤m≤2n-4。下面分2種情況用反證法證明。

情況1xy?E(G)。

假設在G-F中x和y之間不存在m條內部頂點不交路,由定理1可知,在G-F中存在一頂點子集T滿足|T|≤m-1,使得刪去這個頂點集后,得到的子圖G-F-T中x和y不連通。又|F|+|T|≤4n-15+m-1≤6n-20,由引理3：

1)若G-F-T有2個分支,其中一個分支是孤立點u,另一個大分支是C。由于G-F-T中x和y不連通,不失一般性,令x=u,y∈C,顯然NG(x)?F∪T,因此|T|≥dG-F(x)≥m,與|T|≤m-1矛盾。

2)若G-F-T有2個分支,其中一個分支是K2,記為uv,另一個大分支是C。由于G-F-T中x和y不連通,不失一般性,令x=u,y∈C,顯然NG(x)?F∪T∪{v},于是m-1≥|T|≥dG-F(x)-1≥m-1,因此|T|=m-1,NG-F(x)=T∪{v},又由引理4,|NG(x)∩NG(v)|≤1,則dG-F(v)≤2,與δ(G-F)≥3矛盾。

3)若G-F-T有3個分支,其中2個是孤立點u和v,另一個大分支是C。由于G-F-T中x和y不連通,若{x,y}={u,v},不失一般性,令x=u,y=v,顯然NG-F(x)∪NG-F(y)?T,由引理4,2m-2≤dG-F(x)+dG-F(y)-2≤|T|≤m-1,與m≥3矛盾。若x∈{u,v},y∈C,不失一般性,令x=u,y∈C,顯然NG-F(x)∪NG-F(v)?T,又dG-F(v)≥3,由引理4,m+3-2≤dG-F(x)+dG-F(v)-2≤|T|≤m-1,矛盾。

情況2xy∈E(G)。

假設在G-F-xy中x和y之間不存在m-1條內部頂點不交路,由定理1可知,在G-F-xy中存在一頂點子集T滿足|T|≤m-2,使得刪去這個頂點集后,得到的子圖G-F-T-xy中x和y不連通。又|F|+|T|≤4n-15+m-2≤6n-21，由引理6：

1)若G-F-T-xy有2個分支,其中一個分支是孤立點u,另一個大分支是C。由于G-F-T-xy中x和y不連通,不失一般性,令x=u,y∈C,顯然NG(x)?F∪T∪{y},因此|T|≥dG-F(x)-1≥m-1,與|T|≤m-2矛盾。

2)若G-F-T-xy有2個分支,其中一個分支是K2,記為uv,另一個大分支是C。由于G-F-T-xy中x和y不連通,不失一般性,令x=u,y∈C,顯然NG(x)?F∪T∪{v,y},于是m-2≥|T|≥dG-F(x)-2≥m-2,因此|T|=m-2,NG-F(x)=T∪{v,y},又由引理4,|NG(x)∩NG(v)|≤1,則dG-F(v)≤2,與δ(G-F)≥3矛盾。

3)若G-F-T-xy有3個分支,其中2個是孤立點u和v,另一個大分支是C。由于G-F-T-xy中x和y不連通,若{x,y}={u,v},不失一般性,令x=u,y=v,顯然NG-F(x)∪NG-F(y)?T∪{x,y},由引理4,2m-1≤dG-F(x)+dG-F(y)-1≤|T|+2≤m,與m≥3矛盾。若x∈{u,v},y∈C,不失一般性,令x=u,y∈C,顯然NG-F(x)∪NG-F(v)?T∪{y},又dG-F(v)≥3,由引理4,m+3-2≤dG-F(x)+dG-F(v)-2≤|T|+1≤m-1,矛盾。

3 結論

本文研究了由2-樹生成的Cayley圖的極大局部連通容錯性,當刪除不超過2n-7個頂點時,導出子圖中任意一對頂點x和y都被min{d′(x),d′(y)}條內部頂點不交路連接,d′(x),d′(y)分別表示頂點x和y在頂點刪除圖中的度。同時,也證明了由2-樹生成的Cayley圖是一對多(2n-7)極大局部連通。進一步,如果每個頂點都被限制至少有3個無故障鄰點,由2-樹生成的Cayley圖是(4n-15)極大局部連通,網絡容錯性相應增加。本文主要研究的是網絡中處理器發(fā)生問題(去點)的情況,如果通訊線路發(fā)生問題(去邊)，是否也能有相應的結果呢?這將是一個值得研究的問題。