检索结果-南通市图书馆

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

有向图的k-限制弧连通度

有向图的k-限制弧连通度

作者：晋亚男山西大学

学位级别：硕士

众所周知,多处理机网络的基础拓扑通常以图为数学模型,其中图中的顶点表示处理机,图中的边表示处理机间的直接通讯联系.很多网络间的通讯联系都具有方向,因此,以有向图为网络的数学模型并且用弧连通度来度量有向网络的可靠性.限制弧连... 详细信息

众所周知,多处理机网络的基础拓扑通常以图为数学模型,其中图中的顶点表示处理机,图中的边表示处理机间的直接通讯联系.很多网络间的通讯联系都具有方向,因此,以有向图为网络的数学模型并且用弧连通度来度量有向网络的可靠性.限制弧连通度作为比弧连通度更加精确的指标被提出.本文提出了 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)={а+(X1)∪а(X\X1):X1(?)X},ζ(X) = min{|S| :S∈Ω(X}.定义D的最小k小度为ζk(为 =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)}.

关键词：网络有向图笛卡尔积弧连通度最小度

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

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

山东科学 2014年第1期27卷 98-101页

作者：王晓丽王世英晋中学院数学学院山西榆次030600 山西大学数学科学学院山西太原030006

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

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

关键词：有向图弧连通度度序列团数

在线全文

学校读者我要写书评

暂无评论

定向图弧连通度的下界

晋中学院学报 2015年第3期32卷 1-3页

作者：王晓丽张国志晋中学院数学学院山西晋中030619

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

有向图的弧连通度是网络可靠性的一个重要参数.设D是一个有向图,最小度为δλλD,弧连通度为λλDλ,则λλDλ≤δλDλ.当λλDλ弧连通的.

关键词：定向图弧连通度度序列团数

在线全文

学校读者我要写书评

暂无评论

关于有向图弧连通度的一些结果

太原师范学院学报（自然科学版） 2019年第4期18卷 12-14页

作者：王晓丽张磊晋中学院数学学院

互连网络通常以有向图为模型.弧连通度是网络可靠性的一个重要参数.设D是一个有向图,δ(D)是最小度,弧连通度为λ(D),则λ(D)≤δ(D).当λ(D)<δ(D)时,称有向图D是非极大弧连通的.本文给出了非极大弧连通图弧连通度的一些结果.

互连网络通常以有向图为模型.弧连通度是网络可靠性的一个重要参数.设D是一个有向图,δ(D)是最小度,弧连通度为λ(D),则λ(D)≤δ(D).当λ(D)弧连通的.本文给出了非极大弧连通图弧连通度的一些结果.

关键词：团数弧连通度度序列

在线全文

学校读者我要写书评

暂无评论

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

河南科学 2017年第3期35卷 345-349页

作者：晋亚男林上为山西大学数学科学学院山西太原030006

笛卡尔积图是大型互联网络最重要的数学模型之一.有向图的k-限制弧连通度是弧连通度和限制弧连通度的推广,可用于度量网络的可靠性.强连通有向图D的弧子集S被称为D的一个k-限制弧割,若D-S有一个顶点数至少为k的强连通分支D_1,使得D-V(D... 详细信息

笛卡尔积图是大型互联网络最重要的数学模型之一.有向图的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-限制弧连通度的下界,并用例子说明所得界是紧的.

关键词：网络有向图笛卡尔积弧连通度