论文部分内容阅读
图的限制性边连通度问题及许多理论都是源自大型网络的设计和可靠性分析.另外限制性边连通度在实际问题中有着广泛的应用,是图论研究中一个很活跃的课题,各类限制边连通度问题被相继提出并加以发展、应用.
当研究网络可靠性的时候,经常考虑这样一种图模型,它的节点不失效,但是它的连线,也就是边可以独立地等可能地失效,失效的概率是p∈(0,1).这就是非常有名的Moore—Shannon网络模型[1,2].令G是—个Moore—Shannon网络模型,边数为h的边割的数目用Ch表示,如果G恰好有e条边,则它不连通的概率P(G,p)就可以表示为:
显然,P(G,p)的值越小,网络的可靠性越好.如果能确定所有的系数Ch,那么这个网络的可靠性就确定下来了.但是对于任意图,Provan和Ball在文献[3]中指出,确定所有的系数Ch是—个NP—困难问题,
用Ω(n,e)表示n个点e条边的图的集合,当p充分小时,在Ω(n,e)中为了最小化P(G,p)边连通度λ(G)起了非常重要的作用.Bauer et al在文献[4]中指出,当p充分小时,对G1,G2∈Ω(n,e),如果λ(G1)>λ(G2),则P(G1,p)<p(G2,p).为了更准确地确定这个可靠性,Esfahanian和Hakimi在文献[5]中引入了限制边割和限制边连通度.Fabrega和Fiol将限制边连通度的概念进一步推广,提出了k阶限制边割和k阶限制边连通度的概念[6].本文在前人工作的基础上,继续研究限制边连通度的相关性质.
在本文第一章中,我们主要介绍了文章所涉及的一些概念、术语和符号.记图G的顶点集为V(G),边集为E(G).对于x()V(G),令G[X]表示X的导出子图,—X=V(G)—X.如果G是一个连通图,s()E(G)使得G—S不连通,且G—S的每一个分支至少有k个点,则S称为G的一个k阶限制边割.G中所有k阶限制边割的最小阶称为G的k阶限制边连通度,用λk(G)表示.如果λk(G)存在,则称G是λk—连通的.如果G中的—个k阶限制边割S满足|S|=λk,则S称为λk—割.
对于X,Y()V(G),令[X,Y]表示一端在X中,另一端在Y中的边集.令I(x)=|[X,—X]|,ξk(G)=min{I(X):|X|=k,G[X]是连通的}.
对于—个连通图G,如果λk(G)=ξk(G),则G称为λk—最优图.
如果对于一个λk—最优图的每一个λk七割S都孤立出一个k阶连通子图,则我们称这样的图为超级λk—连通图.
在第二章中,我们研究一般二部图的k阶限制边连通度的最优性的问题.主要得到以下结果:
定理2.2:若G是连通的二部图且δ(G)≥3,对于使d(x,y)=2的点x,y都有d(x)+d(y)≥2[n(G)/4]+4,则G是λ3—最优图,
定理2.4:若G是连通的二部图,且δ(G)≥3,|G|≥11,对于使d(x,y)=2的点x,y都有d(x)+d(y)≥2[n(G)/4]+6,则G是λ4—最优图,
定理2.5:若G是连通的二部图,δ(G)≥5,对于使d(x,y)=2的点x,y都有d(x)+d(y)≥2[n(G)/4]+8,则G是λ5—最优图.
在第三章中我们研究完全p部图k阶限制边连通度的存在性、有界性及完全二部图的最优性,主要有以下结果:
定理3.4:若G为完全p部图K(r1,r2,…rp)且G≠K1,n-1,r1+r2+…+rp≥2k,则λk(G)存在且λk(G)≤ξk(G).
由此当p=2时我们可得出
推论3.5:若G为完全二部图Kr,s,r,s≥2,r+s≥2k,则λk存在且λk(G)≤ζk(G).
定理3.6:若G是完全二部图Kr.s,则G是λk—最优图当且仅当r,s≥2,r+s≥2k.
在第四章中我们将给出图三阶限制边连通度最优性的一个充分条件:
定理4.2:对图G,|G|≥6如果δ>3且D≤g—4那么λ3(G)=ζ3(G).