论文部分内容阅读
众所周知，多处理机网络的基础拓扑通常以图为数学模型，其中图中的顶点表示处理机，图中的边表示处理机间的直接通讯联系.很多网络间的通讯联系都具有方向，因此，以有向图为网络的数学模型并且用弧连通度来度量有向网络的可靠性.限制弧连通度作为比弧连通度更加精确的指标被提出.本文提出了k-限制弧连通度的概念，它是弧连通度与限制弧连通度的共同推广. 设D是强连通有向图且S是D的一个弧子集.若D-S包含一个顶点数至少为k的强连通分支D使得D-V(D)包含一个顶点数至少为k的连通子图，则称S为D的一个k-限制弧割.若是这样的一个k-限制弧割存在，那么称D是λk-连通的.一个λk-连通有向图D的k-限制弧连通度λk（D)是指D中一个最小k-限制弧割所含弧数. 为了研究k-限制弧连通度，本文提出最小k-度的概念.设D是有向图，k是一个正整数.对任意X(∈)V(D)，令Ω(X）={(a)+(X1)∪(a)-(XX1）:X1(∈)X}，ξ(X）=min{|S|:S∈Ω(X)}.定义D的最小k-度为ξk(D）=min{ξ(X）:X(∈)V(D)，|X|=k，D[X]连通}.一个有向图D是λk-最优的，若λk(D）=ξk(D). 近几年，λ2-连通有向图和λ2-最优有向图的充分条件是限制弧连通度领域的一大研究热点.本文主要研究有向图是λ3-连通和λ3-最优的最小度条件，并且给出了有向笛卡尔积图的k-限制弧连通度的上、下界. 本文共分为四章. 第一章首先介绍了本文用到的一些图理论概念和记号，然后介绍了k-限制弧连通度的研究背景. 第二章研究了有向图是λk-连通的和λk-最优的最小度条件并用例子说明这些度条件是最优的.得到以下结论: 对顶点数至少为2k的强连通有向图D，若D的最小出度δ+(D)≥2k-1或D的最小入度δ-(D)≥2k-1，那么D是λk-连通的且满足λk(D)≤ξk(D). 对顶点数至少为6的强连通有向图D， (1)若D的最小度δ(D)≥3，那么D是λ3-连通的. (2)若D的最小度δ(D)≥4.那么D是λ3-连通的且满足λ3(D)≤ξ3(D). (3)若D的最小度δ(D)≥|V(D)|+3/2，那么D是λ3-最优的. 第三章确定笛卡尔积有向图2-限制弧连通度的值以及k-限制弧连通度的上、下界，并且用例子说明这些结论是最优的.设D1和D2是两个分别以V1和V2为顶点集的强连通有向图.得到下述结果: (1)若λ(D1)≥2和λ(D2)≥2，则D=D1×D2是λ2-连通的且λ2(D)=min{ξ2(D)，|V1|λ(D2)，|V2|λ(D1)} (2)若|V1|≥k和|V2|≥k，那么D=D1×D2是λk-连通的且满足λk(D)≤min{ξk(D)，|V1|λ(D2),|V2|λ(D1)} (3)若|V1|≥3和|V2|≥3，那么D=D1×D2是λ3-连通的且满足λ3(D)≥min{|V1|λ(D2),|V2|λ(D1),3λ(D2)+λ(D1),3λ(D1)+λ(D2)}. 强限制弧连通度λs是一个与限制弧连通度密切相关的概念.第四章主要研究有向笛卡尔积图的强限制弧连通度，并且用例子说明这些结论是最优的.设D1和D2是两个分别以V1和V2为顶点集的强连通有向图.得到下述结果: (1)若它们的顶点数分别为|V1|≥2，|V2|≥2，弧连通度分别为λ(D1)，λ(D2)，那么D=D1×D2是λs-连通的且λs(D)≤min{|V1|λ(D2)，|V2|λ(D1)}. (2)若它们的顶点数分别为|V1|≥2，|V2|≥2，围长分别为g1，g2，弧连通度分别为λ(D1)，λ(D2)，则笛卡尔积有向图D=D1×D2是λs-连通的并且λs（D)≥min{|V1|λ(D2），|V2|λ(D1),λ(D1)+g1λ(D2),λ(D2)+g2λ(D1)}.