网络图的两个可靠性参数

来源 :北京化工大学 | 被引量 : 0次 | 上传用户:tjmaomaoxiong
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的条件连通度是除了点连通度之外的另外一种探索网络结构的方法,在研究网络图容错率中有很多应用。对一个连通图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。
其他文献
线性矩阵方程的求解问题是近年来数值代数领域重点研究的问题之一.它在参数识别,自动控制理论,勘测,遥感学领域都有着广泛的应用.正是由于不同的领域,不同的背景,不同的约束
遗传算法是一种模拟自然界生物进化的智能优化算法,由于它简单易行、鲁棒性强,尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程,从而使它的应用范围极为广泛,并
作为一种新的信息获取方式和处理模式,无线传感器网络成为当前通信领域备受关注的研究热点.在无线传感器网络中,节点能量极其有限,补充困难.如何有效利用能量延长网络生命周
多元双小波框架的构造由于较大的自由度以及计算的复杂性,一直是小波框架研究内容的难点问题之一。通常情况下,由B样条或箱样条的加细面具得到的规范滤波器对,生成的小波系统无
学位
设f为定义在区域Ω?-C上的2p(p为正整数)次连续可微复值函数.若f满足多调和方程△pf=0,其中△表示Laplace算子此处为公式则称f是多调和的.  特別的,当p=1(或者p=2)时,f称为调
我国是世界上受泥石流灾害威胁最为严重的国家之一。泥石流灾害平均每年导致数百人死亡,造成多达数十亿元的直接经济损失,严重威胁到国民经济和社会的可持续发展。泥石流灾害预测在泥石流防灾减灾实践中具有重要的意义,可直接服务于国民经济建设。其影响因素众多且关系复杂,随着我国经济的发展,泥石流所造成的经济损失随势而增。因此,泥石流预测作为一重要减灾手段,是减灾研究的热点和关键问题。人工神经网络用于灾害预测的模
函数型数据统计分析开始于生长曲线分析、分类学、生物力学、医学等领域,基于函数型数据的非参数统计推断理论、方法与应用研究是在最近十年来发展起来的。由于相关学科领域中