论文部分内容阅读
目前，互联网络已经与人们的工作，日常生活等方面息息相关．网络的可靠性和容错性是近年来国内外研究的热点问题．我们知道，边连通度是反映图的连通性质的一个重要参数．而要精确地刻画图的连通性质，经典边连通度存在着不足之处：首先，边连通度相同的图可靠度可能不同．其次，不能区分删掉k个割断点或λ条割断边得到的图的不同类型，即未考虑对网络的伤害程度．第三，默认图的任何子集中所有元素能潜在地同时失效．为克服以上缺陷，自然要将经典边连通度的概念加以推广．自1983年Harary[2]提出条件连通度的概念以来，经过约二十年的发展，条件连通度所涉及的内容日益丰富和具体，包括超级连通度、过边连通度、限制边连通度等。
设计和分析大规模网络的可靠性和容错性时，通常包括某些类型的图模型．针对不同的模型，都有诸多相关理论问题需要研究．其中一个重要模型是这样的网络G：假设其节点不会失效，但节点间的连线可能相互独立地以等概率p失效．则G不连通的概率为：p(G．p)=e∑h=1Chph(1-p)e-h.其中e为G的边数，Ch表示基数为^的边割的数目，则图G的可靠度为1-P(G, p)．确定P(G:p)的大小问题在可靠度的研究中受到了广泛关注．但Provan和Ball[3]已经证明，对一般图G．P(G，p)的计算是NP-hard的．为此，Esfahanian和Hakimi[5]提出了限制边连通度的概念．本文在前人工作的基础上，继续研究限制边连通度的相关性质。
在第一章中，我们主要介绍了本文的研究背景和已有的一些结果，以及文章中所涉及的一些概念和术语符号。
在第二章中，我们具体讨论了正则图、2-连通图的k-限制边连通度(k≤6)的存在性和上界问题。
在第三章中，我们研究了(k-2)-正则图k-限制边连通度的存在性。
在第四章中，我们研究了限制边连通度的最优性。