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

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

【學(xué)位級(jí)別】：博士

【文章目錄】：
摘要
ABSTRACT
主要符號(hào)表
第一章 緒論
    1.1 研究的背景和意義
    1.2 研究現(xiàn)狀
    1.3 主要工作及寫(xiě)作安排
    1.4 圖論的術(shù)語(yǔ)和記號(hào)
    1.5 條件連通度和限制診斷度的預(yù)備知識(shí)
第二章 BC圖的g-額外診斷度
    2.1 預(yù)備知識(shí)
    2.2 BC圖的g-額外診斷度的下界
    2.3 兩類BC圖的g-額外診斷度
    2.4 當(dāng)g≤3時(shí),BC圖的g-額外診斷度
    2.5 折疊超立方體的g-額外診斷度
第三章 k-元 n-方體的g-額外連通度和診斷度
    3.1 預(yù)備知識(shí)
    3.2 k-元n-方體的g-額外連通度
    3.3 k(≥4)-元n-方體的g-額外診斷度
    3.4 3-元n-方體的g-額外診斷度
第四章 分層星圖的g-好鄰連通度和診斷度
    4.1 預(yù)備知識(shí)
    4.2 分層星圖的g-好鄰連通度
    4.3 PMC模型下分層星圖的g-好鄰診斷度
    4.4 MM^*模型下分層星圖的g-好鄰診斷度
總結(jié)和展望
參考文獻(xiàn)
攻讀博士學(xué)位期間的主要研究成果
致謝
個(gè)人情況及聯(lián)系方式



本文編號(hào)：3924250