学位论文 > 优秀研究生学位论文题录展示

图的k-限制边连通度性质的研究

作 者: 马玉
导 师: 高敬振
学 校: 山东师范大学
专 业: 应用数学
关键词:  κ-限制边连通度 λ_κ-最优图 超级-λ_κ图
分类号: O157.5
类 型: 硕士论文
年 份: 2011年
下 载: 14次
引 用: 0次
阅 读: 论文下载
 

内容摘要


随着经济和科技的迅猛发展,网络与人们的工作、日常生活等方面的关系越来越密切.自然,网络的可靠性和容错性倍受人们的关注.研究网络的可靠性和容错性是近年来国内外研究的热点之一.众所周知,边连通度是反映的连通性质的一个重要参数.而要精确地刻画图的连通性质,它存在着不足之处:首先,边连通度相同的图可靠度可能不同;其次,不能区分删掉κ个割断点或λ条割断边得到的图的不同类型,即未考虑对网络的破坏程度;第三,默认图的任何子集中所有元素可能潜在地同时失效.为克服以上缺陷,自然要将其加以推广.自1983年Harary提出条件边连通度的概念以来,经过二十多年的发展,条件边连通度所涉及的内容日益丰富和具体,包括超级边连通度、过边连通度、限制边连通度等.设计和分析大规模网络的可靠性和容错性时,通常包括某些类型的图模型,其中一个重要模型是这样的图:设图G=(V, E),其节点不会失效,每一条边是独立失效的,失效概率为p∈(0,1).用Ni(G)表示边数为i的边割的数目,则G连通的概率R(G,p)为:R(G,p)=1-(?) Ni(G)pi(1-p)ε-i, i=λ(G)其中ε是G的边数,A(G)为边连通度.对于一般图,确定Ni(G)是NP-困难的[2].Esfahanian和Hakimi[3]提出了图的限制边连通度的概念.这一概念能反映图的经典边连通度所不能反映的更深刻的图的边连通度性质.更进一步,李乔良和李乔[4]提出了超级限制边连通度的概念.本文将在前人工作的基础上,继续研究k-限制边连通度的若干性质.在第一章中,我们主要介绍了本文的研究背景和一些已有的结果,以及文章中涉及的一些概念和术语符号.记G=(V,E)是一个有限简单连通图,其中V(G)表示G的顶点集,E(G)表示G的边集,我们称n(G)=|V|为G的阶.对于X(?)V(G),G[X]表示由X导出的子图,x=V(G)一X.对A,B (?) V定义[A,B]为一端在A中,另-端在B中的边的集合.如果S是图G的边割,且G-S的每个分支的阶至少为k,则称S为G的k-限制边割.定义Ak=λk(G)=min{|S|:S是G的k-限制边割}为G的k-限制边连通度,达到最小的这种s称为G的λk-割.若λk(G)存在,则称G是λk-连通图.设F是图G的一个子图,令(?)(F)表示恰有一个点在F上的边的数目.定义ξk=ξk(G)=min{(?)(F):F是G的k阶连通子图}.特别地,λ2(G),ξ2(G)分别记为λ’(G),ξ(G),其中ξ(G)叫最小边度.如果λk(G)=ξk(G),称G是λk-最优的.若任意一个λk-割都孤立一个k阶连通子图,则称G是超级-λk的.显然超级-λk图G有Ak(G)≥λk(G),因而若有λk(G)≤ξk(G),则G是λk-最优的.然而反过来不一定成立.在第二章中,我们给出了两个用度刻画图的超级-λ′性的充分条件,得到如下的结果:定理2.2令G是n阶图,δ(G)≥3.若G满足下面的条件,则G是超级-λ′的.(a)任意的边存在一个端点v,使得d(v)≥[n/2],(b)任意三角形上存在一点v,使得d(v)≥[n/2]+2,(c)若d(u)≤[n/2]-1,d(v)≥[n/2],则uv∈E(G).定理2.3若G是n阶图,δ(G)≥3,且满足下面条件,则G是超级-λ′的.(a)对G中任意两个不相邻的顶点u,v,有|N(u)∩N(v)|≥2,(b)任意的三角形上存在一点v,使得d(v)≥[n/2]+2,(c)任意的导出四圈和K4-上都至多存在一点v,使得d(v)≤[n/2]-1.其中K4-表示K4删去一条边所得图.在第三章中,我们主要研究了图是超级-A3的充分条件,得到下面的结果:定理3.3令G是n(≥6)阶图,若(a)对任意一对不相邻的顶点u,v,有|N(u)∩N(v)|≥4,(b)ξ3(G)≤[n/2]+4,则G是超级-λ3的或G∈G1∪G2.其中图类Gi(i=1,2)的具体定义见正文.定理3.4令G是n(≥6)阶图,若(a)对任意一对不相邻的顶点u,v,有|N(u)∩N(v)|≥4,特别地,u或v在K4-上时有|N(u)∩N(v)|≥5,(b)每个三角形和导出四圈上存在一点ν,使得d(v)≥[n/2]+3,则G是超级-λ3的.在第四章中,我们主要讨论了图的λ4-最优性和超级性的充分条件,具体研究了利用一定距离的点对的最大度,邻域交,ξ4及度条件来刻画的情形,得到下面的结果:定理4.1.4令G是n(≥11)阶连通图.G是λ4-最优的,若(a)对任意两点x,y∈V(G),当d(x,y)=m时max{d(x),d(y)}≥[n/2]+5-2m(m=2,3,4),(b)G中任意K5上存在一点ν满足d(v)≥[n/2]+3.若d(·)换为d(·)-1后条件仍成立,则G是超级-λ4的.定理4.2.1令G是n(≥11)阶图.若(a)对任意一对不相邻的顶点u,ν,有|N(u)∩N(v)|≥4,(b)ξ4(G)≤[n/2]+6,则G是λ4-最优的或G∈G*定理4.2.3令G是n(≥11)阶图.若(a)对任意一对不相邻的顶点u,ν,有|N(u)∩N(v)|≥5,(b)ζ4(G)≤[n/2]+8,则G是超级-λ4的或G∈G3∪G4∪G5.其中图类G*,Gi(i=3,4,5)的具体定义见正文.定理4.3.3设G是n(≥12)阶无三角形的连通图,除去至多一点外,其余任意x∈V(G)有d(x)≥[(n+2)/4]+3,则G是λ4-最优的.定理4.3.4设G是n(≥12)阶无三角形的连通图,除去至多一点外,其余任意x∈V(G)有d(x)≥[n/4]+4,则G是超级-λ4的.在第五章中,我们主要讨论二部图的最优性和超级性的邻域交条件,得到下面的结果:定理5.1.1令G(X∪Y,E)是n(≥4)阶连通平衡二部图.若除X,Y中各至多一点外,其余任意x∈V(G)有d(x)≥[n/4]+3,则G是超级-λ’的.定理5.2.2令G(X∪Y,E)是n(≥6)阶平衡二部图.若除X,Y中各至多一点外,其余任意x∈V(G)有d(x)≥[n/4]+3,且任意的同部顶点u,ν满足|N(u)∩N(v)|≥1,则G是λ3-最优的.定理5.3.2令G是n(≥11)阶连通二部图.G是λ4-最优的,若(a)对任意两点x,y∈V(G),d(x,y)=2时max{d(x),d(y)}≥[(n+2)/4]+4,(b)对任意两点x,y∈V(G),d(x,y)=3或4时max{d(x),d(y)}≥[(n+2)/4]+1.若d(·)换为d(·)-1后条件仍成立,则G是超级-A4的.

