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

k阶限制边连通度的最优性和超级性

作　者: 张凤娟
导　师: 高敬振
学　校: 山东师范大学
专　业: 应用数学
关键词: 图 k阶限制边连通度 λp,q-连通最优性超级性
分类号: O157.5
类　型: 硕士论文
年　份: 2009年
下　载: 18次
引　用: 2次
阅　读: 论文下载

内容摘要

图的限制性边连通度问题及许多理论都是源自大型网络的设计和可靠性分析.另外限制性边连通度在实际问题中有着广泛的应用,是图论研究中一个很活跃的课题,各类限制边连通度问题被相继提出并加以发展、应用.如果不是特别说明,本文中谈及的所有图都是简单连通的.当研究网络可靠性的时候,经常考虑这样一种图模型,它的节点不失效,但是它的连线,也就是边可以独立地等可能地失效,失效的概率是ρ∈（0,1）.令G是一个网络模型,边数为h的边割的数目用C_h表示,如果G恰好有e条边,则它不连通的概率P（G,ρ）就可以表示为:显然, P（G,ρ）的值越小,网络的可靠性越好.如果能确定所有的系数C_h,那么这个网络的可靠性就是确定的.但是对于任意图,Provan和Ball在文献[1]中指出,确定所有的系数C_h是一个NP-困难问题.用Ω（n,e）表示n个点e条边的图的集合,当ρ充分小时,在Ω（n,e）中为了最小化P（G,ρ）,边连通度λ（G）起了非常重要的作用.当ρ充分小时,对G₁,G₂∈Ω（n,e）,如果λ（G₁）>λ（G₂）,则P（G₁,ρ）<P（G₂,ρ）.为了更准确地确定这个可靠性,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导出的子图, （?=）V（G）-X[X,（?）]表示G中一端在X中,一端在（?）中的边的集合.给定n（≥2k）阶图G的一个边集S,若G-S不连通且它的每个分支的阶至少为k,则称S为G的一个k阶限制边割,简称为R_k^-边割.若G有R_k^-边割，则称G是λ_k^-连通的,且G的最小R_k^-边割(叫λ_k^-边割)所含边数称为G的k阶限制边连通度,记为λ_k（G）.显然,λ（G） =λ₁（G）≤λ₂（G）≤…≤λ_k（G）.设X（?）V（G）,α（X）=|[X,（?）]|.记ξ_k（G）=min{α（X）:|X|=k,G[X]连通}.易见ξ₁（G）=δ（G）,其中δ（G）为G的最小度.称一个图G是λ_k^-最优的,若λ_k（G）存在且λ_k（G）=ξ_k（G）.称图G是超级-λ_k连通图,若G的每个λ_k^-割都分离一个k阶连通子图.Harary首次提出了广义限制边连通度的定义.一般地,对整数p,q≥1,称一个连通图是λ_p,q^-连通的,如果存在一个边割使得去掉此边割后得到的图恰有两个分支阶分别至少为p和q.文献[2]中给出了λ_2,q^-连通图的性质,第二章主要考虑去掉图中一个三阶连通子图后的情形,即研究λ_3,q^-连通图的性质,并使[26]中结果成为本文主要结果的推论.在第三章中,本文主要研究图的三阶和四阶限制边连通度的最优性和超级性.给出了:图是λ_3^-,最优及超级-λ₂连通的最小度条件,图是λ_4^-最优及超级-λ₃连通的最小度条件,以及图是λ_4^-最优及超级-λ₄连通的度和条件.在第四章中我们将给出k阶限制边连通度的最优性的一个度序列条件.在本文中,我们主要得到如下结论:定理2.3令n,q为正整数且n≥max{7,q+3},q≥3₁一个阶为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非λ_2,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.6令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.1.5设G是一个n阶连通图,n≥10且δ（G）≥[n/2]-2,若G中每个四圈C上都存在一点ω使得d（ω）≥[n/2]+2,则G是λ_3^-最优的.进而,若G中每个三角形T上都存在一点ν使得d（ν）≥[n/2],则G是超级-λ₂连通的.定理3.2.4设G是一个n阶λ_4^-连通图,n≥11且δ（G）≥[n/2]-3.若G中每个导出五圈上及两个三角形的粘合图除粘合点外都存在一点u使得d（u）≥[n/2]-1,每个导出四圈上都存在一点v使得d（v）≥[n/2]+1且每个K₄-e上都存在一点ω使得d（ω）≥[n/2]+3,则G是λ_4^-最优的.进而,若n≥12,则G是超级-λ₃连通的.定理3.3.2设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）每个K₄-e上都存在一点v使得d（v）≥[n/2]+3.定理3.3.5设G是一个n≥11阶连通图,若G满足以下条件,则G是超级-λ₄连通的.（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）每个K₄-e上都存在一点v使得d（v）≥[n/2]+4.定理4.3设G=（V,E）为n阶λ_k^-连通图,其围长g>k+1.如果对G的任意连通子图H都有|E（H）|≤|V（H）|²/g,λ_k（G）≤ξ_k（G）且G的度序列d₁≥d₂≥…≥d_n=δ满足则G是λ_k^-最优的.

全文目录

中文摘要  5-8
英文摘要  8-12
第一章引言  12-17
第二章图的λ_(3,q~-)连通性  17-23
第三章三四阶限制边连通度最优性和超级性的局部条件  23-35
  3.1 图是λ_(3~-)最优及超级-λ_2连通的最小度条件  23-27
  3.2 图是λ_(4~-)最优及超级-λ_3连通的最小度条件  27-31
  3.3 图是λ_(4~-)最优及超级-λ_4连通的度和条件  31-35
第四章图的k阶限制边连通度的最优性  35-37
参考文献  37-41
在学期间发表的学术论文  41-42
致谢  42

k阶限制边连通度的最优性和超级性

内容摘要

全文目录

相似论文