图的k-限制边连通度的最优性和超级性的充分条件

摘要

在当今经济和科技蓬勃发展的信息时代，互联网络在人们的工作、日常生活等方面凸显越来越重要的地位．对于网络的各项研究倍受人们的关注，其中对于网络的可靠性和容错性研究已经成为近年来国内外研究的热点之一．众所周知，边连通度是反映图的连通性质的一个重要参数．而要精确地刻画图的连通性质，经典边连通度存在着不足之处：首先，边连通度相同的图可靠度可能不同；其次，不能区分删掉κ个割断点或λ条割断边得到的图的不同类型，即未考虑删掉点割或边割对网络的破坏程度；第三，默认图的任何子集中所有元素可能潜在地同时失效．为克服以上缺陷，自然要将经典边连通度加以推广．自1983年F．Harary[1]提出条件边连通度的概念以来，经过二十多年的发展，条件边连通度所涉及的内容日益丰富和具体，包括超级边连通度、过边连通度、限制边连通度等．
　　对于大规模网络的可靠性和容错性的分析通常引入各种图论模型，利用图的点和边来代替网络的节点和连线，以此构成相互连通的网络的基础拓扑．针对不同的模型，都有诸多相关理论问题需要研究。其中一个重要模型是这样的图[2]G=(V，E)：假设其节点不会失效，每一条边是独立失效的，失效概率为p∈(0，1)．若G的边数是ε，用Ci表示边数为i的边割的数目，则G不连通的概率为：其中λ(G)是G的边连通度．易知网络保持连通的概率为1-P(G，p)．显然，P(G，p)的值越小，网络的可靠性就越好．因此，若要确定网络的可靠性，则需要确定所有的系数Gi．但是J．S．Provan和M．O．Ball[3]指出：对于一般图G，确定Gi是NP-困难的．
　　为了更加精确地估计网络的可靠性，A．H．Esfahanian和S．L．Hakimi[4]提出了图的限制边连通度的概念．J．Fabrega和M．A．Foil[5]将限制边连通度的概念进一步推广，提出了κ-限制边割和κ-限制边连通度的概念．更进一步，李乔良和李乔[6]提出了超级限制边连通度的概念．目前，对于这一领域已有了广泛而深入的研究。本文在前人工作的基础上，继续研究限制边连通度的若干性质．

目录

封面

声明

目录

中文摘要

英文摘要

第一章 预备知识

第二章 一般图的 λ4-最优性

第三章 无三角形图的 λk-最优性和超级性

第四章 二部图的 λk-最优性

参考文献

攻读学位期间发表的学术论文

致谢