正则图的受限边连通性（英文）

一、正则图的限制性边连通度(英文)（论文文献综述）

张明祖^[1]（2018）在《图的边等周问题及其应用》文中指出图G的边等周问题是指在图G中找到m个点构成的顶点子集,满足从图G中分离出此集合所需要删除的边数是在所有从图G中分离出来任意m个顶点子集所需要删除的边数最少的.图的边等周问题自1964年Harper提出后,在网络可靠性连通度参数估计,图嵌入边阻塞数和全线长参数研究,光网络波分复用技术波长估计以及布尔函数势函数研究中得到了广泛应用.给定一个连通图G =（V,E）和正整数h≤（?）｜V（G）|/2（?）,abrega和Foil在1996年首次提出的h-extra边连通度的概念（有时也叫h-限制性边连通度）.图G的h-extra边连通度,如果存在的话,记为λh（G）,定义为可以删除的最少的边数满足删除这些边图G不再连通,每个连通分支至少有h顶点.本文主要以可用字典序提供边等周问题最优解的图为中心,以h-extra边连通度和图嵌入时边阻塞数和全线长参数的估计为背景展开研究.在第二章中研究了字典序提供幂图边等周问题最优解的情况下,利用数字表示理论和δ（G）-序列精确地给出此时幂图的边等周问题的优解的显示表达式.作为应用,分别研究了以n-维折叠立方体FQn,n-维一一对应连接互连网络Bn和3-元 n-方体Qn3为并行分布式网络计算网络的拓扑结构的h-extra边连通度问题.第三章主要研究FQn的h-extra边连通度λh（FQn）.由于FQn具有N= 2n个顶点,λh（FQn）对任意的1≤h<≤2n-1都有定义.我们研究了以下三种情况:（1）当n>6,1 ≤ h≤2（?）n/2（?）+1时,计算λh（FQn）的精确值和确定λh-最优的问题.该结论包含若干当h ≤ n时的已知结论.（2）当2（?）n/2（?）+r-lr≤h≤2（?）n/2（?）+r时,得到λh（FQn）为（（?）n/2（?）-r+ 1）2（?）n/2（?）+r,其中r = 1,2,…,（?）n/2（?）-1,当n是奇数时,设lr= 3 当n是偶数时lT=22r+1-2/3.（3）当1≤h≤2n-1时,设计出一个O（log2（N））算法,计算λh（FQn）的精确值和确定λh-最优的问题.该算法使得λh（FQn）的问题完整解决.第四章主要研究Bn的h-extra边连通度λh（Bn）.我们研究了以下两种情况:（4）当h≤2n-1时,找到了关于h的满足λh（Bn）=（n-c）2c的充分必要条件,其中c为非负整数c≤ n-1,该结论包含若干当1 ≤ h ≤ 2[n/2]+1和[2n-1/3]≤h ≤ 2n-1时的已知结论;（5）当1≤h≤2n-1时,也设计出一个O（log2（N））算法,计算λh（Bn）的精确值和确定λh-最优的问题.该算法使得λh（Bn）的问题完整解决.第五章研究了 3-元n-方体网络当1 ≤ h≤3[n/2]和h = 3c,0 ≤ c ≤ n-1时,λh（Qn3）的精确值和λh-最优的问题,该结论包含若干当h≤3时的已知结论.在第六章研究了当把彼此不同构的n-维一一对应连接互连网络Bn嵌入在一条路上时,具有共同的最小的边阻塞数EC（Bn,P2n）=[2n+1/3],共同的最小全线长WL（Bn,P2n）= 22n-1-2n-1.并得到在路上能够达到最小的边阻塞数的边的集合构成了一个康托集.

