论文部分内容阅读
在当今经济和科技蓬勃发展的信息时代，互联网在人们的工作、日常生活等方面凸显越来越重要的地位．研究网络的可靠性和容错性成为近年来国内外研究的热点课题之一．众所周知，图的边连通度是反映图的连通性质的一个重要参数．然而为了更精确地刻画图的连通性质，需要将经典边连通度的概念继续加以推广．1983年F．Harary[1]提出条件边连通度的概念，经过二十年来的发展，各类条件边连通度问题被相继提出，发展和应用．图的限制边连通度问题在大型网络的设计和分析中非常重要，在实际问题中也应用广泛，是图论研究中非常活跃的研究课题． 在设计和分析大规模网络的可靠性和容错性时，通常考虑某些类型的度量准则和图模型．对于不同的度量准则和模型，相应地需要研究许多不同的相关理论问题．图的不连通性可以作为图网络可靠性的度量准则，此时其中一个重要模型是这样的图G=(V,E)：假设其节点不会失效，但节点间的连线，也就是边相互独立地以等概率p∈(0，1)失效．令e是G的边数，Ch表示边数为h的边割的数目，则G不连通的概率可以表示为：P(G，p)=e∑ h=1 Chph(1-p)e-h． 因此图G的可靠度为1-P(G，p)．显然P(G，p)越小，网络的可靠性就越好．自然，为了确定P(G，p)的值就需要确定所有系数Ch．但是J．Provan和M．Ball[2]指出，对一般图G，确定所有系数Ch，从而计算P(G，p)的值是NP-困难的．为此，A．H．Esfahanian和S．L．Hakimi[3]在研究大规模网络的可靠性和容错性时提出了图的限制边连通度的概念，这一概念能反映图的经典边连通度所不能反映的更深刻的图的边连通性质．J．Fabrega和M．A．Fiol[4]将限制边连通度的概念进一步推广，提出了k-限制边割和k-限制边连通度的概念．本文将在前人工作的基础上，继续研究k-限制边连通度的相关性质．