类超立方体关于极大局部连通性的容错度

发布时间：2021-10-07 14:11

　　当一个多处理器系统的网络用图来建模时,该网络的可靠性可以通过图的连通性来衡量.图的局部连通度是比连通度更准确的指标.众所周知,图的局部连通度越大,对应的网络就越可靠.极大局部连通图是使局部连通度达到最大的一类图.在多处理器系统的运行过程中,处理器出现故障是难以避免的,因此必须考虑系统的容错性.容错度是度量系统容错性的参数.人们将容错度与极大局部连通性结合,提出了一个图关于极大局部连通性的容错度的概念.实际应用中系统的故障分布将遵循一定的规律,基于此,我们将关于极大局部连通性的容错度这个概念推广,提出了关于极大局部连通性的g-好邻容错度的概念.在一些应用中,有向网络比无向网络具有更多的优势,因此研究有向网络的性质是有意义的.在本文我们也将关于极大局部连通性的容错度推广到有向图,提出了有向图关于极大局部连通性的容错度的概念.超立方体网络凭借其良好的拓扑性质以及简洁的实现方式而成为最为流行的网络之一.为了改进和推广超立方体,一些类超立方体网络被提出,如kk元n方体和单向k元n方体.本文分四章研究了超立方体、kk元n方体和单向k元n方体关于极大局部连通性的容错度.第一章主要介绍了一些图论方面的... 

【文章来源】：山西大学山西省

【文章页数】：52 页

【学位级别】：硕士

【部分图文】：

图１．超立方体ｑ３??

ｕ?＝?ａｎ－ｉａｒｔ－２…邮与Ｖ?＝?ｋ－ｉ６ｎ－２…知相邻当且仅当存在整数ｄ，使得ａｄ?＝?Ｗ士ｌ（ｍｏｄ??ｆｃ）且对任意的ｉ?＃?ｄ都有ａ；二ｂｉ？此时，称边ｍ；为一＇条ｄ维边．??图２给出了?５元２方体Ｑｉ．??００?１０?２０?３０?４０??才３４?＾＾４ｙ??图２．?５元２方体防．??二、有向网络??由于ｆｃ元ｎ方体具有对称性、正则性和哈密尔顿性等优良的性质而成为一些多??处理机系统的拓扑结构．在实际应用中，网络中的一对处理器间的直接通信联系往往??由两个方向相反的通信信道实现的，基于此观察，可将网络中的一条边看成两条端点??相同方向相反的弧，由此一个无向网络可看成一个有向网络．为了减低构造网络的费??用和复杂性，单向网络的概念被提出１３，４１．特别地，张国珍问在２０１５年提出了单向Ａ：??元ｎ方体这一概念．??定义１．１．３．（问）对给定整数ｎ＞ｌ和ｆｃ＞３．单向／ｃ元ｎ方体￥的顶点集为??｛ａｒｅ—ｉａｒａ＿２?…ａ〇?：叫?６?｛０，１，…，Ａ；?—?ｌ｝，ｉ?＝?０，１，…，ｎ?＿?１｝?？顶点?ｗ?＝?ａｒａ＿ｉａ？＿２?…ａ〇?控制??顶点ｗ?＝?ｂｎ＿ｉｂｎ—２?？．．知当且仅当存在整数ｄ?＃牐?枺?牐保?浚??

§１．２极大局部连通性??无向图的极大局部连通性??和选择网络时的一个基本考量是网络的可靠性，它通Ｇ中任意两个不同的顶点Ｕ和Ｖ之间都存在路，则１．２．１．（网）连通图Ｇ中的一个点子集Ｓ是一个点最小点割的基数称为Ｇ的连通度，记为ｋ（Ｇ）．??是连通度“割”版本的定义，下面给出连通度“路”版本明这两个定义是等价的．??１．２．２．?（［６］）设ｕ和？；是连通图Ｇ中不同的两点，用ｘ－ｗ路的最大数目．定义Ｇ的连通度为ｋ（Ｇ）?＝?ｍｉｎ｛ＫＣ１．２．１．（叩设ｕ和是图Ｇ中不相邻的两点．则Ｇ

【参考文献】：
期刊论文
[1]在PMC模型下单向k元n立方体的诊断度[J]. 张雯丽,林上为,李艺海,郭慧铃.  计算机工程与应用. 2019(04)
[2]单向k-元n-立方体网络[J]. 张国珍.  计算机工程与应用. 2015(20)
[3]On Restricted Connectivity and Extra Connectivity of Hypercubes and Folded Hypercubes[J]. 徐俊明,朱强,侯新民,周涛.  Journal of Shanghai Jiaotong University. 2005(02)
[4]无向de-Bruijn图的超级边连通性和限制性边连通度[J]. 吕长虹,张克民.  应用数学学报. 2002(01)



本文编号：3422200