k阶限制边连通度的最优性和超级性

来源 :山东师范大学 | 被引量 : 3次 | 上传用户:gksword
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的限制性边连通度问题及许多理论都是源自大型网络的设计和可靠性分析.另外限制性边连通度在实际问题中有着广泛的应用,是图论研究中一个很活跃的课题,各类限制边连通度问题被相继提出并加以发展、应用。 如果不是特别说明,文中谈及的所有图都是简单连通的,当研究网络可靠性的时候,经常考虑这样一种图模型,它的节点不失效,但是它的连线,也就是边可以独立地等可能地失效,失效的概率是p∈(0,1).令G是一个网络模型,边数为h的边割的数目用Ch表示,如果G恰好有e条边,则它不连通的概率P(G,p)就可以表示为:显然,P(G,p)的值越小,网络的可靠性越好,如果能确定所有的系数Ch,那么这个网络的可靠性就是确定的.但是对于任意图,Provan和Ball在文献[1]中指出,确定所有的系数Ch是一个NP—困难问题。 用Ω(n,e)表示n个点e条边的图的集合,当p充分小时,在Ω(n,e)中为了最小化P(G,p),边连通度λ(G)起了非常重要的作用,当p充分小时,对G1,G2∈Ω(n,e),如果λ(G1)>λ(G2),则P(G1,p)<P(G2,p)[5].为了更准确地确定这个可靠性,Esfahanian和Hakimi在文献[14]中引入了限制边割和限制边连通度.Fabrega和Fiol将限制边连通度的概念进一步推广,提出了k阶限制边割和k阶限制边连通度的概念[16].目前,对于它已经有了广泛而深入的研究。 第一章,介绍了研究背景和已有的一些结果,以及所涉及的一些概念、术语和符号,记G=(V,E)是一个简单连通图,其中V(G)表示G的顶点集且E(G)表示G的边集,我们记n(G)=|V|.对X()V(G),G[X]表示由X导出的子图,—X= V(G)—X,[X,—X]表示G中一端在X中,一端在—X中的边的集合.给定n(≥2k)阶图G的一个边集S,若G—S不连通且它的每个分支的阶至少为k,则称S为G的一个k阶限制边割,简称为Rk—边割.若G有Rk—边割,则称G是λk—连通的,且G的最小Rk—边割(叫λk—边割)所含边数称为G的k阶限制边连通度,记为λk(G).显然,λ(G)=λ1(G)≤λ2(G)≤…≤λk(G).设X()V(G),()(X)=|[X,—X]|记ξk(G)=min{()(X):|X|=k,G[X]连通}.易见ξ1(G)=δ(G),其中δ(G)为G的最小度,称一个图G是λk—最优的,若λk(G)存在且λk(G)=ξk(G).称图G是超级—λk连通图,若G的每个λk—割都分离一个k阶连通子图。 第二章主要考虑去掉图中一个三阶连通子图后的情形,即研究λ3,q—连通图的性质,并使[26]中结果成为本文主要结果的推论。 第三章,主要研究图的三阶和四阶限制边连通度的最优性和超级性.给出了:图是λ3—最优及超级—λ2连通的最小度条件,图是λ4—最优及超级—λ3连通的最小度条件,以及图是λ4—最优及超级—λ4连通的度和条件。 第四章,将给出k阶限制边连通度的最优性的一个度序列条件.主要得到以下结论; 1.令n,q为正整数且n≥max{7,q+3},q≥3。(1)—个阶为n≥2q-1的图G非λ3,q—连通当且仅当G∈W*n.(2)—个阶为n=2q—2的图G非λ3,q—连通当且仅当G∈{W*n,R*(q-1,0,q─1)}.(3)一个阶为n=2q—3的图G非λ3,q—连通当且仅当G∈{W*n,S*(q-1,0,q—2),S*(q—2,1,q—2),R*(q—2,1,q—2)}.其中,新构造图的定义详见定义2.1和定义2.2。 2.令t,r为整数且t≥1,0≤r≤5,令q=6t+r,若G为n阶连通图,n≥q+3,使得G含长为l的圈C满足l≥3t+5,则G是λ3,q—连通的。 3.设G是一个n阶连通图,n≥10且δ(G)≥[n/2]—2,若G中每个四圈C上都存在一点w使得d(w)≥[n/2]+2,则G是λ3—最优的.进而,若G中每个三角形T上都存在一点钐使得d(u)≥h/2J,则G是超级—A2连通的。 4.设G是一个n阶λ4—连通图,n≥11且δ(G)≥|n/2|—3.若G中每个导出五圈上及两个三角形的粘合图除粘合点外都存在一点u使得d(u)≥[n/2]-1,每个导出四圈上都存在一点v使得d(v)≥[n/2]+1且每个K4—e上都存在一点w使得d(w)≥[n/2]+3,则G是λ4—最优的.进而,若n≥12,则G是超级—λ3连通的。 5.设G是一个n≥11阶λ4—连通图,若G满足以下条件,则G是λ4—最优的.(1)G中任意使得d(x,y)=t的两点x,y都有d(x)+d(y)≥2[n/2]—2t+1(t=2,3,4)。(2)每个导出四圈上都存在一点u使得d(u)≥[n/2]+1。(3)每个K4—e上都存在一点v使得d(v)≥[n/2]+3。 6.设G是一个n≥11阶连通图,若G满足以下条件,则G是超级—λ4连通的.(1)G中任意使得d(x,y)=t的两点x,y都有d(x)+d(y)≥2[n/2]—2t+3(t=2,3,4)。(2)每个导出四圈上都存在一点u使得d(u)≥[n/2]+2。(3)每个K4—e上都存在一点v使得d(v)≥[n/2]+4。 7.设G=(V,E)为n阶λAk—连通图,其围长g>k+l.如果对G的任意连通子图H都有|E(H)|≤|V(H)|2/g,λk(G)≤ξk(G)且G的度序列d1≥d2≥…≥dn=δ满足则G是λk—最优的。
其他文献
语文考试时,作文写得好坏与平素作文训练过程里有没有注意让学生学会创新选材有直接关系,所以,作文训练一定要把这个环节落到实处.本文对考场作文训练中创新选材的问题进行了
本文在研究偏微分方程数值解法时,采用了两种新型的有限元方法,一种是交替方向有限元法,其基本思想是:将交替方向与Galerkin方法相结合,通过算子分裂技术,把高维问题转化为一系列低
信息技术自其兴起,直至推广,正在影响着人们日常生产、生活的方方面面。与此同时,信息技术也在逐渐地渗透到教育领域中。随着中学数学课程理念的推进,信息技术与中学数学课程整合
事物发展过程的瞬时突变通常称之为脉冲现象.脉冲现象在现代科技的各领域的实际问题中是普遍存在的,其数学模型往往可归结为脉冲微分系统.脉冲微分系统最突出的特点是能够充分
12010年农药进出口情况分析2010年我国农药进出口量为126.13万吨,比去年同期增长14.3%;进出口额为52.92亿美元,比去年同期增长14.6%;农药进出口总量、进出口总额实现 Analys
兴趣是提高教学质量的调味剂,目的在于启发学生学习的积极性.在数学教学中,要想真正达到教学目的,就一定要解决学生的兴趣问题,当学生对这门课产生强烈的兴趣,让他觉得有意思
本文着重研究了制度质量和考虑政府支出的财政政策的内生经济增长模型。第一章简要阐述了内生经济理论的演变过程及制度质量和财政政策理论的研究背景。第二章以Erlich和Lui(JPE)的内生经济增长模型为基础,改进了模型,在效用函数中加进了参与者的官僚腐败被发现时的消费额,提出了一个关于参与者可选择人力资本和政治资本来进行投资的新的增长模型,分析了官僚腐败、司法腐败、制度质量和经济增长之间的关系。第三章
本文针对自回归滑动平均(ARMA)过程的参数估计和定阶,把Box-Jenkins方法和BIC准则与系统的定阶方法加以结合,详细地介绍了基于线性估计和自回归定阶准则的方法(ARCRI)和公因
在高中物理实验学习中,其对学生具有不可忽视的影响,不但可以提升学生的创新能力和兴趣,而且可以提升学生的团队合作能力,对于学生后期的发展奠定了坚实的基础.本文主要对高
本文主要研究了由两个集值映射及一集合定义的广义扰动映射的导数,给出其导数的表达式。其中导数的定义是由通常的几何观点引入的。也即,集值映射在一点导数的图像等于该集值映