有向图的条件弧连通度

来源 :山西大学 | 被引量 : 0次 | 上传用户:welson926
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在设计大型网络时,人们要考虑的一个基本问题是网络的可靠性(容错性),它可由图的边连通度来度量.为更精确地度量,人们推广边连通度,提出限制边连通度的概念.限制边连通度一经提出就得到了很多的关注作为限制边连通度在有向图中的推广,圈弧连通度λ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图关于超级弧连通性的弧容错度.
其他文献
研究vonNeumann正则环成为强正则环的条件是代数环论研究的一个重要组成部分,由此产生了许多重要的环类,如约化环、reversible环、semicommutative环和Abel环等.本论文介绍了新
在优化设计、优化控制和反问题应用中,人们常采用模型降阶方法来构造低自由度下大规模动力系统的降阶模型,从而满足在保证一定物理精度的同时提高计算效率的要求.特征正交分解
生产计划是企业生产管理中的决策性问题,如何制定合适的生产计划使企业获得最满意的效果是企业管理者最主要的任务之一.由于市场的动态性和复杂性,在制定生产计划的过程中存在许多不确定因素,在传统的生产计划问题中这些不确定因素理解为随机变量,由于随机问题需要大量统计数据为研究前提,许多学者用模糊变量来刻画不确定因素,将模糊规划引进到生产计划问题中,但是现实生活中许多主观不确定现象用模糊理论无法给出合理的解释
传染病是危害人类健康的因素之一,研究其传播机理进而控制其传播具有重大意义.本文在复杂网络上考虑具有出生与死亡的SIS模型,具有重要的理论及实际意义.第一章,介绍传染病研
迭代函数系统起源于动力系统理论,是研究多个映射的迭代。迭代函数系统的研究最早开始于J.Hutchinson的文章[21]。J.Hutchinson构造了Rn中的有限个相似的压缩映射族来研究分形
群论研究的一个主要任务是研究各种群的性质和结构,而通过子群的广义正规性研究有限群的结构是近年来非常活跃的课题之一.   本学位论文中,我们主要利用准素子群的几乎M-可
本文主要从动力系统的角度来研究马尔可夫过程的遍历理论。   第一章在介绍了动力系统和马尔可夫过程的基本概念与知识之后,引入了平移算子,它将具有不变测度的马尔可夫过程