论文部分内容阅读
图的限制性边连通度问题及许多理论都是源自大型网络的设计和可靠性分析.另外限制性边连通度在实际问题中有着广泛的应用,是图论研究中一个很活跃的课题,各类限制边连通度问题被相继提出并加以发展、应用。
如果不是特别说明,文中谈及的所有图都是简单连通的,当研究网络可靠性的时候,经常考虑这样一种图模型,它的节点不失效,但是它的连线,也就是边可以独立地等可能地失效,失效的概率是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—最优的。