随着社会经济和科技的发展，互联网络与人们的工作、日常生活等方面的关系越来越密切，自然，网络的可靠性和容错性倍受人们的关注．研究网络的可靠性和容错性是社会发展的必然趋势，是近年来国内外研究的热点之一．众所周知，边连通度是反映图的连通性质的一个重要参数．而要更精确地刻画图的连通性质，经典边连通度存在着不足之处：首先，边连通度相同的图的可靠度可能不同．其次，不能区分删掉K—点割或λ—边割得到的图的不同类型，即未考虑删掉点割或边割对网络的损害程度．第三，默认图的任何子集中所有元素可能潜在地同时失效，为克服以上缺陷，自然要将经典边连通度的概念加以推广．自1983年Harary[1]提出条件边连通度的概念以来，经过二十多年的发展，条件边连通度所涉及的内容日益丰富和具体，包括超级边连通度、过边连通度、限制边连通度等。 设计和分析大规模网络的可靠性和容错性时，通常涉及某些类型的图模型，针对不同的模型，都有诸多相关理论问题需要研究．其中一个重要模型是这样的图G=(V，E)：假设其节点不会失效，但节点间的连线相互独立地以等概率p∈(0，1)失效．则G不连通的概率为：其中e为G的边数，Ch表示边数为h的边割的数目．则图G的可靠度为1—P(G，p)．显然P(G，p)越小，网络的可靠性越好，因此，确定P(G，p)的大小问题在网络可靠度的研究中倍受关注，但Provan和Ball[2]已经证明，对一般图G，P(G，p)的计算是NP—困难的．为此，Esfahanian和Hakimj[3]提出了限制边连通度的概念．本文在前人工作的基础上，继续研究限制边连通度的相关性质．文中k总表示一个正整数，ω(G)表示图G的最大团的点数。 第一章，主要介绍了本文的研究背景和已有的一些结果，以及文中所涉及的一些概念和术语符号．1.令G=(V，E)是n(≥2k)阶连通图，S是G的一个边子集，若G—S不连通且G—S的每个分支至少有k个顶点，则称S为G的k—限制边割，记为Rk—边割．G的最小Rk—边割(叫λk—边割)所含边数称为G的k—限制边连通度，记为λk(G)或λk．若λk(G)存在，则称G是λk—连通的。2.设X，Y是图G=(V，E)的顶点集V的两个不交的非空子集或G的两个点不交的子图．G的一端点在X中且另一端点在Y中的边构成的集合记作[X，Y]．当X={x}时，用[x，Y]代替[X，Y]．记I(X)=[X，V—X]，称()(x)=|I(X)|为X的外度．令ξk(G)=min{()(X)：|X|=k，且G[X]连通}，这里G[X]表示X(()V)在G中的导出子图．令—X=V(G)—X．若[X，—X]是图G的一个λk—边割，则X称为λk—碎片．显然，若X是一个λk—碎片，则—X亦然．图G的含顶点数最少的λk—碎片称为G的λk—原子，其顶点数记为rk(G)。3.设G是λk—连通的，若λk(G)=ξk(G)，则称图G是λk—最优的。 第二章，讨论了5—限制边连通度的上界问题，得到以下结果：1. 3设G是阶至少为18的连通图．若G含5—限制边割，则λ5(G)≤ξ5(G)当且仅当G不属于^G5.其中^G5定义如下：阶至少为18，恰含一个5阶完全图K5，且K5的每个顶点上通过恰好一条边连接一个阶至多为3的连通图得到的图．2.设G是阶至少为18的λ5—连通且无三角形的图，若G不是λ5—最优的，则r5(G)≥max{6，28(G)—4}．3.设G是λ5—连通的，δ(G)≥6，U是G的λ5—原子，若G不是λ5—最优的，则对于任意的v∈U，有dG[U](v)≥4。 第三章，研究了正则图k—限制边连通度的存在性，得到下面的结果：1.设G是阶至少为2k的(k—3)—正则连通图(k≥5)，则G的k—限制边连通度λk(G)存在当且仅当G不属于G～k—3∪Gk—2k—3；且k—7时，G不同构于G417.将阶至少为2k，(k—3)—正则连通(k≥5)，包含割点b使得删掉顶点b后每个分支的阶为k-1或k—2的图类记为G～k—3.将阶为3k—3或3k—4的(k—3)—正则连通(k≥5)，由在三角形的每个顶点上各粘合一个阶≤k—2的连通图得到的图类记为Gk—2k—3.将阶为17的4—正则连通，包含一条边e和三个5阶连通图G1，G2，G3(Gi为5阶完全图去掉关联同一点的两条边得到，i=1，2，3)，且e的每个端点均与G1，G2，G3的2度点恰通过一条边相连得到的图记为G417.2.设G是阶至少为2k的(k—4)—正则连通图(k≥6)，则G的k—限制边连通度λk(G)存在当且仅当G不属于Gok—4∪Gk—2k—4且k=8时， G不同构于G417.将阶至少为2k，(k—4)—正则连通(k≥6)，包含割点b使得删掉顶点b后每个分支的阶为k-1，k—2或k—3的图类记为Gok—4.将阶为3k—3，3k—4，3k—5或3k—6的(k—4)—正则连通(k≥4)，由三角形的每个顶点上各粘合一个阶≤k—2的连通图得到的图类记为Gk—2k—4。 第四章，研究了图是k—限制边连通度最优的充分条件，得到下面的结果：1.设G是一个n(≥2k)阶连通图，假设对G中任意一对不相邻的顶点x和y，都有d(x)+d(y)≥n+2k—4，若G不是G*k图，则G是λk—最优的．其中，图G*k是这样的n(≥2k)阶连通图，它的顶点集可剖分成两部分V1，V2，使得|V1|，|V2|≥k且若存在xi∈Vi，使得d(xi)=|Vi|+k—2且xi是[V1，V2]的k-1饱和点(即xi与[V1，V2]的k-1条边关联)，i=1，2，则x1，x2不相邻。2.设G是n阶λ3—连通无三角图，度序列为d1≥d2≥…≥dn=δ．若则G是λ3—最优的。3.设p≥3是一个整数，G是n阶λ3—连通图且ω(G)≤p，度序列d1≥d2≥…≥dn=δ．若则G是λ3—最优的。