论文部分内容阅读
图的条件连通度是除了点连通度之外的另外一种探索网络结构的方法,在研究网络图容错率中有很多应用。对一个连通图G=(V,E),点集F(C)V记作G的Rk点割如果G-F不连通且V-F中的每一个点在G-F中至少有k个邻点。我们用κk(G)表示图G所有的Rk点割中元素最少的集合的大小。 凯莱图在互联网络中有很好的属性,如点对称性、边对称性、层次结构可分解、高容错度等,因此凯莱图研究在设计和分析网络方面有很多的应用。令Sym(n)是基于{1,2,…,n}的对称群,T是Sym(n)中的一个置换集,图G(T)由点集{1,2,…,n}和边集{ij:(ij)∈T}构成。如果G(T)是轮图,那么我们简单地将凯莱图Cay(Sym(n),T)记作WGn。 图的广义连通度是图的连通度的另一种自然推广,常被用作衡量网络G的稳定性。给定图G=(V,E)和顶点数大于等于2的顶点集合S(C)V,若i≠j且1≤i,j≤r,则图G中满足V(Ti)∩ V(Tj)=S的边不交的树T1,T2,…,Tr叫做S斯坦纳树,我们用κG(S)表示图G中S斯坦纳树数量的极大值。对于满足2≤k≤n的正整数k,图G的广义k连通度κk(G)定义为κk(G)=min{κG(S)|S(C)V(G),|S|=k},也就是说,κk(G)是κG(S)在取遍G中所有的k元顶点子集S后的最小值。 本文,我们探索了由轮图所生成的凯莱图(记作WGn)的κ1(WGn)和κ2(WGn)值;探索了凯莱图冒泡星图(记作BSn)的广义3连通度κ3(BSn)值,并分别证明了在n≥5时κ1(WGn)=4n-6,κ2(WGn)=8n-18,在n≥3时κ3(BSn)=2n-4。