论文部分内容阅读
在当今经济和科技蓬勃发展的信息时代,互联网在人们的工作、日常生活等方面凸显越来越重要的地位.研究网络的可靠性和容错性成为近年来国内外研究的热点课题之一.众所周知,图的边连通度是反映图的连通性质的一个重要参数.然而为了更精确地刻画图的连通性质,需要将经典边连通度的概念继续加以推广.1983年F.Harary提出条件边连通度的概念,经过二十年来的发展,各类条件边连通度问题被相继提出,发展和应用.图的限制边连通度问题在大型网络的设计和分析中非常重要,在实际问题中也应用广泛,是图论研究中非常活跃的研究课题. 在设计和分析大规模网络的可靠性和容错性时,通常考虑某些类型的度量准则和图模型.对于不同的度量准则和模型,相应地需要研究许多不同的相关理论问题.图的不连通性可以作为图网络可靠性的度量准则,此时其中一个重要模型是这样的图G=（V,E）：假设其节点不会失效,但节点间的连线,也就是边相互独立地以等概率p∈（0,1）失效.令e是G的边数,Ch表示边数为h的边割的数目,则G不连通的概率可以表示为：因此图G的可靠度为1-P（G,p）.显然P（G,p）越小,网络的可靠性就越好.自然,为了确定P（G,p）的值就需要确定所有系数Ch.但是J.Provan和M.Ball指出,对一般图G,确定所有系数Ch,从而计算P（G,p）的值是NP-困难的.为此,A.H.Esfahanian和S.L.Hakimi在研究大规模网络的可靠性和容错性时提出了图的限制边连通度的概念,这一概念能反映图的经典边连通度所不能反映的更深刻的图的边连通性质.J.Fabrega和M.A.Fiol将限制边连通度的概念进一步推广,提出了κ-限制边割和κ-限制边连通度的概念.本文将在前人工作的基础上,继续研究κ-限制边连通度的相关性质. 在第一章中,我们简要介绍了本文的研究背景和部分已有结果,以及文章中所涉及到的一些概念、术语和符号. 本文所谈及的图都是有限无向简单连通图.记G=（V, E）,其中V表示G的顶点集,E表示G的边集,我们记n（G）=|V|.对于X（?）V（G）,G[X]表示由X导出的子图, X=V（G）-X.对于A,B（?）V（G）,[A,B]表示一端在A中且另一端在B中的所有边构成的集合.称（?）（X）=|[X,V-X]|为X的外度. 设κ为正整数,n（≥2κ）阶连通图G=（V, E）,其边子集S称为G的κ-限制边割,若G-S不连通且G-S的每个分支至少有κ个顶点,记为Rκ-边割.G的最小Rκ-边割（称为λκ-割）所含的边数称为G的κ-限制边连通度,记为λκ（G）或λκ.若λκ（G）存在,则称G为λκ-连通图. 令ξκ（G）=min{（?）（X）：X（?）V（G）,|X|=κ,且G[X]连通}.若[X,X]是图G的一个λκ-割,则称X,X为λκ-碎片.图G的含顶点数最少的λκ-碎片称为G的λκ-原子.图G的λκ-原子的顶点数记为rκ（G）. 设G是λκ-连通图,若λκ（G）=ξκ（G）,则称G为λκ-最优图.若G的每个λκ-割孤立一个κ阶连通子图,则称G为超级λκ-连通图（简称超级-λκ图）. 在第二章中,我们给出了图的λκ（κ=2,3）最优性和超级性的一些充分条件,得到以下结果： 定理2.1.3设整数p≥3,G为n（≥4）阶λ’-连通图,G的团数w（G）≤p,度序列d1≥d2≥…≥dn=δ.若则G为超级-λ’图. 定理2.2.4设G是n阶λ3-连通图,对任意不相邻的两点u,v,有|N（u）∩N（v）|≥1,且ξ3（G）≤（?）,若满足下面条件： （a）每个导出四圈上至少有一个点w满足d（w）≥（?）-1； （b）每个K4-e上至少有一个点w满足d（w）≥（?）+1； （c）K1,3+e的一度点w满足d（w）≥（?）-3,则图G是λ3-最优图. 定理2.3.2 n阶λ3-连通图G若满足下面条件： （a）对任意两点x,y,d（x,y）=2或3时有max{d（x）,d（y）}≥（?）-2; （b）导出K1,3+e的一度点v满足d（v）≥（?）-2； （c）导出四圈上至少存在一个v满足d（v）≥（?）； （d）K4-e上至少存在一个点v满足d（v）≥（?）+2,则G为λ3-最优图.若d（·）换为d（·）-1以上条件还成立,则G为超级-λ3图. 在第三章中,我们给出了二部图λ3最优性和超级性的两个充分条件,得到下面的结果： 定理3.1.6设G（X∪Y,E）是一个λ3-连通二部图,δ（G）≥3.若λ3（G）＜ξ3（G）,则r3（G）≥（ξ3（G）+3）/2. 定理3.2.4设G=（X∪Y, E）为一个n（≥6）阶二部图且ξ3（G）≤（?）,若G有一个饱和X或Y的匹配,且对X中的任意两点和Y中的任意两点u,v都有|N（u）∩N（v）|≥3,则G为λ3-最优图. 在第四章中,我们给出了图的λκ最优性和超级性的一些充分条件以及相关性质,得到下面的结果： 定理4.2设G是n（≥2κ）阶连通图,δ（G）≥κ-1,G不同构于Gm,t*,t=δ（G）,则 （a）G为λκ-最优图当且仅当G为非λκ+1-连通图,或G为λκ+1-连通图且λκ+1（G）≥ξκ（G）； （b）G为超级-λκ图当且仅当G为非λκ+1-连通图,或G为λκ+1-连通图且λκ+1（G）＞ξκ（G）. Gm,t*的定义见正文. 定理4.4设G是n（≥2κ）阶不含三角形的连通图,δ（G）≥κ-1,若至多除去一点外,其余任意的x∈V（G）有d（x）≥（?）+（κ+（κ-2）2）/2,则G是λκ-最优图. 定理4.5设G是n（≥2κ+4）阶不含三角形的连通图,δ≥κ-1≥2,若至多除去一点外,其余任意的x∈V（G）有d（x）≥（?）+（κ+（κ-2）2）/2,则G是超级-λκ图. 定理4.8设κ≥2是整数.若G是不含三角形的λκ-最优图,δ（G）≥max{3,κ-2},且对任意不相邻的两点u,v有d（u）+d（v）≥4κ-7,则对于i=1,2,…,κ-1,G是超级-λκ-i图.