导读:本文包含了边连通性论文开题报告文献综述及选题提纲参考文献，主要关键词:k元n立方体,容错性,强Menger边连通性,条件边容错
边连通性论文文献综述
翟登鑫[1]（2019）在《k元n立方体的条件容错强Menger边连通性》一文中研究指出研究了k元n立方体的强Menger边连通度,并证明了k元n立方体Q■(n≥2,k≥3)是3n-3条件容错强Menger边连通的.(本文来源于《沈阳大学学报(自然科学版)》期刊2019年02期）
裴建峰[2]（2018）在《超图的超级边连通性和限制边连通度》一文中研究指出图的边连通度是度量网络的重要参数.当用边连通度作为度量时,最可靠的网络对应两类极图:极大边连通图和超级边连通图.为了更精确地描绘图的连通性,Esfa-hanian和Hakimi于1988年引入了图的限制边连通度.超图是图的一个自然推广,它可用于研究多元子集问题,分析有限集中各元之间的多元关系,并可描述最具一般性的离散结构关系.在计算机领域中,若把多机系统中的处理机看作超图的顶点,把总线看作超图的边,一个多处理机系统就可抽象为一个超图.关于图的边连通度和限制边连通度,研究者已经给出许多结果.但对于超图相应的研究还比较少.本文共分为叁章,研究超图的边连通度和限制边连通度.第一章先给出文中要使用的图论基本概念和记号,然后介绍本文的研究背景、主要概念和主要结果.第二章首先说明超图的超级边连通性和极大边连通性之间的关系,并证明交叉超图一定是超级边连通的.随后,将完全图的概念推广到超图,给出它们的一些性质.此外,也给出超级边连通超图的最小度条件和直径条件,并用例子说明这些条件的最优性.第叁章将限制边连通度以及极大限制边连通性的概念推广到超图.首先给出限制边连通超图的一个充分条件以及它的限制边连通度的一个上界,用例子说明所得结果的最优性.然后,给出极大限制边连通超图的最小度条件和直径条件.(本文来源于《山西大学》期刊2018-06-01）
陈金阳,朱文慧,江秉华[3]（2016）在《变换图G~(++-)的圈边连通性（英文）》一文中研究指出研究了变换图G~(++-)的圈边连通性问题,利用枚举分析法获得了变换图G~(++-)是圈可分图的充要条件.进一步得到变换图G~(++-)的圈边连通度的界.(本文来源于《兰州大学学报(自然科学版)》期刊2016年03期）
张磊[4]（2015）在《图的限制边连通性与哈密尔顿性》一文中研究指出多处理机系统的互连网络拓扑通常以图为数学模型,因此网络拓扑的性能可以通过图的性质和参数来度量.在设计和选择多处理机系统的互连网络拓扑时,我们要考虑的一个问题是系统的可靠性(容错性).边连通度λ(G)是度量网络可靠性的一个重要参数.通常,边连通度A(G)越大,网络越可靠.但是,这个参数有一个明显的缺陷：它假定系统的任何部分都可能同时损坏,这在实际应用中几乎不可能发生.为弥补这个缺陷,Fabrega和Fiol提出了k限制边连通度的概念.对于互连网络来说,有一类重要的问题,是在某一个网络上模拟另外一个网络,这个问题被称为网络嵌入问题.图的嵌入是把客图映射到主图.许多应用,如建筑仿真,处理器分配,和超大规模集成电路芯片设计,可以建模为图的嵌入.本文主要研究图的k限制边连通性和Hamiltonian性.本文共分五章.第一章首先给出本文将用到的图论方面的术语和记号,然后综述图的k限制边连通性和Hamiltonian性的应用背景和研究进展,最后概述了本文的研究内容和获得的主要结论.作为边连通度的推广,k限制边连通度是度量图的连通性的一个重要参数.当k=2时,2限制边连通度通常被称为限制边连通度.2012年,Holtkamp等研究了非极大限制边连通无3-圈图的λ2-碎片的基数的下界和非极大k限制边连通无3-团图的Ak-碎片的基数的下界.进一步,给出了极大限制边连通无3-圈图和极大k限制边连通无3-团图的充分条件.第二章主要研究无(p+1)-团图和围长为g的图的极大k限制边连通性.我们首先给出了一个非极大k限制边连通且无(p+1)-团图的λk-碎片的基数的下界.其次,我们给出了一个围长为9的非极大k限制边连通图的λk-碎片的基数的下界.最后,一些极大k限制边连通图的充分条件被给出.近年来,图的极大限制边连通性和极大3限制边连通性得到了广泛的研究.但是关于更一般的k限制边连通性研究略少.这需要被推广到更一般的情形.2004年,Hell-wig和Volkmann证明了：如果λ'-连通图G中所有不相邻顶点u,v都满足N(u)∩N(v)|≥2,且G中每个叁角形T中都存在一点u使得d(v)≥[(v(G))/2]+1,那么G是极大限制边连通的.第叁章主要研究了图的极大k限制边连通性和超级k限制边连通性.我们首先给出了一个图是极大k限制边连通的充分条件,这个结果推广了上面的结论.其次,我们证明了如果G中任意一对不相邻顶点都有d(u)+d(v)≥v(G)+2k-4且G不属于一类特殊图,那么G是极大k限制边连通的.最后,我们给出了一个图是超级k限制边连通的度条件.k等周边连通度是一个与k限制边连通度密切相关的概念.它也是度量网络可靠性的一个重要的参数.2009年,Wang等人证明了一个阶至少为2k的图G,如果G中任意一对不相邻顶点u,v都满足W(u)∩N(u)|≥2k-1,那么G是极大k等周边连通的.第四章主要研究极大k等周边连通图的邻域交条件.我们首先给出了一个在k等周边连通图中,由γk-碎片生成的子图中存在(k-1)-路的充分条件.其次,我们给出了极大等周边图的一个邻域交条件,这个是上面结果的一个改进.最后研究了直径为2的图的极大k等周边连通性.一个图G中的Hamiltonian圈是指经过G中每个顶点恰好一次的圈Hamiltonian圈的嵌入是图论中的一个热点问题.第五章主要研究直径为2的图中的Hamiltonian圈.首先,我们给出了相关的概念和结果.然后,我们证明了如果对于阶至少是3的图G中任意一对不相邻顶点都有N(u)∩N(u)|≥[v/2]-1,且G不属于一类特殊图,那么G是一个Hamiltonian图.(本文来源于《山西大学》期刊2015-06-01）
张慧云[5]（2015）在《有向图和定向图的边连通性与点连通性研究》一文中研究指出近年来,随着大规模集合电路,微电子技术,大规模互联网络的飞速发展,人们对网络的拓扑结构要求越来越高.图的理论及其在各个领域的广泛应用越来越受到数学界和其他科学界的重视.网络的可靠性和容错性受到人们的普遍关注.图论中图的连通性分析为此类问题的研究提供了重要的理论依据.设计和分析多处理机互联网络时,通常会涉及某些类型的网络模型,利用图的点和边来代替网络的节点和连线,以此构成相互连通的网络的拓扑结构.通常将网络的拓扑结构抽象成图或有向图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-04-10）
王艳红[6]（2015）在《有向图和定向图的边连通性研究》一文中研究指出图论是一门古老而又活跃的学科,也是一门很有实用价值的学科.它是研究工程技术,自然科学等的重要数学工具,应用极为广泛.在现代社会中,人们的日常生活,学习和工作与多处理机互联网络的关系也越来越密切.因此网络的可靠性和容错性受到人们的普遍关注,从而网络的可靠性和容错性的研究成为了近年来国内外研究的一大热点.在设计和分析大规模互联网的可靠性和容错性时,一个很重要的模型是将网络的拓扑结构抽象成图或有向图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-04-10）
张娟[7]（2014）在《两类网络有关条件边连通性的研究》一文中研究指出用图研究互联网络的基础拓扑结构已被工程技术人员和计算机科学工作者广泛接受和运用。当用图来表示互联网络时,图论中的边连通度是研究网络可靠性和容错性的一个重要参数,它能准确地刻画小规模网络的边容错性。但是,对于大规模网络,传统的边连通性就容易低估其可靠性。随着大规模网络的发展,有必要改进传统的边连通性的概念。本文讨论了边连通度的推广概念,即k限制边连通度,超k限制边连通及超k限制边连通度的边容错概念。重点研究了当k为1、2、3时超立方体网络和它的变形网络折迭超立方体网络这两类常见且重要的网络关于超k限制边连通性的问题,并确定了相应的值。通过一些已知结论,获得的主要结果有以下几个：对于超立方体Qn,在n≥4时关于超边连通度的边容错、在n≥5时关于超限制边连通度的边容错以及在n≥6时关于超3限制边连通度的边容错均为n-1；对于折迭超立方体FQn,在n≥3时关于超边连通度的边容错、在n≥2时关于超限制边连通度的边容错以及在n≥5时关于超3限制边连通度的边容错均为n.(本文来源于《中国科学技术大学》期刊2014-05-01）
高敬振,吴芳[8]（2014）在《图的局部k限制边连通性及最优性》一文中研究指出首先研究图的局部k限制边连通性问题和局部λ_k-连通图的存在性问题.然后研究图的局部λ_k最优性,并且应用邻域条件得到了一个保证图局部λ_k最优的充分条件.(本文来源于《数学的实践与认识》期刊2014年08期）
杜涛[9]（2014）在《图的边连通性与点连通性研究》一文中研究指出图论是一门古老却又十分活跃的学科,也是一门很有实用价值的学科.作为组合数学和离散数学的重要分支,它是研究自然科学,工程技术等的重要数学工具,应用极为广泛.在经济发展的时代,其与计算机科学和网络理论等方面的联系也越来越密切.图论中图的边连通度问题就源于大规模网络的设计及可靠性分析,在实际问题中有着极其广泛的应用.目前,边连通度已成为图论中的热点研究领域.对于多处理机互联网络的分析,通常会涉及某些类型的图论模型,利用图的点和边来代替网络的节点和连线,以此构成相互连通的网络的拓扑结构.一个重要的数学模型就是将其抽象化为无向图G=(V,E),其中G的顶点集代表所有的处理机,而边集代表系统中处理机之间的通信联系.因此网络拓扑的性能就可以通过图的性质来刻画了.在研究此类模型时,通常假设其节点不失效,而节点间的连线即边可相互独立地以等概率ρ∈(0,1)失效.则G连通的概率R(G,ρ)为其中ε为G的边数,λ(G)为边连通度,G(G)表示边数为i的边割的数目.显然R(G,ρ)越大,网络的可靠性越好.若能计算出所有系数Gi(G)(i=λ(G),λ(G)+1,.,ε),那么该网络的可靠性就能够确定.而对于一般图G,Provan和Ball于1983年证明了：R(G,ρ)的计算是NP-困难的.对网络的一个重要指标是希望其可靠性要尽可能好,而用图论的术语来讲,就是希望图的边连通度尽可能大.因此边连通度成为衡量图的连通性质的一个经典参数,也就成为反映网络可靠性的重要参数.而要更精确地刻画图的连通性,经典边连通度仍存在一些不足.首先,边连通度相同的图可靠性可能不同；其次,不能区分删掉λ条割断边后所得的图的不同类型；最后,默认图的任何子集中所有元素可能潜在地同时失效.为了更好地刻画图的连通情况,Harary[7]于1983年提出了条件边连通度的概念,为该领域的研究开辟了新的道路.从而,网络的可靠性与容错性的分析快速发展成为图论研究中的热门课题.为此,许多新的参数相继被提出来,其中包括极大边连通性、超级边连通性、限制边连通度和局部边连通度.目前,对于这一领域已有了广泛而深入的研究.本人将在前人工作的基础上,继续研究局部边连通和局部点连通的相关性质.本文讨论有限简单的图.在第一章中,主要介绍本文的研究背景,文中涉及的基本概念及术语符号及已有的一些结论.图G的边连通度λ(G)=min{|(x,y)|:φ≠X cV(G),Y=V(G)X},达到最小的(X,Y)叫G的λ-割.而Bauer等人也证明了λ(G)越大,网络的可靠性越好.因此,在网络设计中,我们也希望λ(G)尽可能大.对任意图G,显然有λ(G)≤δ(G),故当满足λ(G)≤δ(G)时,称G为极大边连通的,也称λ-最优的.为了更加精确地刻画网络的可靠性,局部边连通度的概念被提出.图G中两个顶点u和v的局部边连通度λ(u,v)=min{|(X,Y)|:u∈X∈V(G){v),Y=V(G)X},达到最小的(X,Y)叫G的λ(u,v)-割.显然有λ(u,v)≤min{d(u),d(v)},故当对任意顶点u和v,有λ(u,v)≤min{d(u),d(v)},时,称G是极大局部边连通的,简记为mlec.A.Holtkamp于2007年给出了无钻石图的定义以及相关的结论.从4阶完全图中去掉任意一条边所得到的图称为钻石图.图G是无钻图,若它不以钻石作为子图(不必是导出子图)A.Holtkamp于2011年给出了K2,p-free图的定义以及相关的结论K2,p-free图：p≥2是整数,若图G不以完全二部图K2,p作为子图.在第二章中,我们主要讨论了K2,p-free图的极大局部边连通性的充分条件,本文得到如下结果：定理2.1.4设G是n阶K2,p-free连通图(p≥3),最小度δ.若n≤4δ-2p+3,δ≥誓,则G是极大局部边连通的.推论2.1.5设G是n阶K2,p+1-free且无导出C4连通图,最小度δ.若n≤4δ-2p+1,p≥2,δ≥4(p+1)/3则G是极大局部边连通的.推论2.1.6设G是n阶K2,p+1-free且无导出C4连通图,最小度δ.若n≤4δ-2p+1,p≥2,δ≥4(p+1)/3,则G是极大边连通的.我们可以采用K2,p+1-free图来限制无C4图从而产生受限制于K2,p+1-free的无导出C4图是极大边连通的充分性判定条件：定理2.2.1设G是K2,p+1-free且无导出C4的n阶连通图,最小度δ.若n(G)≤4δ-2p+3,其中p≥3且δ≥2p,则G是极大边连通的.推论2.2.2设G是无C4子图的n阶连通图,最小度δ≥6.若n(G)≤4δ+1,则G是极大边连通的.在第叁章中,我们主要讨论了K2,p-free图的极大局部点连通性的充分性判定条件.定理3.1.5令p≥3是一个整数,G是K2,p-free的n阶连通图,最小度δ≥2p+m-2/2,其中m∈{0,1,2}.若n≤3δ-2p+3+m,则G是极大局部点连通的.定理3.2.2设G是K2,4-free且无导出C4的n阶连通图,最小度δ≥3.若n≤3δ-4,则G是极大连通的.在第四章中,我们主要利用无钻图的极大局部边连通性的已有结论,再利用团数来限制,从而得出依赖于团数的无导出钻图是极大局部边连通的充分性的判定条件,从而得到了下面的定理.定理4.6令G是一个不含导出钻的n阶连通图且团数ω(G)≤p,δ≥p≥3.若n≤4δ-2p+5,则G是极大局部边连通的.推论4.10令G是一个不含导出钻的n阶连通图且团数ω(G)≤p,δ≥p≥3.若n≤4δ-2p+5,则G是极大边连通的.在第五章中,类似于第四章,仍然是根据无钻图的极大连通性的已有结论,再利用团数来限制,从而产生依赖于团数的无导出钻图不是极大连通的充分性判定条件,得出以下定理：定理5.6设G是一个n阶,最小度6≥p≥3的无导出钻连通图,且团数ω(G)≤p.若连通度κ<δ,则κ≥4δ-n+6-2p.推论5.7设G是一个n阶,最小度δ≥p≥3的无导出钻连通图,p是整数,团数ω(G)≤p.若n≤3δ(G)-2p+6,则κ=δ.(本文来源于《山东师范大学》期刊2014-04-10）
林泽芳[10]（2014）在《有向图和图的边连通性与点连通性》一文中研究指出随着社会的不断进步,人们的生活、工作和学习与多处理机互联网络的联系越来越紧密.自然,网络的可靠性与容错性倍受关注,进而网络的可靠性与容错性分析就成为近年来国内外研究的热点之一.图论中图的连通性分析为此问题的研究提供了重要的理论支撑.在设计、分析大规模互联网络的可靠性和容错性时,通常将网络的拓扑结构抽象成图或有向图D=(V,E).这里D的顶点代表处理机,连接顶点的边表示一对处理机之间的直接通信联系(有向边则表示只能进行单向联系).在研究这种模型时,经常假设其节点不会失效,但每条边相互独立地以相等的概率p∈(0,1)失效.用m表示D的边数,λ(D)表示D的边连通度,Ci(D)表示D的边数为i的边割数目,则D不连通的概率为：从而可用D连通的概率R(D,p)=1-P(D,p)来衡量网络的可靠性.显然P(D,p)越小,网络的可靠性越好.但是对于一般图,确定所有的系数Ci是一个NP-困难问题.对此,Colbour[2]做了进一步的阐述.当假设D的边不会失效,但其节点相互独立地以相等的概率p∈(0,1)失效时也有类似的讨论.图或有向图的边连通度与点连通度是反映其连通性质的两个重要参数.但是,在精确刻画图或有向图的连通性方面,边连通度或点连通度存在一些不足：首先,边连通度或点连通度相同的图或有向图的可靠性可能有所不同.其次,不能区分删掉λ-割或κ-割后的图或有向图的不同类型,即未考虑网络的破坏程度.第叁,默认图或有向图的任何子集中所有元素可能潜在地同时失效.为克服以上缺陷,自1983年Harary[5]提出了条件边连通度的概念,经过叁十年的发展,边连通性所涉及的内容日益丰富和具体,包括超级边连通性、极大局部边连通性和超级局部边连通性等.类似的,在图的点连通性方面,也出现了极大连通性、极大局部连通性等概念.这些参数都能更深刻地刻画图或有向图的边、点连通性质.本人在前人工作的基础上,继续研究图或有向图的超级边连通性以及图的超级局部连通性等相关性质.在第一章中,我们主要介绍本文的研究背景和一些已有的结果,以及文章中涉及的一些基本概念、术语符号.记有限简单图或有向图D=(V(D),E(D)),其中V(D)表示D的顶点集,E(D)表示D的边集,称D的阶数为n=|V(D)|.不含来回边的有向图称为定向图.图或有向图D的边连通度λ(D)＝min{｜(X,Y)｜φ≠Xc V(D),Y=V(D)X),达到最小的(X,Y)称为D的A的λ-割.显然,λ(D)≤δδδ(D),故称满足λ(D)=δ(D)的图或有向图为极大边连通的.如果D的每个λ-割都是由发自某点或发至某点的边组成,则称D是超级边连通的,简记为超级-λ的.D中两个顶点u和v的局部边连通度λ(u,v)=min{|(X,Y)|:u∈X<y(D){v},Y=V(D)X),达到最小的(X,Y)叫D的λ(u,v)-割.显然λ(u,v)=min{d+(u),d-(v)},故当对任意顶点u和v都有λ(u,v)=min{d+(u),d-(v)}时,称D是极大局部边连通的,简记为：mlec若对任意顶点u和v,每个λ(u,v)-割都或者由发自u的边组成,或由发至v的边组成,则称D是超级局部边连通的,简记为slec显然,当D超级局部边连通时,其必定超级-λ和极大局部边连通.非完全图G的点连通度k(G)=min{|S｜:Sc V(G),G-S不连通},达到最小的S称为G的κ-割.完全图G的点连通度κ(G)=n(G)-1.显然κ(G)≤δ(G),当κ(G)=δ(G)时,称G为极大连通的.一个κ-割称为平凡的,若它由某顶点的所有邻点组成.称G是超级连通(简记为超级-κ)的,若其κ-割都是平凡的.图G中顶点u和v的局部连通度κ(u,v)定义为G中内点不交的u-v路的最大条数.显然,k(u,v)≤min{d(u),d(v)},若对任意的顶点u和v都有K(u,v)=min{d(u),d(v)},则称G是极大局部连通的.对D中的顶点u,记N+(-)(u)为u的外(内)邻点集.在第二章中,我们给出了二部定向图极大与超级局部边连通的邻域条件：定理2.1.4设D为n阶二部定向图,最小度δ≥3.若对任意同部顶点x,y,有并且则D是极大局部边连通的.定理2.2.3令D是n阶二部定向图,最小度δ≥4.若对任意同部顶点x,y,有并且则D是超级局部边连通的.然后又讨论了二部定向图超级局部边连通的度序列条件,得到了以下结果：定理2.2.5设D为二部定向图,度序列为d1≥d2≥…≥dn(=δ≥2),若δ≥[n+3/8]或若δ≤[n+2/8]且对某整数k,1≤k≤4δ-1,有则D是超级局部边连通的.在第叁章,我们首先给出了二部定向图超级边连通的度序列条件：定理3.1.2设D为二部定向图,度序列为d1≥d2≥…≥dn(=δ≥2).若δ≥[n+3/8]或若δ≤[n+2/8]且对某整数k,1≤k≤4δ-1,有则D是超级边连通的.对D中的边e=uu,令N+(e)=(N+(u)∪+N+(v){u,v),ξ+=min{N+(e):e∈E(D)}类似定义N-(e),ξ-.称ξN=∈N(D)=min{ξ+,∈-}为D的最小限制边数.结合最小限制边数,我们首先给出利用度序列的低度端保证有向图超级边连通的充分条件,并举例说明了其最好可能性.定理3.2.4设D为n阶非完全有向图,度序列为d1≥d2≥…≥dn(=δ).若ξN≥[n/2]+δ-1或若ξN≤[n/2]+δ-2且对某整数k,2≤k≤ξN-δ+2,有则D是超级边连通的.然后,又讨论了有向图超级边连通的边邻域条件,得到以下结果：定理3.2.7令D是n阶强连通有向图,边连通度为λ,最小度为δ.如果对每条满足max{d+(u),d+(u))≤[n/2]-1的边e=uv有且对每条满足max{d-(u),d-(v))≤[n/2]-1的边e=uv有则D超级边连通或D∈H*.最后,我们给出利用度序列的低度端保证图的超级边连通性的依赖团数的度序列条件,并举例说明了最好可能性.定理3.3.4设图G的团数ω(G)≤p,度序列为d1≥d2≥…≥dn(=δ≥3).(1)设p≠δ且p-1十δ.若n≤2[pδ/p-1]-1或若n≥2[pδ/p-1]≥2p且对某整数k,1≤k≤[δ/p-1],有则G是超级边连通的.(2)设p=δ或p-1|δ若n≤2[pδ/p-1]-3或若n≥2[pδ/p-1]-2且p=δ时对k=1有或若n≥2[pδ/p-1]-2≥2p-2且当p-1=δ时对k=1,当p-1|δ且p-1≠δ时对某整数k,1≤k≤δ/p-1,有则G是超级边连通的.笛卡尔乘积是构造大规模网络的常用方法,它可以保持小规模网格的许多性质.在第四章中,我们主要讨论了正则图笛卡尔乘积的超级局部连通性,得到了以下主要结果：定理4.2若d1-正则图G1与d2-正则图G2都是超级局部连通的,且d1,d2≥2,则G1×G2超级局部连通.(本文来源于《山东师范大学》期刊2014-04-10）
边连通性论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
图的边连通度是度量网络的重要参数.当用边连通度作为度量时,最可靠的网络对应两类极图:极大边连通图和超级边连通图.为了更精确地描绘图的连通性,Esfa-hanian和Hakimi于1988年引入了图的限制边连通度.超图是图的一个自然推广,它可用于研究多元子集问题,分析有限集中各元之间的多元关系,并可描述最具一般性的离散结构关系.在计算机领域中,若把多机系统中的处理机看作超图的顶点,把总线看作超图的边,一个多处理机系统就可抽象为一个超图.关于图的边连通度和限制边连通度,研究者已经给出许多结果.但对于超图相应的研究还比较少.本文共分为叁章,研究超图的边连通度和限制边连通度.第一章先给出文中要使用的图论基本概念和记号,然后介绍本文的研究背景、主要概念和主要结果.第二章首先说明超图的超级边连通性和极大边连通性之间的关系,并证明交叉超图一定是超级边连通的.随后,将完全图的概念推广到超图,给出它们的一些性质.此外,也给出超级边连通超图的最小度条件和直径条件,并用例子说明这些条件的最优性.第叁章将限制边连通度以及极大限制边连通性的概念推广到超图.首先给出限制边连通超图的一个充分条件以及它的限制边连通度的一个上界,用例子说明所得结果的最优性.然后,给出极大限制边连通超图的最小度条件和直径条件.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
边连通性论文参考文献
[1].翟登鑫.k元n立方体的条件容错强Menger边连通性[J].沈阳大学学报(自然科学版).2019
[2].裴建峰.超图的超级边连通性和限制边连通度[D].山西大学.2018
[3].陈金阳,朱文慧,江秉华.变换图G~(++-)的圈边连通性（英文）[J].兰州大学学报(自然科学版).2016
[4].张磊.图的限制边连通性与哈密尔顿性[D].山西大学.2015
[5].张慧云.有向图和定向图的边连通性与点连通性研究[D].山东师范大学.2015
[6].王艳红.有向图和定向图的边连通性研究[D].山东师范大学.2015
[7].张娟.两类网络有关条件边连通性的研究[D].中国科学技术大学.2014
[8].高敬振,吴芳.图的局部k限制边连通性及最优性[J].数学的实践与认识.2014
[9].杜涛.图的边连通性与点连通性研究[D].山东师范大学.2014
[10].林泽芳.有向图和图的边连通性与点连通性[D].山东师范大学.2014
标签：k元n立方体; 容错性; 强Menger边连通性; 条件边容错;