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

发布时间：2017-11-15 03:29

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

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

【摘要】：图论是一门古老而又活跃的学科,也是一门很有实用价值的学科.它是研究工程技术,自然科学等的重要数学工具,应用极为广泛.在现代社会中,人们的日常生活,学习和工作与多处理机互联网络的关系也越来越密切.因此网络的可靠性和容错性受到人们的普遍关注,从而网络的可靠性和容错性的研究成为了近年来国内外研究的一大热点.在设计和分析大规模互联网的可靠性和容错性时,一个很重要的模型是将网络的拓扑结构抽象成图或有向图D=(V,E).D的顶点代表处理机,连接顶点的边表示一对处理机之间的直接通信联系(有向边则表示只能进行单向联系).研究这种模型时,假设其节点不会失效,但每条边相互独立地以相等的概率p∈(0,1)失效.则D不连通的概率为：其中m表示D的边数,λ(D)表示D的边连通度,Ci(D)表示D的边数为i的边割数目,因而可用D连通的概率R(D,p)=1—P(D,p)来衡量网络的可靠性.显然P(D,p)越小,网络的可靠性越好,但是对于一般图,确定所有的系数G是NP-困难的.对此,Colbour[2]做了进一步的阐述.当假设D的边不会失效,但其节点相互独立地以相等的概率p∈(0,1)失效时也有类似的讨论.图或有向图的边连通度是反映其连通性质的一个重要参数.而在精确刻画图或有向图的连通性方面,经典边连通度存在一些不足：首先,边连通度相同的图或有向图的可靠性可能有所不同.其次,不能区分删掉λ-割后所得图或有向图的不同类型.最后,默认图或有向图的任何子集中所有元素可能潜在地同时失效.为了克服以上缺陷,自1983年Harary[5]提出了条件边连通度的概念,经过三十多年的发展,边连通性所涉及的内容日益丰富和具体,其中包括极大边连通性、超级边连通性、极大局部边连通性和超级局部边连通性等.目前,对于这一邻域已有了广泛而深入的研究.本人在前人工作的基础上,继续研究图或有向图的边连通的相关性质.本文主要研究有向图与定向图的边连通性的一些条件.在第一章中,主要介绍本文的研究背景和一些已有的结果,以及文章中涉及的一些基本概念、术语符号.在第二章中,首先给出定向图依赖于团数的超级边连通性的度序列条件：为简洁起见,本章所讨论的定向图的阶数n为偶数时,令v=1,否则,令v=0；当所讨论的定向图的团数ω(D)≤p,最小出度,最小入读,最小度分别为δ+,δ-,δ时,令定理2.1.5 设D是n阶定向图,团数ω(D)≤p且p≥4,出度序列为d1+≥d2+≥…≥dn+(=δ+≥2),入度序列为d1-≥d2-≥…≥dn-(=δ-≥2).若则D是超级边连通的.定理2.1.6 设D是n阶定向图,团数ω(D)≤p且p≥4,度序列为d1≥d2≥…≥若则D是超级边连通的.定理2.1.7 设D是n阶定向图,团数ω(D)≤p且p≥4,n为偶数,度序列为d1≥若则D是超级边连通的.然后又讨论了有向图和定向图极大局部和超级局部边连通依赖于团数的度序列条件,得到了以下结果：定理2.2.4 设D为n阶定向图,团数ω(D)≤p,度序列为d1≥d2≥…≥dn(=δ),△’=△’(D).若n≤4[pδ/p-1]-1或若n≥4[pδ/p-1]且对某整数k,1≤k≤2δ+1,有则D是极大局部边连通的.定理2.3.4 设D为n阶有向图,团数ω(D)≤p,度序列为d1≥d2≥…≥dn(=δ),△’=△’(D).若n≤2[pδ/p-1]-1或若n≥2[pδ/p-1]且对某整数k,1≤k≤[pδ/p-1],有则D是极大局部边连通的.定理2.3.11设D为n阶有向图,团数ω(D)≤p,度序列为d1≥d2≥…≥dn(=δ≥3),△'=△'(D).若n≤2[pδ/p-1]-3或若n≥2[pδ/p-1]-2且对某整数k,1≤k≤[pδ/p-1]-1,有则D是超级局部边连通的.在第三章,首先给出了有向图极大局部边连通的度序列条件：定理3.1.3设D为n阶有向图,度序列为d1≥d2≥…≥dn(=d),△'=△'(D).若δ≥[n/2]或若δ≤[n2/]-1且对某整数k,1≤k≤δ+1,有则D是极大局部边连通的.接着又讨论了二部有向图和定向图的边连通性的度序列条件：定理3.2.3设D为n阶二部有向图,度序列为d1≥d2≥…≥dn(=δ).若δ≥[到+1或若δ≤[n/4]且对某整数k,1≤k≤δ,有则D是极大边连通的.定理3.2.5设D为n阶二部定向图,度序列为d1≥d2≥…≥dn(=δ≥2).若δ≥[n+3/8]或若δ≤[n+2/8]且对某整数k,1≤k≤4δ-1,有则D是超级边连通的.定理3.2.7(1)设D为n阶二部定向图,度序列为d1≥如≥…≥dn(=δ≥1),△’=△’(D).若δ≥[n+1/8]或若δ≤[n/8]且对某整数k,1≤k≤4δ,有则D是极大局部边连通的.(2)设D为n阶二部定向图,度序列为d1≥d2≥…≥dn(=δ≥2),△'=△'(D).若δ≥[n+/3]或若δ≤[n+2/8]且对某整数k,1≤k≤4δ-1,有则D是超级局部边连通的.最后,主要讨论了定向图极大边连通与超级边连通的倒数度条件：定理4.1.4设图D为无三角形连通n阶定向图,最小度为δ,边连通度为λ,若δ≥[n/8]+1或若δ≤[n/8]且则D是极大边连通的.定理4.2.3令D为强连通无三角形n阶定向图,最小度为δ≥2,边连通度为λ.若δ≥[n+3/8]或δ≤[n+2/8]且则D是超级边连通的.
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【参考文献】

中国期刊全文数据库 前1条

1 邵光凤;高敬振;;极大局部边连通和超级局部边连通有向图的度条件[J];科学技术与工程;2011年23期

，

本文编号：1188209