论文部分内容阅读
在通信网络的研究中,人们通常以图或有向图为数学模型表示多处理器系统的互连网拓扑结构,其中顶点集和边集或弧集分别表示元件和连线的集合.此时,图的性质和参数可用来度量网络拓扑的性能.在实际应用中,很多网络的连线都是有向的,这样的网络通常以有向图为数学模型.通常用弧连通度来度量有向网络的可靠性,但是用弧连通度进行度量有一定的缺陷,因而为了更好地度量网络的可靠性,限制弧连通度的概念被提出. 设 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是超级λ的. 第四章给出了在一些度序列条件下,定向图的限制弧连通度的一个下界.