一些正则图的条件连通度和限制诊断度

发布时间：2024-03-10 04:33

　　双连通网络(也称BC图)、k-元 n-方体、星图是目前被广泛应用于计算机系统互连网络的正则图。图的连通度和诊断度是表征互连网络可靠性的重要参数。g-额外连通度、g-额外诊断度、g-好邻连通度、g-好邻诊断度是两类带有约束条件连通度和诊断度,因其能更精确地度量互连网络可靠性而得到了广泛的关注。本文研究了 BC图、k-元n-方体和以星图为单元的分层星图的g-额外连通度、g-额外诊断度、g-好邻连通度和g-好邻诊断度。该研究可以为以这些图作为互连网络拓扑的计算机系统的可靠性分析和故障诊断算法的设计提供理论依据。对于BC图,我们研究了 BC图以及与之密切相关的图——折叠超立方体在PMC模型和MM*模型下的g-额外诊断度。图G的g-额外诊断度是指G中每个没有故障点的分支至少包含(g+1)个顶点的情况下,G可以自我诊断的故障点的最大数。论文利用BC图中(g+1)阶子图的性质,证明了 BC图g-额外诊断度的一个下界及其g-额外诊断度等于该下界的充分条件。进而,对于一般的整数g,我们得到了n-维超立方体和变形超立方体的g-额外诊断度;对于较小的整数g(1≤g≤3),我们得到了BC图的g-额外诊断度。最...

【文章页数】：113 页

【学位级别】：博士

【文章目录】：
摘要
ABSTRACT
主要符号表
第一章 绪论
    1.1 研究的背景和意义
    1.2 研究现状
    1.3 主要工作及写作安排
    1.4 图论的术语和记号
    1.5 条件连通度和限制诊断度的预备知识
第二章 BC图的g-额外诊断度
    2.1 预备知识
    2.2 BC图的g-额外诊断度的下界
    2.3 两类BC图的g-额外诊断度
    2.4 当g≤3时,BC图的g-额外诊断度
    2.5 折叠超立方体的g-额外诊断度
第三章 k-元 n-方体的g-额外连通度和诊断度
    3.1 预备知识
    3.2 k-元n-方体的g-额外连通度
    3.3 k(≥4)-元n-方体的g-额外诊断度
    3.4 3-元n-方体的g-额外诊断度
第四章 分层星图的g-好邻连通度和诊断度
    4.1 预备知识
    4.2 分层星图的g-好邻连通度
    4.3 PMC模型下分层星图的g-好邻诊断度
    4.4 MM^*模型下分层星图的g-好邻诊断度
总结和展望
参考文献
攻读博士学位期间的主要研究成果
致谢
个人情况及联系方式



本文编号：3924250