广义de Bruijn有向图和Kautz有向图的限制性弧连通度

有向图的限制性弧连接度是测量互连网络容错性的重要参数.本文证明了对于直径k≥4和参数d≥4的广义de Bruijn有向图BG(n, d),它的限制性弧连通度是2d-2.对于直径k≥4和参数d≥4或者d≥3, k≥5, n和d的最大公约数g.c.d(n,d)≥2和n可以被d+1整除的广义Kautz有向图KG(n, d),它的限制性弧连通度为2d-2.作为结论, BG(n, d)和KG(n, d)的超限制性弧连通性可以直接得出.本文还证明了对于任意的强连通有向图D有λh(D)≤min{ξh(D),|V1|λ(D2),|V2|λ(D1)}.另外,对于直径k≥4,证明这两类有向图分别跟自己做笛卡尔积得到的有向图的限制性弧连通度分别是d≥3,λ2(BG(n, d)×BG(n, d))=4d-2;d≥2,λ2(KG(n, d)×KG(n, d))=4d-2.

有向Kautz图的超级限制弧连通性

限制边连通度是比传统的边连通度更精确的网络可靠性指标.限制边连通度在有向图中有4个推广,分别对应有向图的4种限制弧连通度.有向Kautz图可以作为多处理机系统的基础拓扑,是一类重要网络.证明了有向Kautz图K(d,n)的4种限制弧连通度都为2d-2,并且确定了对应的最小限制弧割的结构特征.

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

互联网络常以有向图或无向图作为模型,有向图的限制弧连通性能精确度量网络的容错性和可靠性.称有向图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)的一个充分条件.

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

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

超级λ′定向图的最小度条件

图的限制弧连通度是度量网络可靠性的一个重要指标.设D是一个强连通有向图,其弧割S是一个限制弧割,若D-S包含一个非平凡的强连通分支D′,使得D-V(D′)包含至少一条弧.限制弧连通度λ′(D)是指最小限制弧割的弧数.一个强连通有向图是超级λ′的,若它的限制弧连通度是极大的且最小限制弧割的数目是极小的.定向图和二部定向图是超级λ′的最小度条件被给出,并用例子说明所给的条件是紧的.