定向图的限制弧连通度

来源 :山西大学 | 被引量 : 0次 | 上传用户:liur8888
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在通信网络的研究中,人们通常以图或有向图为数学模型表示多处理器系统的互连网拓扑结构,其中顶点集和边集或弧集分别表示元件和连线的集合.此时,图的性质和参数可用来度量网络拓扑的性能.在实际应用中,很多网络的连线都是有向的,这样的网络通常以有向图为数学模型.通常用弧连通度来度量有向网络的可靠性,但是用弧连通度进行度量有一定的缺陷,因而为了更好地度量网络的可靠性,限制弧连通度的概念被提出.  设 D是一个强连通的有向图.一个弧割S是一个限制弧割,若 D-S包含一个非平凡的强分支D使得D- V( D)至少包含一条弧.限制弧连通度λ(D)是指最小限制弧割的弧数.设(( D)是 D的最小弧度,它在绝大多数情况下都是λ(D)的上界.一个强连通有向图D被称为乂最优的,若λ(D)=((D).一个强连通的有向图是超级λ的,若它的限制弧连通度是极大的且最小限制弧割的数目是极小的.  近年来,有向图是λ最优和超级λ的条件得到了广泛的关注.2013年,Griiter等人相继提出了竞赛图和二部竞赛图是A最优的最小度条件.竞赛图是定向图的一个子类.文中给出了定向图和k部定向图(k>2)是λ最优的最小度条件,并且研究了定向图和二部定向图是超级A的最小度条件以及在一些度序列条件下,定向图的限制弧连通度的一个下界.  本文共分为四章内容.  第一章首先综述了限制弧连通度的应用背景和研究现状,然后介绍了本文中将用到的一些图论基本概念和记号.  第二章研究了定向图和k部定向图(k≥2)是λ最优的最小度条件.设D是一个阶为n的定向图.得到以下结论:  (1)若最小度S(D)≥ n+1_4,则定向图D是λ最优的.  (2)当 k=2或 n是奇数时,若最小度δ(D)≥(k-1) ra+3)—4k,则 k部(k≥2)定向图D是λ最优的;  当 k≥3且 n是偶数时,若最小度δ(D)≥(k-1)(n+4)—4k,则 k部(k≥2)定向图D是λ最优的.  第三章研究了定向图和二部定向图是超级A的最小度条件.得到下述结果:  (1)若最小度δ(D)> n+2—4,则定向图D是超级λ的.  (2)若最小度δ(D)> n+4—8,则二部定向图D是超级λ的.  第四章给出了在一些度序列条件下,定向图的限制弧连通度的一个下界.
其他文献
等度连续定理是经典的泛函分析的三大基本原理之一,是这门学科的精华部分。这一学科的发展受到了数学物理方程和量子力学的推动,它把具体的分析问题抽象到更加纯粹的代数、拓扑
偏微分方程的精确能控是控制理论中的一个重要研究课题,有重要的理论意义和应用价值.本文主要研究非柱状区域上波动方程的精确能控性.本篇论文共分为三章.  第一章是绪论,主
本文主要考虑具依赖状态脉冲的积分微分系统{x=f(t,x,Tx),t≠τk(x),Δx=Ik(x),t=τk(x),x(t0+)=x0,k=1,2,3,…(I)的稳定性,其中f(t,x,Tx)=F(t,x)+R(t,x,Tx),Tx=∫t0tL(t,s,x(s))ds,L∈
我国高速铁路进入快速发展时期,确保高速动车组安全高效运行,是一项重要的研究工作.系统仿真是一种以计算机和仿真系统软件为工具,对现实系统或未来系统进行动态试验研究的理
非负矩阵理论一直是矩阵理论中最活跃的研究领域之一,在数学、自然科学的其他分支以及社会科学中都广泛涉及到,例如博弈论、Markov链(随机矩阵)、概率论、概率算法、数值分析、
本文将分为四个部分:  第一部分我们研究了具有巢寄生行为的两种群模型,两个种群都具有阶段结构,得到该系统持续生存的充分性条件,进一步证明了在适当的条件下,周期解及概周