全文目录


相似论文

  1. 基于图的标志SNP位点选择算法研究,Q78
  2. 新型银基无镉中温钎料组织性能的研究,TG425.2
  3. 基于蚁群算法的电梯群优化控制研究,TU857
  4. LDPC码译码算法的研究,TN911.22
  5. 支持XML数据查询的F&B索引结构的研究,TP311.13
  6. 频繁图结构并行挖掘算法的研究与实现,TP311.13
  7. 矢量CAD电子图纸保护系统研究,TP391.72
  8. 基于图分割的文本提取方法研究,TP391.41
  9. 高保真遥感图象压缩与分辨率增强联合处理研究,TP751
  10. 基于支持向量机的故障诊断方法研究,TP18
  11. 基于LVDS技术的通讯卡研制,TP273
  12. 诗意的疏离:图文之间,J506
  13. 急性脑梗死患者睡眠结构的变化,R743.33
  14. 思维导图在科学教学中的应用,G633.98
  15. 高中生物学课堂教学中概念图的应用研究,G633.91
  16. 基于约束图的服装参数化制板技术,TS941.2
  17. 魔力平台业务过程建模冲突消解的研究与实现,TP311.5
  18. 经皮骶髂螺钉固定治疗不稳定骨盆骨折的临床疗效分析,R687.3
  19. 七维稳定耗散系统的代数条件及动力学性质,O175
  20. 基于模型的Web测试技术研究与应用,TP311.53
  21. 中考数学分层复习的实践研究,G633.6

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学(组合学) > 图论
© 2012 www.xueweilunwen.com