论文部分内容阅读
在设计大型网络时,人们要考虑的一个基本问题是网络的可靠性(容错性),它可由图的边连通度来度量.为更精确地度量,人们推广边连通度,提出限制边连通度的概念.限制边连通度一经提出就得到了很多的关注作为限制边连通度在有向图中的推广,圈弧连通度λc(D)、强限制弧连通度λ2(D)、限制弧连通度λ(D)分别被提出.本文提出限制边连通度的又一个推广-条件弧连通度. 设D是一个强连通有向图.D的一个弧子集S是D的一个条件弧割,若D-S不是强连通的且它的最小度δ(D-S)≥1.称D是λ(1)-连通的,若它包含一个条件弧割D的条件弧连通度,记为λ(1)(D),是D的一个最小条件弧割所含的弧数. Kautz图是有竞争力的大型网络-Kautz网络的拓扑结构本文分为四章,将给出条件弧连通度的一些性质并确定有向Kautz图的条件弧连通度. 第一章首先介绍将用到的一些图论基本概念和记号,然后给出本文的研究背景、主要概念和主要结果. 第二章首先说明条件弧连通度是限制边连通度的一个推广,讨论条件弧连通度和强限制弧连通度λ2(D),圈弧连通度λc(D),限制弧连通度λ(D)之间的关系,证明对于存在一个强限制弧割的有向图D,λ2(D)≥λ(1)(D)≥λc(D)≥λ(D),并用例子说明限制边连通度的这四个推广各不相同. Volkmann给出了有向图D的限制弧连通度λ(D)的一个上界ξ(D).第三章证明了当一个有向图D的最小度大于它的围长时有λ(1)(D)≤ξ(D),并用例子说明了这个结果是最优的.作为应用,我们确定了有向Kautz图的条件弧连通度. 超级弧连通性是与网络可靠性密切相关的一个图性质.第四章提出有向图关于超级弧连通性的弧容错度Sλ(D)的概念,用条件弧连通度给出超级弧连通性的一个特征刻画并用之研究Sλ(D)的界.作为应用,我们确定有向Kautz图关于超级弧连通性的弧容错度.