定向图弧连通度的下界

有向图的弧连通度是网络可靠性的一个重要参数。设D是一个有向图，最小度为δ！D"，弧连通度为λ！D"，则λ！D"≤δ！D"。当λ！D"＜δ！D"时，称有向图D是非极大弧连通的。     

非极大弧连通有向图弧连通度的下界

设D是一个有向图,δ(D)是最小度,弧连通度为λ(D),则λ(D)≤δ(D)。当λ(D)δ(D)时,称有向图D是非极大弧连通的。本文给出了非极大弧连通图的弧连通度的下界。     

限制弧连通有向图的充分条件

互联网络常以有向图或无向图作为模型,有向图的限制弧连通性能精确度量网络的容错性和可靠性.称有向图D的一个弧子集S是D的限制弧割,如果D-S中存在一个非平凡的强连通分支D1使得D-V(D1)包含至少一条弧.若强连通的有向图D存在限制弧割,则称D是λ′-连通的.λ′-连通图D的最小限制弧割所含的弧数称为D的限制弧连通度,记λ′(D).设D的围长为g,任取长度为g的有向圈Cg=u1u2…ugu1,令ξ(Cg)=min{(sum from i=1 to g)d+(ui)-g,(sum from i=1 to g)d-(ui)-g}且ξ(D)=min{ξ(Cg)}.本文给出了强连通有向图D是λ′(D)≤ξ(D)的一个充分条件.     

有向笛卡尔积图的k-限制弧连通度

笛卡尔积图是大型互联网络最重要的数学模型之一.有向图的k-限制弧连通度是弧连通度和限制弧连通度的推广,可用于度量网络的可靠性.强连通有向图D的弧子集S被称为D的一个k-限制弧割,若D-S有一个顶点数至少为k的强连通分支D_1,使得D-V(D_1)包含一个顶点数至少为k的连通子图.若这样的一个弧割存在,则称D是λ~k-连通的.D中最小k-限制弧割所含的弧数称为D的k-限制弧连通度,记做λ~k(D).在有向笛卡尔积图中,推广2-限制弧连通度的结论到k-限制弧连通度,得到有向笛卡尔积图的k-限制弧连通度的上界和3-限制弧连通度的下界,并用例子说明所得界是紧的.     

限制边连通度的四个推广之间的关系

无向图的限制边连通度是度量网络可靠性的一个重要指标.为将该概念推广到有向图,人们提出限制弧连通度、强限制弧连通度以及圈弧连通度这三个概念.通过给出限制边连通度在有向图的又一推广—条件弧连通度,并讨论这四个推广之间的关系.     

关于弧式连通函数的一个准则

给出了弧式连通函数的一个准则,即定义在弧式连通集上的一个函数是弧式连通函数当且仅当在同一弧式连通集上,此函数是Q-连通的且中间弧式连通的.     

关于有向图的强弧连通度

在图论中,图的连通性研究是一个较重要的方面,因为图的许多性质都与图的连通性有着密切的联系.李慰萱在其所著的《图论》一书中介绍了有向图的各种连通度,并且给出了有关强弧连通度λ_3与最小出入度δ_3的两个结论1.对任何有向图D,K_3≤λ_3≤δ_3.2.若D是一个强有向图,δ_3≥[p/2],则λ_3=δ_3.我们推广了上述第2个结论,得到了下面的结果:定理 若D是一个有P个顶点的有向图,记d_3(v)=min{odv,idv},如果存在整数k(1≤k≤4),使对D中任意k个顶点v_1,…,v_k都有d_3(v_1)+…+d_3(v_k)≥k/2(p-2)+1/2则λ_3=δ_3.     

λ'最优定向图的最小度条件

图的限制弧连通度是度量网络可靠性的一个重要指标.称强连通有向图D的弧割S是一个限制弧割,若D-S包含一个非平凡的强连通分支D'使得D-V(D')包含至少一条弧.限制弧连通度λ'(D)是指最小限制弧割的弧数.λ'最优有向图是使限制弧连通度尽可能大的一类有向图.定向图是一类重要的有向图.定向图和多部定向图是λ'最优的一些最小度条件将被给出.这些结果推广了Grüter等关于竞赛图的相关结论.     

广义弧连通K-凸映射

在序拓扑向量空间中引入较锥凸映射更一般的若干弧连通锥凸映射概念,讨论它们之间的相互关系,给出连续映射成为弧连通锥弱凸映射的条件,得到弧连通锥凸映射的值域与锥水平集分别是锥凸集与弧连通集,证明了锥半连续的弧连通严格凸映射是弧连通锥凸映射.     

圆有向图中的泛弧

设D=(V,A)是一个有向图,uv是D上的一条弧。如果对于任意顶点w∈V(D),都有弧uv和顶点w包含在某个公共圈中,则称弧uv是D的一条泛弧。证明了圆有向图R的每条弧都是泛弧当且仅当R是一个圈或者R是2-强连通的且R不属于一类特殊的圆有向图。并由此给出了判断圆有向图的每条弧是否都是泛弧的多项式算法。