有向网络的连通度和诊断度

论文摘要

多处理器系统的网络对系统性能有重要的影响.超立方体是最著名的一类多处理器系统的网络,已被广泛应用于商业和研究领域.随着研究的深入,人们发现以超立方体为网络构建的系统有些固有的缺陷,如顶点的度和直径本身都较大.为了尽可能多的保留超立方体的优良拓扑性质,弥补超立方体固有的缺陷,k元n方体被提出.多处理器网络中的一条边常由两条方向相反的单向信道物理实现,基于这个观察,人们提出双向超立方体网络的概念.为了减少构建双向网络的费用和复杂性,单向网络被提出,例如单向超立方体、单向k元n方体等.多处理器系统中出现故障处理器是难以避免的,因此诊断出系统的故障是至关重要的.系统的诊断度是度量系统诊断故障能力的一个参数.图的连通度是网络容错性的重要指标,与诊断度密切相关.g好邻连通度和g好邻诊断度是比连通度和诊断度更精确的网络指标.关于无向图的g好邻连通度和g好邻诊断度已经有了大量的研究,但是还没有关于有向图的g好邻连通度和g好邻诊断度的相应结果.本文分四章用好邻连通度和好邻诊断度这两个参数分别对单向超立方体网络、单向k元n方体网络以及带有丢失弧的双向超立方体网络的性能进行研究.第一章介绍了本文的主要概念和研究背景.第二章首先研究了单向超方体网络的一些性质,然后确定了单向超方体网络的1好邻（1好内邻,1好外邻）连通度,具体为:当n ≥ 3时,n维单向超立方体UQn的1好内邻连通度和1好外邻连通度皆为[n/2],当n ≥ 4时,n维单向超立方体UQn的1好邻连通度是2n-4.其次,确定了 n维单向超立方体UQn在PMC模型下的诊断度t（UQn）、1好邻诊断度t1（UQn）、1好内邻诊断度t1-（UQn）和1好外邻诊断度t1+（UQn）,具体为:t（UQn）=t1+（UQn）=[n/2],t1（UQ3）=t1-（UQ3）=3,t1（UQ5）=t1-（UQ5）=11,当 n=4 或者 n ≥ 6 时,t1（UQn）=t1-（UQn）=2n-1.第三章首先研究了单向k元n方体网络的一些性质,然后证明了当k ≥ 3和n ≥ 3时,单向k元n方体网络的1好邻连通度为k1（UQnk）=k（n-1）.其次,确定了单向k元n立方体UQnk在PMC模型下的诊断度和1好邻诊断度分别是n和kn-1.超立方体是丢失0条弧的双向超立方体,单向超立方体是丢失了一半弧的双向超立方体.在本文的第四章,研究了丢失任意弧的双向超立方体D在PMC模型下的诊断度满足t（D）≤δ(D 并给出t（D）=δ（D）的充要条件.此外也证明了D在MM*模型下的诊断度t*（D）满足δ（D）≥t*（D）≥δ（D）.

论文目录

• 中文摘要
• Abstract
• 符号说明
• 第一章 绪论
•   §1.1 网络
•     §1.1.1 无向网络
•     §1.1.2 有向网络
•   §1.2 连通度和好邻连通度
•   §1.3 诊断度和好邻诊断度
•     §1.3.1 PMC模型下的诊断度
• *模型下的诊断度'>    §1.3.2 MM^*模型下的诊断度
• 第二章 单向超立方体网络的1好邻连通度和1好邻诊断度
•   §2.1 单向超立方体的一些性质
•   §2.2 单向超立方体的1好邻连通度
•   §2.3 单向超立方体的诊断度
•     §2.3.1 PMC模型下单向超立方体的1好邻诊断度
• *模型下单向超立方体的1好邻诊断度'>    §2.3.2 MM^*模型下单向超立方体的1好邻诊断度
• 第三章 单向k元n立方体网络的1好邻连通度和1好邻诊断度
•   §3.1 单向k元n立方体的一些性质
•   §3.2 单向k元n立方体的1好邻连通度
•   §3.3 PMC模型下单向k元n立方体的1好邻诊断度
• 第四章 带有丢失弧的双向超立方体网络的诊断度
•   §4.1 PMC模型下带有丢失弧的双向超立方体的诊断度
• *模型下带有丢失弧的双向超立方体的诊断度'>  §4.2 MM^*模型下带有丢失弧的双向超立方体的诊断度
• 结束语
• 参考文献
• 研究成果
• 致谢
• 个人简况及联系方式

文章来源

类型: 硕士论文

作者: 张雯丽

导师: 林上为,逯丽清

关键词: 网络,有向图,单向超立方体,单向元立方体,好邻连通度,好邻诊断度

来源: 山西大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 山西大学

分类号: O157.5

DOI: 10.27284/d.cnki.gsxiu.2019.001103

总页数: 63

文件大小: 3576K

下载量: 24