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

关于k阶限制边连通度若干问题的研究

作　者: 桑镇
导　师: 高敬振
学　校: 山东师范大学
专　业: 应用数学
关键词: 图 k阶限制边连通度有界性最优性完全二部图
分类号: O157.5
类　型: 硕士论文
年　份: 2009年
下　载: 15次
引　用: 2次
阅　读: 论文下载

内容摘要

图的限制性边连通度问题及许多理论都是源自大型网络的设计和可靠性分析.另外限制性边连通度在实际问题中有着广泛的应用,是图论研究中一个很活跃的课题,各类限制边连通度问题被相继提出并加以发展、应用.当研究网络可靠性的时候,经常考虑这样一种图模型,它的节点不失效,但是它的连线,也就是边可以独立地等可能地失效,失效的概率是ρ∈（0,1）.这就是非常有名的Moore-Shannon网络模型[1,2].令G是一个Moore-Shannon网络模型,边数为h的边割的数目用C_h表示,如果G恰好有e条边,则它不连通的概率P（G,ρ）就可以表示为:显然,P（G,ρ）的值越小,网络的可靠性越好.如果能确定所有的系数C_h,那么这个网络的可靠性就确定下来了.但是对于任意图,Provan和Ball在文献[3]中指出,确定所有的系数C_h是一个NP-困难问题.用Ω（n,e）表示n个点e条边的图的集合,当ρ充分小时,在Ω（n,e）中为了最小化P（G,ρ）,边连通度λ（G）起了非常重要的作用.Bauer et al在文献[4]中指出,当ρ充分小时,对G₁,G₂∈Ω（n,e）,如果λ（G₁）＞λ（G₂）,则P（G₁,ρ）＜P（G₂,ρ）.为了更准确地确定这个可靠性, Esfahanian和Hakimi在文献[5]中引入了限制边割和限制边连通度.Fabrega和Fiol将限制边连通度的概念进一步推广,提出了k阶限制边割和k阶限制边连通度的概念[6].本文在前人工作的基础上,继续研究限制边连通度的相关性质.在本文第一章中,我们主要介绍了文章所涉及的一些概念、术语和符号.记图G的顶点集为V（G）,边集为E（G）.对于x（?）V（G）,令G[X]表示X的导出子图,（?）＝V（G）－X.如果G是一个连通图,S（?）E（G）使得G－S不连通,且G－S的每一个分支至少有k个点,则S称为G的一个k阶限制边割. G中所有k阶限制边割的最小阶称为G的k阶限制边连通度,用λ_k（G）表示.如果λ_k（G）存在,则称G是λ_k-连通的.如果G中的一个k阶限制边割S满足|S|＝λ_k,则S称为λ_k-割.对于X,Y（?）V（G）,令[X,Y]表示一端在X中,另一端在Y中的边集.令I（X）＝|[X,（?）]|,ξ_k（G）＝min{I（X）:|X|＝k,G[X]是连通的}.对于一个连通图G,如果λ_k（G）＝ξ_k（G）,则G称为λ_k-最优图.如果对于一个λ_k-最优图的每一个λ_k割S都孤立出一个k阶连通子图,则我们称这样的图为超级λ_k-连通图.在第二章中,我们研究一般二部图的k阶限制边连通度的最优性的问题.主要得到以下结果:定理2.2:若G是连通的二部图且δ（G）≥3,对于使d（x,y）＝2的点x,y都有d（x）＋d（y）≥2（?）＋4,则G是λ₃-最优图.定理2.4:若G是连通的二部图,且δ（G）≥3,|G|≥11,对于使d（x,y）＝2的点x,y都有d（x）＋d（y）≥2（?）＋6,则G是λ₄-最优图.定理2.5:若G是连通的二部图,δ（G）≥5,对于使d（x,y）＝2的点x,y都有d（x）＋d（y）≥2（?）＋8,则G是λ₅-最优图.在第三章中我们研究完全p部图k阶限制边连通度的存在性、有界性及完全二部图的最优性,主要有以下结果:定理3.4:若G为完全p部图K_{（r₁）,（r₂）,…,（r_p）}且G≠K_{1,（n－1）},r₁＋r₂＋…＋r_p≥2k,则λ_k（G）存在且λ_k（G）≤ξ_k（G）.由此当p＝2时我们可得出推论3.5:若G为完全二部图K_r,s,r,s≥2,r＋s≥2k,则λ_k存在且λ_k（G）≤ξ_k（G）.定理3.6:若G是完全二部图K_r,s,则G是λ_k-最优图当且仅当r,s≥2,r＋s≥2k.在第四章中我们将给出图三阶限制边连通度最优性的一个充分条件:定理4.2:对图G,|G|≥6如果δ≥3且D≤g－4那么λ₃（G）＝ξ₃（G）.

全文目录

中文摘要  5-8
英文摘要  8-11
第一章引言  11-16
第二章二部图的最优性  16-31
第三章完全多部图的最优性  31-34
第四章图三阶限制边连通度最优性的一个充分条件  34-37
参考文献  37-41
攻读学位期间发表的学术论文  41-42
致谢  42

关于k阶限制边连通度若干问题的研究

内容摘要

全文目录

相似论文