有向图和定向图的边连通性与点连通性研究

发布时间：2017-11-16 13:06

  本文关键词：有向图和定向图的边连通性与点连通性研究

  更多相关文章： 有向图 定向图 极大(超级)局部边连通性 极大(超级)连通性

【摘要】：近年来,随着大规模集合电路,微电子技术,大规模互联网络的飞速发展,人们对网络的拓扑结构要求越来越高.图的理论及其在各个领域的广泛应用越来越受到数学界和其他科学界的重视.网络的可靠性和容错性受到人们的普遍关注.图论中图的连通性分析为此类问题的研究提供了重要的理论依据.设计和分析多处理机互联网络时,通常会涉及某些类型的网络模型,利用图的点和边来代替网络的节点和连线,以此构成相互连通的网络的拓扑结构.通常将网络的拓扑结构抽象成图或有向图D=(V,E).这时D的顶点代表处理机,连接顶点的边表示一对处理机之间的直接通信联系(有向边则表示只能进行单向联系).在研究这种模型时,经常假设其节点不会失效,但每条边相互独立地以相等的概率p∈(0,1)失效.用m表示D的边数,λ(D)表示D的边连通度,Ci(D)表示D的边数为i的边割数目,则D连通的概率为：要准确的计算出D的可靠度,需要计算出每个系数Ci(D).但是,Provan和Ball在1983年指出计算出所有这些系数是NP-困难的.Colbour对此作了进一步阐述.但是,在精确刻画图或有向图的连通性方面,边连通度或点连通度存在一些不足：首先,边连通度或点连通度相同的图或有向图的可靠性可能有所不同.其次,不能区分删掉λ-割或κ-割后的图或有向图的不同类型,即未考虑网络的破坏程度.第三,默认图或有向图的任何子集中所有元素可能潜在地同时失效.为克服以上缺陷,自1983年Harary提出了条件边连通度的概念,为该领域的研究开辟了新的道路.经过二十多年的发展,边连通性所涉及的内容日益丰富和具体,包括超级边连通性、极大局部边连通性和超级局部边连通性等.类似的,在图的点连通性方面,也出现了极大连通性、极大局部连通性等概念.这些参数都能更深刻地刻画图或有向图的边、点连通性质.本人在前人工作的基础上,继续研究图或有向图的超级边连通性以及图的的超级局部连通性等相关性质.在第一章中,主要介绍本文的研究背景和一些已有的结果,以及文章中涉及的一些基本概念、术语符号.在第二章中,主要研究定向图极大与超级局部边连通的充分条件,首先,给出了利用度序列的低度端保证定向图是极大和超级局部边连通的充分条件.定理2.1.3设D为n阶定向图,度序列为d1≥d2≥…≥dn(=δ),△'=△'(D).(1)若δ≥[n-1/4],或δ≤[n-2/4]且对某整数k,1≤k≤2δ+1,有∑ dn+1-i≥k(n-1-k)+1+max{0, △'+k-2δ-2,2△'+2k-n-2},则D是极大局部边连通的.(2)若δ≥[(n+1)/4],或δ≤[n/4]且对某整数k,1≤k≤2δ有∑ dn+1-i≥k(n-1-k)+1+max{0, △'+k-2δ-2,2△'+2k-n-2},则D是超级局部边连通的.其次,给出了二部定向图极大局部边连通的度和条件.定理2.2.4设D为n阶二部定向图,最小度δ≥2.若对任意同部顶点u,v,有d+(u) +d+(v)n/2-3/2,d-(u)+d-(v)n/2-3/2,则D是极大局部边连通的.在第三章,主要研究有向图与定向图的依赖团数的局部边连通性.首先给出有向图依赖团数的极大局部边连通的充分条件.定理3.1.3设D为n阶有向图,团数w(D)≤p,度序列为d1≥d2≥…≥dn(=δ), △'=△'(D).若n≤2[(pδ)/(p-1)]-1,或n≥2[(pδ)/(p-1)]且对某整数k,1≤k≤[δ/(p-1)],有则D是极大局部边连通的.定理3.1.4设D为n阶有向图,团数w(D)≤p,度序列为d1≥d2≥…≥dn(=δ), △'=△'(D).若n≤2[(pδ)/(p-1)]-1,或n≥2[(pδ)/(p-1)]且对某整数k,1≤k≤[(pδ)/(p-1)]-,有则D是极大局部边连通的.然后,又给出了依赖团数的超级局部边连通的充分条件,即有如下结果：定理3.2.4设D为n阶有向图,团数w(D)≤p,最小度δ≥3,度序列为d1≥d2≥...≥dn(=δ),△'=△'(D).若n≤2[(pδ)/(p-1)]-3,或n≥2[(pδ)/(p-1)]-2且对某整数k,1≤k≤[(pδ)/(p-1)]--1,有则D是超级局部边连通的.定理3.2.5设D为n阶定向图,团数w(D)≤p,最小度为δ≥2,度序列为d1≥d2≥…≥dn(=δ),△'=△'(D).若n≤2[(2pδ)/(p-1)]-3,或n≥2[(2pδ)/(p-1)]-2且对某整数k,1≤k≤[(2pδ)/(p-1)]-1,有则D是超级局部边连通的.在第四章中,主要研究有向图极大边连通的倒数度条件.得到如下结果：定理4.1.2设D是n≥2阶强连通有向图,最小度δ.若δ≥[n-1/2],或δ≤[n-2/2]且则D是极大边连通的.定理4.2.2设D是n阶强连通无三角形有向图,最小度δ.若δ≥[(n+1/4],或δ≤ [n/4]且满足则D是极大边连通的.在第五章中,得到保证无p-钻图与不含K2,3图局部连通性的充分条件.定理5.2设p≥2为整数,G是n阶连通无p-钻图,u,v∈V(G),则G是超级局部连通的,若其中r=min{d(u),d(v)}-δ(≥0).定理5.5不含k2,3,最小度δ≥2的n阶连通图G为极大局部连通的,若阶数n≤3δ-3.
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【参考文献】

中国硕士学位论文全文数据库 前1条

1 邵光凤;有向图的局部边连通度的性质[D];山东师范大学;2012年

，

本文编号：1192418