雙連通網(wǎng)絡(也稱BC圖)、k-元 n-方體、星圖是目前被廣泛應用于計算機系統(tǒng)互連網(wǎng)絡的正則圖。圖的連通度和診斷度是表征互連網(wǎng)絡可靠性的重要參數(shù)。g-額外連通度、g-額外診斷度、g-好鄰連通度、g-好鄰診斷度是兩類帶有約束條件連通度和診斷度,因其能更精確地度量互連網(wǎng)絡可靠性而得到了廣泛的關注。本文研究了 BC圖、k-元n-方體和以星圖為單元的分層星圖的g-額外連通度、g-額外診斷度、g-好鄰連通度和g-好鄰診斷度。該研究可以為以這些圖作為互連網(wǎng)絡拓撲的計算機系統(tǒng)的可靠性分析和故障診斷算法的設計提供理論依據(jù)。對于BC圖,我們研究了 BC圖以及與之密切相關的圖——折疊超立方體在PMC模型和MM*模型下的g-額外診斷度。圖G的g-額外診斷度是指G中每個沒有故障點的分支至少包含(g+1)個頂點的情況下,G可以自我診斷的故障點的最大數(shù)。論文利用BC圖中(g+1)階子圖的性質,證明了 BC圖g-額外診斷度的一個下界及其g-額外診斷度等于該下界的充分條件。進而,對于一般的整數(shù)g,我們得到了n-維超立方體和變形超立方體的g-額外診斷度;對于較小的整數(shù)g(1≤g≤3),我們得到了BC圖的g-額外診斷度。最...

【文章頁數(shù)】：113 頁

【學位級別】：博士

【文章目錄】：
摘要
ABSTRACT
主要符號表
第一章 緒論
    1.1 研究的背景和意義
    1.2 研究現(xiàn)狀
    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-好鄰診斷度
總結和展望
參考文獻
攻讀博士學位期間的主要研究成果
致謝
個人情況及聯(lián)系方式



本文編號：3924250