论文部分内容阅读
随着社会的不断进步,人们的生活、工作和学习与多处理机互联网络的联系越来越紧密.自然,网络的可靠性与容错性倍受关注,进而网络的可靠性与容错性分析就成为近年来国内外研究的热点之一.图论中图的连通性分析为此问题的研究提供了重要的理论支撑.在设计、分析大规模互联网络的可靠性和容错性时,通常将网络的拓扑结构抽象成图或有向图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超级局部连通.