论文部分内容阅读
随着经济和科技的迅猛发展,互联网络与人们的关系越来越密切,对于网络的各项研究备受人们的关注,其中对于可靠性和容错性的研究已经是国内外的研究热点之一.对于大规模网络的可靠性和容错性的分析通常引入各种图论模型,利用图的点和边来代替网络的节点和连线,以此构成相互连通的网络的基础拓扑.众所周知,传统边连通度可以估计网络的可靠程度,但这一重要参数在对于相同边连通度的不同网络可靠性的判断中却失效了.为了更好地刻画图的连通情况,F.Harary于1983年提出条件边连通度的概念,为这一领域的研究开辟了新的道路.自此,网络的可靠性及容错性的综合分析快速发展起来,成为图论研究中一个很热门的课题.在设计和分析大规模网络的可靠性和容错性时,通常涉及这样一种著名的图模型G=(V,E)：节点不会失效,但边独立地以概率ρ∈(0,1)等可能地失效.若G的边数是ε,Gi表示边数为i的边割的数目,则G不连通的概率为：易知网络保持连通的概率为1-P(G,ρ).显然P(G,ρ)越小,网络的可靠性越好.因此,若要确定网络的可靠性,需要确定所有的系数Ci,但J.S.Provan和M.O.Ball证明了对于一般图这是NP-困难问题.为了更加精确地估计网络的可靠性,A.H.Esfahanian和S.L.Hakimi提出了限制边连通度的概念.更进一步,李乔良和李乔提出了超级限制边连通度的概念.目前,对于这一领域已有了广泛而深入的研究.本文在前人工作的基础上,继续研究限制边连通度的若干性质.在第一章中,我们主要介绍了本文的研究背景和一些已有的结果,以及文章中涉及的一些概念和术语符号.记G=(V,E)是一个简单连通图,其中V(G)表示G的顶点集,E(G)表示G的边集,我们称n(G)=|V|为G的阶.对v∈V(G),非负整数r≥0,以Nr(v)={w∈V(G)：d(w,v)=r}记与v距离为r的点的集合.显然N0(v)={v}.当r=1时,将N1(v)简记为N(v),N[v]=N(v)∪{v}.如果U是阶为n(≥2κ)的图G的边割,且G-U的每个分支的阶至少为κ,则称U为G的κ阶限制边割.定义λκ=λκ(G)=min{|U|：U为G的κ阶限制边割}为G的κ阶限制边连通度,达到最小的这种U称为G的λκ-割.若λκ(G)存在,则称G是λκ-连通的.设F是图G的一个子图,令(?)(F)表示恰好有一个端点在F上的边的数目.定义ξκ=ξκ(G)=min{(?)(F)：F是G的κ阶连通子图}.特别地,λ2(G),ξ2(G)分别记为λ’(G),ξ(G),其中ξ(G)叫最小边度.如果λκ(G)=ξκ(G),称G是λκ-最优的.如果G的每个λκ-割都孤立一个κ阶连通子图,则称G是超级-λκ的.显然超级-λκ图G有λκ(G)≥ξκ(G),因而若有λκ(G)≤ξκ(G),则G是λκ-最优的.然而反过来不一定成立.在第二章中,我们重点讨论了图的最优性和超级性的邻域交条件,得到以下结果：定理2.1.1令G是n(≥4)阶连通图,且n≥6时, G不同构于Kn/22和K2,n-2.若对任意一对不相邻的顶点u,v,有(a)u,v均不在三角形上时, |N(u)∩N(v)|≥2,(b)u或v在三角形上时, |N(u)∩N(v)|≥4或G[N(u)∩N(v)](?)K3,则图G是超级-λ’的.其中Kn/22为由n条边连接两个完全图Kn/2所得的(n/2+1)-正则图.定理2.2.1令G是n(≥6)阶连通图,若对不相邻的两点u,v,有|N(u)∩N(v)|≥2,特别地(a)u或v在K4-e或导出四圈上时, |N(u)∩N(v)|≥3,(b)u或v在K4上时,|N(u)∩N(v)|≥5,则图G是λ3-最优的.定理2.2.2令G是n(≥6)阶连通图,若对任意一对不相邻的顶点u,v有|N(u)∩N(v)|≥5或G[N(u)∩N(v)](?)K4,则图G是λ3-最优的.在第三章中,我们主要研究了利用局部条件刻画图的最优性和超级性,具体讨论了利用邻域交,边度和度条件来刻画的情形,得到以下主要结果：定理3.1.3令G是n(≥4)阶连通图,且G不同构于G6,3,G8,4和G5,3,若(a)对任意一对不相邻的顶点u,v,有|N(u)∩N(v)|≥3,(b)ξ≤(?)+2,则图G是超级-λ’的.定理3.1.4令G是n(≥4)阶连通图,若(a)对任意一对不相邻的顶点u,v,有|N(u)∩N(v)|≥3,(b)每个三角形上至少存在一点v,有d(v)≥(?)+2,则图G是超级-λ’的.定理3.2.1令G是n(≥6)阶连通图,且G不同构于Gi,4,i=4,6,7,8和G11,5,若(a)对任意一对不相邻的顶点u,v,有|N(u)∩N(v)|≥3,(b)ξ3≤(?)+4,则图G是λ3-最优的.其中上述图类Gi,j的具体定义见正文.定理3.2.2令G是n(≥6)阶连通图,若(a)对任意一对不相邻的顶点u,v,有|N(u)∩N(v)|≥3,(b)每个三角形和导出四圈上至少存在一点v,使得d(v)≥(?)+2,则图G是λ3-最优的.在第四章中,我们利用直径,围长条件给出了图是超级-λ’的一个充分条件,得到下面的结果：定理4.1令G是n(≥4)阶连通图,δ≥3,D≤g-2,且D=g-2时满足下列条件之一：(ⅰ)满足d(u,v)=g-2的点u,v均不在长为g的圈上,(ⅱ)满足d(u,v)=g-2的点u,v有|N[(g-2)/2](u)∩N(?)(v)|≥3,则图G是超级-λ’的.