由2-树生成的Cayley图的容错极大局部连通性

罗祖文,徐丽琼

(集美大学理学院，福建 厦门 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]等。

通常衡量一个互连网络好坏的标准是:对称性,可扩展性,短直径,简单方便的最优路由,递归结构,平行路的存在性等。Cayley网络作为一种正则、点对称的互连网络倍受人们的青睬,它在计算机互连网络的设计与分析中起着重要的作用。基于此,本文主要研究由2-树生成的Cayley图的容错极大局部连通性和容错一对多极大局部连通性。

1 预备知识

在设计和选择互连网络拓扑结构时,要考虑的一个重要问题是它的可靠性,而图的连通度是衡量网络可靠性的最重要参数之一。对于图的连通度,Menger[10]从局部的角度出发,定义任意两个顶点的局部连通度κ(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循环生成图,或简称为AGn的生成图。AGn的生成图是一棵特殊的2-树。

当Γ是交错群An,生成图是一般的2-树时,称Γ(Δ)为由2-树T2,n生成的Cayley图,记为An(Δ)[12]。由2-树生成的Cayley图是交错群图的推广。由2-树生成的Cayley图的生成集Δ里有2n-4个3循环,所以Γ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条内部顶点不交路连接。由于网络中故障的发生是不可避免的,下面对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个故障点,结果并不能被保证。在大多数情况下,所有故障都发生在一个顶点身上概率很小,所以限制每个顶点有至少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)极大局部连通,网络容错性相应增加。本文主要研究的是网络中处理器发生问题(去点)的情况,如果通讯线路发生问题(去边)，是否也能有相应的结果呢?这将是一个值得研究的问题。