林辉球^[2]（2010）在《k-正则双轨道图的条件连通度》文中研究表明利用图来研究互联网络的拓扑结构已经被计算机科学工作者广泛接受和运用,图论中（边）连通度的概念是用来研究网络可靠性的一个重要参数,它能准确的刻画小规模网络的容错性.但是,对于大规模网络而言传统连通度就容易低估其可靠性.随着大规模网络的发展,我们有必要改进传统连通度的概念.基于传统连通度的不足,Harary在文献[4]中介绍了条件连通度的概念.设G是一个无向简单图, P是一个图性质. Harary在[4]中定义条件边连通度λ(G;P为所去掉的最小点数（边数）使得G不连通并且每个分支具有图性质P.边集F称为是限制性边割如果G ? F不连通且不含孤立点. G中基数最小的限制性边割称为限制性边连通度,用λ（G）来表示.图G称为是λ-最优的如果λ（G） =ξ（G）,其中ξ（G） = min{dG（u） + dG（v） ? 2 : uv∈E（G）}.图G的圈边割指的是一个边割集,去掉它之后分离出2个圈.如果G有一个圈边割,则称G为圈边可分离的.对一个圈边可分离的图G,圈边连通度cλ（G）是G的基数最小的圈边割.设ζ（G）=min{ω（X）|X是G中导出的最小圈},其中ω（X）是一个端点在X另一个端点在V （G） ? X的边的边数.圈边可分离图G如果有cλ（G） =ζ（G）,则称为是圈边最优的.在本文中,我们得到k（≥3）-正则连通双轨道图是λ-最优的充分条件.同时我们也讨论了正则双轨道图的圈边连通度.

王建伟^[3]（2010）在《容错网络中若干问题研究》文中研究说明本文考虑互连网络中的容错性和容错网络的路嵌入问题.习知,互连网络的拓扑结构可以用图G=（V,E）来作为数学模型,图G中的点表示互连网络中的元件,G中的边表示元件之间的通信连线.那么,图G的点连通度κ（G）和边连通度λ（G）则是该互连网络可靠性的重要度量参数.它们表明对应的互连网络可以容许κ（G）-1个元件或者λ（G）-1条连线同时发生故障的情况下,剩余网络的元件之间仍能保持通信.所以,图的点连通度或者边连通度越大,它所模拟的互连网络的可靠性越高.目前,互连网络最广泛采用的拓扑结构是n维超立方体Qn,它的点连通度和边连通度都是n.为了更准确地度量网络的容错性,人们根据网络应用的实际推广图的连通度概念到超连通度.图G的超点连通度κs（G）（或者超边连通度λs（G））是最小点数（或者边数）,这个数目的点集（或者边集）从G中移走会导致剩下的图不连通并且不含孤立点.Esfahanian （1989）已经证明：n维超立方体Qn的超点连通度和超边连通度都是2n-2.这意味着,即使Qn中有2n-3条边同时发生故障,只要确保每个点关联至少一条非故障边,那么Qn中任何两个非故障点之间仍然存在由非故障边组成的路.徐俊明等人（2003）证明了：当Qn（n≥4）至多有2n-3条故障边,而且每个点关联至少一条非故障边时,对于Qn中任何两点u和v,如果它们之间的距离d满足2≤d≤n-2且n≥4,那么u和v之间存在长不超过d+4且不含故障边的路.另一方面,Chan和Lee（1991）证明了：Qn （n≥3）存在2n-4条故障边,而且每个点关联至少两条非故障边,但Qn中不存在不含故障边的Hamilton圈.这个事实说明：如果Qn（n≥3）有2n-4条故障边,而且每个点关联至少两条非故障边,那么,对于一条非故障边uv,Qn中有可能不存在不含故障边且长为2n-1的uv路.本文证明了：如果Qn（n≥3）至多有2n-5条故障边,而且每个点关联至少两条非故障边,那么对Qn中任何不同两点u和v,其距离为d和满足d+4≤e≤2n-1和e-d≡0（mod 2）的整数e,Qn中存在一条不含故障边且长为e的uv路.这个结果改进了许多有关超立方体网络边容错泛圈性和泛连通性的已知结果,也为超立方体网络的高容错性提供更有力的理论证据.本文的另一部分是研究超立方体的变形网络VQn和超立方体的推广-置换图（G0,G1；M）的超点连通度和超边连通度.证明了VQn的点连通度和边连通度都是n,超点连通度和超边连通度都是2n-2.对于两个k正则k连通图G0和G1的置换图G=G（G0,G1；M）,我们给出了κs（G）>κ（G）和λs（G）>λ（G）的充分和必要条件,κs（G）=2κ和λs（G）=2κ的充分条件.作为应用,超立方体网络Qn,纽立方体网络TQn,交叉立方体网络CQn,Mobius立方体网络MQn,局部纽立方体网络LQn和变形超立方体网络VQn的超点连通度,超边连通度,限制点连通度和限制边连通度都等于2n-2.这些结果为这些网络的可靠性和容错性提供更精确的度量.

刘清海^[4]（2009）在《图的高阶连通性》文中研究表明随着信息网络的飞速发展,许多相关的理论问题开始引起人们的重视,其中之一是网络的可靠性,即网络在它的某些部件（节点或者连接）发生故障的条件下仍能工作的能力.网络拓扑结构通常被模型化为图或有向图,因此,图论中的一些经典概念,如连通度和边连通度,就被用来研究网络的可靠性.为了进一步研究,人们提出了各种各样的高阶连通性的概念,如super-κ性、hyper-κ性和κ-限制性边连通度λκ等.本文主要研究各种连通性问题.本文共分四章.第一章,我们介绍了研究背景和一些基本概念.对各类连通度问题研究的历史与现状进行了一定程度的综述.第二章,我们用围长和直径给出了λκ-最优图的一个充分条件,并且这个条件是对前人结果的一个改进.第三章,我们求出了Harary图的所有可能的λκ和ξκ,由此完全刻画了Harary图的λκ-最优性.第四章,我们研究限制性点连通度κκ和κ’κ,其中κ’κ为我们定义的一类新的图参数,可以做为hyper-κ性的一种度量,并给出了κκ和κ’κ的存在性和上界的一些充分条件以及两种限制性点连通度的性质和关系.

洪艳梅^[5]（2009）在《极小限制性边连通图的最优性和超边连通图的容错性》文中进行了进一步梳理随着信息网络的飞速发展,网络的可靠性越来越受到人们的重视.网络可靠性的传统的衡量标准为边连通度λ（G）.后来为了更深入的研究,人们提出了各种各样的高阶连通性的概念,如m-限制性边连通度λm（G）,λm-最优性,superλm性等.一个图G称为极小m-限制性k-边连通图是指λm（G）=k并且对任意e∈E（G）有λm（G-e）<k.我们证明了极小2-限制性k-边连通图总是λ2-最优的.这说明极小2-限制性k-边连通图总是有一条度为k的边.从而引出了极小2-限制性k-边连通图中度为k的边的计数问题,我们证明了每个极小2-限制性k-边连通图至少有3条度为k的边,当k≠4时,至少有4条度为k的边,并且给出例子表明这些界都是紧的.接着,我们也类似地考虑极小3-限制性k-边连通图,并证明除了3-维立方体外这种图都是λ3-最优的.最后,我们提出一种新的图参数:super-λ图的边容错度.一个super-λ图G称作m-super-λ是指对任意阶数不超过m的边集S（?）E都有G-S是super-λ的.这样最大的整数m称作超边连通图的边容错度,记作Sλ（G）.我们证明了min{λ2（G）-δ（G）-1,δ（G）-1}≤Sλ（G）≤δ（G）-1,并且对正则图和Cartesian积图给出了更精确的界.另外,我们还得出边传递图中Sλ（G）的确切的值.

桑镇^[6]（2009）在《关于k阶限制边连通度若干问题的研究》文中认为图的限制性边连通度问题及许多理论都是源自大型网络的设计和可靠性分析.另外限制性边连通度在实际问题中有着广泛的应用,是图论研究中一个很活跃的课题,各类限制边连通度问题被相继提出并加以发展、应用.当研究网络可靠性的时候,经常考虑这样一种图模型,它的节点不失效,但是它的连线,也就是边可以独立地等可能地失效,失效的概率是ρ∈（0,1）.这就是非常有名的Moore-Shannon网络模型[1,2].令G是一个Moore-Shannon网络模型,边数为h的边割的数目用Ch表示,如果G恰好有e条边,则它不连通的概率P（G,ρ）就可以表示为:显然,P（G,ρ）的值越小,网络的可靠性越好.如果能确定所有的系数Ch,那么这个网络的可靠性就确定下来了.但是对于任意图,Provan和Ball在文献[3]中指出,确定所有的系数Ch是一个NP-困难问题.用Ω（n,e）表示n个点e条边的图的集合,当ρ充分小时,在Ω（n,e）中为了最小化P（G,ρ）,边连通度λ（G）起了非常重要的作用.Bauer et al在文献[4]中指出,当ρ充分小时,对G1,G2∈Ω（n,e）,如果λ（G1）＞λ（G2）,则P（G1,ρ）＜P（G2,ρ）.为了更准确地确定这个可靠性, 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是λ3-最优图.定理2.4:若G是连通的二部图,且δ（G）≥3,|G|≥11,对于使d（x,y）＝2的点x,y都有d（x）＋d（y）≥2（?）＋6,则G是λ4-最优图.定理2.5:若G是连通的二部图,δ（G）≥5,对于使d（x,y）＝2的点x,y都有d（x）＋d（y）≥2（?）＋8,则G是λ5-最优图.在第三章中我们研究完全p部图k阶限制边连通度的存在性、有界性及完全二部图的最优性,主要有以下结果:定理3.4:若G为完全p部图K（r1）,（r2）,…,（rp）且G≠K1,（n－1）,r1＋r2＋…＋rp≥2k,则λk（G）存在且λk（G）≤ξk（G）.由此当p＝2时我们可得出推论3.5:若G为完全二部图Kr,s,r,s≥2,r＋s≥2k,则λk存在且λk（G）≤ξk（G）.定理3.6:若G是完全二部图Kr,s,则G是λk-最优图当且仅当r,s≥2,r＋s≥2k.在第四章中我们将给出图三阶限制边连通度最优性的一个充分条件:定理4.2:对图G,|G|≥6如果δ≥3且D≤g－4那么λ3（G）＝ξ3（G）.

张凤娟^[7]（2009）在《k阶限制边连通度的最优性和超级性》文中认为图的限制性边连通度问题及许多理论都是源自大型网络的设计和可靠性分析.另外限制性边连通度在实际问题中有着广泛的应用,是图论研究中一个很活跃的课题,各类限制边连通度问题被相继提出并加以发展、应用.如果不是特别说明,本文中谈及的所有图都是简单连通的.当研究网络可靠性的时候,经常考虑这样一种图模型,它的节点不失效,但是它的连线,也就是边可以独立地等可能地失效,失效的概率是ρ∈（0,1）.令G是一个网络模型,边数为h的边割的数目用Ch表示,如果G恰好有e条边,则它不连通的概率P（G,ρ）就可以表示为:显然, P（G,ρ）的值越小,网络的可靠性越好.如果能确定所有的系数Ch,那么这个网络的可靠性就是确定的.但是对于任意图,Provan和Ball在文献[1]中指出,确定所有的系数Ch是一个NP-困难问题.用Ω（n,e）表示n个点e条边的图的集合,当ρ充分小时,在Ω（n,e）中为了最小化P（G,ρ）,边连通度λ（G）起了非常重要的作用.当ρ充分小时,对G1,G2∈Ω（n,e）,如果λ（G1）>λ（G2）,则P（G1,ρ）<P（G2,ρ）.为了更准确地确定这个可靠性,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阶限制边割,简称为Rk-边割.若G有Rk-边割，则称G是λk-连通的,且G的最小Rk-边割(叫λk-边割)所含边数称为G的k阶限制边连通度,记为λk（G）.显然,λ（G） =λ1（G）≤λ2（G）≤…≤λk（G）.设X（?）V（G）,α（X）=|[X,（?）]|.记ξk（G）=min{α（X）:|X|=k,G[X]连通}.易见ξ1（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-,最优及超级-λ2连通的最小度条件,图是λ4-最优及超级-λ3连通的最小度条件,以及图是λ4-最优及超级-λ4连通的度和条件.在第四章中我们将给出k阶限制边连通度的最优性的一个度序列条件.在本文中,我们主要得到如下结论:定理2.3令n,q为正整数且n≥max{7,q+3},q≥31一个阶为n≥2q-1的图G非λ3,q-连通当且仅当G∈Wn*.（2）一个阶为n=2q-2的图G非λ3,q-连通当且仅当G∈{Wn*,R*（q-1,0,q-1）}.（3）一个阶为n=2q-3的图G非λ2,q-连通当且仅当G∈{Wn*,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是超级-λ2连通的.定理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且每个K4-e上都存在一点ω使得d（ω）≥[n/2]+3,则G是λ4-最优的.进而,若n≥12,则G是超级-λ3连通的.定理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）每个K4-e上都存在一点v使得d（v）≥[n/2]+3.定理3.3.5设G是一个n≥11阶连通图,若G满足以下条件,则G是超级-λ4连通的.（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）每个K4-e上都存在一点v使得d（v）≥[n/2]+4.定理4.3设G=（V,E）为n阶λk-连通图,其围长g>k+1.如果对G的任意连通子图H都有|E（H）|≤|V（H）|2/g,λk（G）≤ξk（G）且G的度序列d1≥d2≥…≥dn=δ满足则G是λk-最优的.

郭利涛^[8]（2008）在《图的3-限制性边连通度和3-限制性连通度》文中指出一个网络可以模型为一个图,网络的稳定性可以由该图的各种连通性指标来衡量.在本文中我们研究了其中一个参数,就是3-限制性点边连通度.一个连通图G = （V,E）的一个边集S叫做一个k-限制性边割,如果G ? S是不连通的,并且G?S的每一个分支至少含有k个点.一个图的k-限制性边连通度,记为λk（G）,就是最小的k-限制性边割所含边的数目.从这个参数的最近一些研究结果来看,λk越大,网络就越稳定.定义ξk（G） = min{ |[U,U]| : ? = U ? V （G）,|U| = k且G[U]连通},这里|[U,U]|是一端点在U中,另一端点在U中边的数目,U = V U.在大多数情况下,ξk（G）是以λk（G）为上界的.因此在这种意义下一个图G称做λk-最优的,如果λk（G） =ξk（G）.点集X是G的一个k-限制性割,如果G ? X是不连通的并且G ? X的每个分支至少有k个点.G的k-限制性连通度κk（G） （简称κk）是一个最小的k-限制性割的基数.X称作κk-割,如果|X| =κk.论文共分三章.在1.1节,我们主要介绍稳定性参数的一些背景和一些基本概念. 1.2节介绍本文所做的主要结果. 2.1节主要证明了若G是一个不含三角形的λ3-连通的图.如果对所有不相邻的点u,v都有|N（u）∩N（v）|≥3 ,那么G是λ3-最优的. 2.2节证明了设G是一个不含三角形的λ3-连通的图阶数n≥6,度序列d1≥d2≥...≥dn =δ.如果im=a1x {1,δ?3}dn?i≥max{1,δ? 3}12（ n2 + 3 ? n?25）,则G是λ3-最优的.更一般的,设p≥3是一个整数,G是一个不含三角形的λ3-连通的图阶数n≥6 ,团数ω（G）≤p,度序列d1≥d2≥...≥dn =δ.若则G是λ3-最优的.第3章证明了设G是一个连通图,围长g≥6,δ≥3,直径为D.假设存在一条2-路u0u1u2有d（u0）+d（u1）+d（u2）?4 =ξ3（G）使得对每个圈u0u1u2u3u4u5u0（如果存在）满足d（u4）≥4.那么κ3（G） =ξ3（G）,如果下面结论之一成立:（1） D≤g ? 4.（2） g是偶数. D = g ? 3且对每对距离d（u,v） = g ? 3的点u,v使得u和v都不在一个g长圈上.（3） g是偶数.对所有距离d（u,v）≥g ? 3的点u,v有|N（g?4）/2（u）∩N（g?2）/2（v）|≥3.（4） g≥8是偶数.假设设对所有距离d（u,v）≥g ? 3的点u,v,集合N（g?4）/2（u）∩N（g?2）/2（v）至少包含两个不同点x1,x2使得2≤d（x1,x2）≤（g ? 4）/2且对任意w∈N（g?4）/2（v）∩（N（x1）∪N（x2））满足d（w,xi）≥（g ? 4）/2 if w∈N（xj）,i = j; i,j∈{1,2}.

张钦锋^[9]（2008）在《图的k-限制边连通度的存在性及上界》文中指出图论的研究始于200多年前.关于图论的第一篇论文是1736年Euler发表的,他用图的方法解决了哥尼斯堡七桥问题.二十世纪三十年代以来,图论在科学界异军突起,活跃非凡.图论中有很多着名的问题,如哈密顿问题,四色问题,中国邮递员问题等,并且应用图论来解决化学,生物学,信息和计算机科学等学科问题已显示出极大的优越性.同时,图论在工程技术领域及社会科学中也有着广泛的应用.它作为离散数学的一个重要分支,受到了各方面的普遍重视.条件边连通度是分析和刻画图的有力工具,有大量的问题可以归结为图的条件边连通度问题,所以这方面是图论的热点研究领域.目前,互联网络已经与人们的工作、日常生活等方面息息相关.网络的可靠性和容错性是近年来国内外研究的热点问题.我们知道,连通度是反映图的连通性质的一个重要参数.而要精确地刻画图的连通性质,经典连通度存在着不足:首先,连通度相同的图可靠度可能不同.其次,不能区分删掉κ个割断点或λ条割断边得到的图的不同类型,即未考虑对网络的伤害程度.第三,默认图的任何子集中所有元素能潜在地同时失效.为克服以上不足,自然要将经典连通度的概念加以推广.自1983年Harary[3]提出条件连通度的概念以来,经过二十来年的发展,条件连通度所涉及的内容日益丰富和具体,象限制边连通度等.设计和分析大规模网络的可靠性和容错性时,通常包括某些类型的图模型.针对不同的模型,都有诸多相关理论问题需要研究.其中一个重要模型是这样的网络G:其节点不会失效,但节点间的连线可能相互独立地以等概率p失效.则G不连通的概率为,其中e为G的边数,Ch表示基数为h的边割的数目.则图G的可靠度为.确定P（G,p）的问题在可靠度的研究中受到了广泛关注.但Provan和Ball[4]已经证明,对一般图G,P（G,p）的计算是NP-hard的.为此,Esfahanian和Hakimi[5]提出了限制边连通度的概念.本文在前人工作的基础上,继续研究限制边连通度的相关性质.在第一章中,我们主要介绍了本文的研究背景以及已有的一些结果,以及文章中所涉及的一些概念和术语符号.G = （V,E）是连通图,S是G的边子集,若G - S不连通且G - S的每个分支至少有k个点,则S称为G的k-限制边割,记为Rk-边割. G的k-限制边割的最小基数称为G的k-限制边连通度,记为λk（G）或λk.ξk（G）=min {（?）（X） :| X |= k,G[X]连通},这里G[X]表示点集X在G中的导出子图.在第二章中,对直径D（G） = 2的图的k-限制边连通度进行了研究,得到了下面的结果:定理2.2设G是一个直径为2的图,则或者对于任意的λk（G）存在;或者G恰好含有一个饱和点,它是割点.称相邻于所有其它顶点的顶点为图的饱和点.在第三章的第一节中,具体讨论了关于3-正则图限制边连通度的存在性,得到了下面的结果:定理3.1.3设G是一个阶数至少是12的连通3-正则图,若,则λ6（G）存在.在第二节中,研究了正则图k-限制边连通度的上界问题,证明了下面的结果:定理3.2.6设G是一个正则连通图,若λ7（G）存在,则λ7（G）≤ξ7（G）.

霍美霞^[10]（2008）在《图的四阶限制边连通度的研究》文中研究指明图的限制性边连通度问题及许多理论都是源自大型网络的设计和可靠性分析．另外限制性边连通度在实际问题中有着广泛的应用，是图论研究中一个很活跃的课题，各类限制边连通度问题被相继提出并加以发展、应用．如果不是特别说明，本文中谈及的所有图都是简单连通的，阶至少是8．当研究网络可靠性的时候，经常考虑这样一种图模型，它的节点不失效，但是它的连线，也就是边可以独立地等可能地失效，失效的概率是ρ∈（0，1）．这就是非常有名的Moore-Shannon网络模型[1，2]．令G是一个Moore-Shannon网络模型，边数为h的边割的数目用Ch表示，如果G恰好有e条边，则它不连通的概率P（G，ρ）就可以表示为：显然，P（G，ρ）的值越小，网络的可靠性越好．如果能确定所有的系数Ch，那么这个网络的可靠性就是确定的．但是对于任意图，Provan和Ball在文献[3]中指出，确定所有的系数Ch是一个NP-hard问题．用Ω（n，e）表示n个点e条边的图的集合，当ρ充分小时，在Ω（n，e）中，为了最小化P（G，ρ），边连通度λ（G）起了非常重要的作用．Bauer et al．在文献[6]中指出，当ρ充分小时，对G1，G2∈Ω（n，e），如果λ（G1）>λ（G2），则P（G1，ρ）<P（G2，ρ）．为了更准确地确定这个可靠性，Esfahanian和Hakimi在文献[4]中引入了限制边割和限制边连通度．Fabrega和Fiol将限制边连通度的概念进一步推广，提出了k阶限制边割和k阶限制边连通度的概念[5]．目前，对于k=1，2，3的情况已经有了广泛而深入的研究．在本文第一章中，我们主要介绍了文章所涉及的一些概念、术语和符号．记图G的顶点集为V（G），边集为E（G）．对于X（?）V（G），令G[X]表示x的导出子图，（?）=V（G）-X，[X，（?）]表示G中一端在X中，另一端在（?）中的边的集合．如果G是一个连通图，S（?）E（G）使得G-S不连通，且G-S的每一个分支至少有4个点，则S称为是G的一个四阶限制边割．G中所有四阶限制边割的最小阶称为是G的四阶限制边连通度，用λ4（G）表示．如果λ4（G）存在，则称G是λ4-连通的．如果G中的一个四阶限制边割满足|S|=λ4，则S称为λ4-割．在第二章中，我们研究图的四阶限制边连通度的存在性问题．阶至少为8的连通图F若含有一个割点s使得F-s的每一个分支的阶至多是3，则称F为4-花．三角形每个顶点粘合一个3阶完全图的子图所构成的图，称为三角支撑图．利用这两类图我们刻画了阶至少是9的非λ4-连通的图．在文献[20]中，欧见平证明了阶至少是11的λ4-连通图G满足λ4（G）≤∈ξ4（G），其中ξ4（G）=min{|（X，（?））|：X（?）V（G），|X|=4，G[X]是连通的}，本文第三章对这个定理给出了一个简洁的证明．满足λ4（G）=ξ4（G）的λ4-连通图G称为是λ4-最优的．如果X（?）V（G），[X，（?）]是一个λ4-割，则X称为G的一个λ4-碎片．令r4（G）=min{|X|：X是G的一个λ4-碎片}，在第四章中我们将证明：一个δ（G）≥4的λ4-连通图G如果不是λ4-最优的，则r4（G）≥（?）+1．最后，我们研究完全二部图的λ4-最优性．在本文中，我们主要得到如下结论：定理2．6设G是阶至少为9的简单连通图，则G的四阶限制边连通度λ4（G）不存在，当且仅当G是4-花或是三角支撑图．定理4．1．3一个δ（G）≥4的λ4-连通图G如果不是λ4-最优的，则r4（G）≥（?）+1．定理4．2．3设G是一个λ4-连通的无三角图，如果G不是λ4-最优的，则r4≥max{5，2δ（G）-3}．定理4．3．1设r，s≥2，r+s≥8，则λ4(Kr,s)存在，且λ4(Kr,s)≤ξ4(Kr,s)．定理4．3．2设r，s≥2，r+s≥8，则Kr,s是一个λ4-最优图．

二、正则图的限制性边连通度(英文)（论文开题报告）

（1）论文研究背景及目的

此处内容要求：

首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。

写法范例：

本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。

（2）本文研究方法

调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。

观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。

实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。

文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。

实证研究法：依据现有的科学理论和实践的需要提出设计。

定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。

定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。

跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。

功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。

模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。

三、正则图的限制性边连通度(英文)（论文提纲范文）

（1）图的边等周问题及其应用（论文提纲范文）

（2）k-正则双轨道图的条件连通度（论文提纲范文）

（3）容错网络中若干问题研究（论文提纲范文）

（4）图的高阶连通性（论文提纲范文）

（5）极小限制性边连通图的最优性和超边连通图的容错性（论文提纲范文）

（6）关于k阶限制边连通度若干问题的研究（论文提纲范文）

（7）k阶限制边连通度的最优性和超级性（论文提纲范文）

（8）图的3-限制性边连通度和3-限制性连通度（论文提纲范文）

（9）图的k-限制边连通度的存在性及上界（论文提纲范文）

（10）图的四阶限制边连通度的研究（论文提纲范文）

四、正则图的限制性边连通度(英文)（论文参考文献）

• [1]图的边等周问题及其应用[D]. 张明祖. 厦门大学, 2018(07)
• [2]k-正则双轨道图的条件连通度[D]. 林辉球. 新疆大学, 2010(02)
• [3]容错网络中若干问题研究[D]. 王建伟. 中国科学技术大学, 2010(09)
• [4]图的高阶连通性[D]. 刘清海. 新疆大学, 2009(01)
• [5]极小限制性边连通图的最优性和超边连通图的容错性[D]. 洪艳梅. 新疆大学, 2009(01)
• [6]关于k阶限制边连通度若干问题的研究[D]. 桑镇. 山东师范大学, 2009(10)
• [7]k阶限制边连通度的最优性和超级性[D]. 张凤娟. 山东师范大学, 2009(10)
• [8]图的3-限制性边连通度和3-限制性连通度[D]. 郭利涛. 新疆大学, 2008(02)
• [9]图的k-限制边连通度的存在性及上界[D]. 张钦锋. 山东师范大学, 2008(08)
• [10]图的四阶限制边连通度的研究[D]. 霍美霞. 山东师范大学, 2008(10)

标签：连通图论文;  超立方体论文;  正则论文;  可靠性分析论文;  图论论文;