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

论文摘要

当一个多处理器系统的网络用图来建模时,该网络的可靠性可以通过图的连通性来衡量.图的局部连通度是比连通度更准确的指标.众所周知,图的局部连通度越大,对应的网络就越可靠.极大局部连通图是使局部连通度达到最大的一类图.在多处理器系统的运行过程中,处理器出现故障是难以避免的,因此必须考虑系统的容错性.容错度是度量系统容错性的参数.人们将容错度与极大局部连通性结合,提出了一个图关于极大局部连通性的容错度的概念.实际应用中系统的故障分布将遵循一定的规律,基于此,我们将关于极大局部连通性的容错度这个概念推广,提出了关于极大局部连通性的g-好邻容错度的概念.在一些应用中,有向网络比无向网络具有更多的优势,因此研究有向网络的性质是有意义的.在本文我们也将关于极大局部连通性的容错度推广到有向图,提出了有向图关于极大局部连通性的容错度的概念.超立方体网络凭借其良好的拓扑性质以及简洁的实现方式而成为最为流行的网络之一.为了改进和推广超立方体,一些类超立方体网络被提出,如kk元n方体和单向k元n方体.本文分四章研究了超立方体、kk元n方体和单向k元n方体关于极大局部连通性的容错度.第一章主要介绍了一些图论方面的术语和记号以及本文的研究背景和文中涉及到的主要概念.第二章首先研究了 k元n方体网络的一些性质,并证明了 元n方体是极大局部连通图,然后确定了k元n方体关于极大局部连通性的容错度τ（Qnk）=2n-2.第三章首先研究了单向k元n方体Qnk的拓扑性质,证明了当Qnk去掉至多2n-2个顶点后仍然有一个大的强连通分支.在该结果的基础上,我们进一步证明了单向k元n方体Qnk关于极大局部连通性的容错度τ（Qnk）=n-1.第四章研究了超立方体Qn关于极大局部连通性的g-好邻容错度τg（Qn）的上下界.具体为:对n ≥ 4和1≤g≤n-2,τg（Qn）≥（g+1）n-（g+1）（g+2）/2+1-n;对n≥3和1≤g≤[n/2],τg（Qn）≤（2g-g）（n-g）-1.最后确定了Qn关于极大局部连通性的1,2,3-好邻容错度分别是τ1（Qn）=n-2,τ2（Qn）=2n-5和τ3（Qn）=5n-16.

论文目录

文章来源

类型: 硕士论文

作者: 景小飞

导师: 林上为

关键词: 网络,有向图,超立方体,元方体,极大局部连通性,容错性

来源: 山西大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机硬件技术

单位: 山西大学

分类号: O157.5;TP332

DOI: 10.27284/d.cnki.gsxiu.2019.001486

总页数: 52

文件大小: 2155K

下载量: 18

相关论文文献

• [1].最优对称拉丁超立方体的构造[J]. 系统科学与数学 2020(02)
• [2].投影均匀分片拉丁超立方体设计[J]. 系统科学与数学 2020(02)
• [3].平衡超立方体的控制数[J]. 软件 2020(09)
• [4].交换超立方体结构性质的一些注记[J]. 南阳理工学院学报 2018(02)
• [5].块转换网络和分级超立方体网络的化学指标计算[J]. 苏州科技大学学报(自然科学版) 2017(03)
• [6].折叠超立方体网络的自适应诊断[J]. 河南工程学院学报(自然科学版) 2014(04)
• [7].故障加强超立方体中的边泛圈[J]. 数学杂志 2020(06)
• [8].带有丢失弧的双向超立方体网络的诊断度[J]. 河南科学 2018(11)
• [9].不完全类超立方体网络的可诊断性[J]. 小型微型计算机系统 2017(05)
• [10].故障加强超立方体中的路和圈（英文）[J]. 数学杂志 2015(04)
• [11].变形超立方体的圈和路嵌入(英文)[J]. 中国科学技术大学学报 2014(09)
• [12].扭立方体网络到交换超立方体网络嵌入问题研究[J]. 广西科技大学学报 2014(03)
• [13].故障折叠超立方体中的路和圈(英文)[J]. 数学杂志 2013(03)
• [14].交换超立方体网络的网络嵌入研究[J]. 计算机工程与科学 2011(08)
• [15].交叉立方体中的交叉5长圈[J]. 天中学刊 2010(02)
• [16].超立方体图的直径[J]. 中国科技信息 2009(20)
• [17].超立方体网络连通性的概率分析[J]. 电脑知识与技术 2008(S2)
• [18].平衡超立方体的故障容错性[J]. 网络与信息安全学报 2017(09)
• [19].含故障点的加强超立方体中路和圈的嵌入（英文）[J]. 数学杂志 2016(01)
• [20].局部不连通广义超立方体中的容错路由[J]. 数字技术与应用 2014(08)
• [21].n维超立方体的补图的谱(英文)[J]. 湛江师范学院学报 2010(03)
• [22].容错超立方体网络的圈嵌入(英文)[J]. 中国科学技术大学学报 2008(09)
• [23].评估交换超立方体网络可靠性的一种新方法[J]. 电子与信息学报 2015(03)
• [24].变形超立方体网络的可靠性分析(英文)[J]. 中国科学技术大学学报 2009(12)
• [25].有关加强超立方体泛连通性的证明[J]. 学园 2014(13)
• [26].具有不连通子立方体的超立方体中多播路由[J]. 数字技术与应用 2011(10)
• [27].超立方体网络下的自适应容错路由研究[J]. 计算机应用研究 2010(03)
• [28].容错变形超立方体的圈和路（英文）[J]. 中国科学技术大学学报 2015(06)
• [29].有关加强超立方体泛连通性的证明[J]. 数学学习与研究 2014(15)
• [30].基于拉丁超立方体抽样和免疫机制的改进遗传算法[J]. 计算机应用 2011(04)

标签：网络论文;  有向图论文;  超立方体论文;  元方体论文;  极大局部连通性论文;  容错性论文;