網(wǎng)絡(luò)的連通性和診斷.pdf

1、用圖來表示互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)已被計(jì)算機(jī)和工程技術(shù)人員廣泛運(yùn)用.在本文中，“圖”和“互連網(wǎng)絡(luò)”不作區(qū)分.網(wǎng)絡(luò)的可靠性通常用圖的連通度來表示.外連通度是傳統(tǒng)連通度的推廣，更能準(zhǔn)確的分析各種互連網(wǎng)絡(luò)的可靠性.哈密爾頓性是設(shè)計(jì)網(wǎng)絡(luò)時(shí)最基本的要求之一.網(wǎng)絡(luò)故障不可避免，具有故障元素的哈密爾頓路和圈嵌入問題具有實(shí)際意義.診斷度是測量網(wǎng)絡(luò)容錯(cuò)性的重要參數(shù).
　　本文主要研究圖的外連通度，網(wǎng)絡(luò)的容錯(cuò)哈密爾頓性以及故障診斷.
　　本文的結(jié)構(gòu)如下

2、:
　　第一章是引言部分，主要介紹圖的條件連通度，網(wǎng)絡(luò)容錯(cuò)哈密爾頓性以及故障診斷的研究背景.
　　第二章，給出了本文所用到的圖論的基本概念.
　　第三章，研究了k-元n-立方體Qkn的外連通度.當(dāng)n≥3時(shí)，證明了3-元n-立方體Q3n的3-外連通度是8n-12，其結(jié)果大概是傳統(tǒng)連通度的4倍.當(dāng)n≥3和k≥4時(shí)，證明了k-元n立方體Qkn的3-外連通度是8n-9，此結(jié)果與k的取值無關(guān).這一結(jié)論擴(kuò)展了Zhao等人關(guān)于Q3n

3、的2-外連通度以及Hsieh等人關(guān)于Qkn的2-外連通度的結(jié)果.
　　第四章，研究了平衡超立方體的容錯(cuò)哈密爾頓性.關(guān)于平衡超立方體的容錯(cuò)性，已知的結(jié)果大多都是只考慮故障點(diǎn)或者故障邊.我們考慮同時(shí)具有故障點(diǎn)和故障邊的容錯(cuò)性.
　　首先證明了平衡超立方體具有故障點(diǎn)和故障邊數(shù)目不超過2n-2并且故障點(diǎn)數(shù)目不超過n-1情況下的哈密爾頓圈的存在性.令Fv和Fe分別表示BHn(n≥2）中的故障點(diǎn)和故障邊的集合.如果|Fe|+|Fv|≤2

4、n-2且|Fv|≤n-1，則BHn中存在一個(gè)無故障的長度為22n-2|Fv|的圈.
　　其次證明了平衡超立方體在故障邊數(shù)目不超過n-1的情況下具有強(qiáng)哈密爾頓交織性.設(shè)x和y是BHn中同一部中的任意兩點(diǎn).令Fe是一些故障邊的集合.如果|Fe|≤n-1且n≥1，那么在BHn中存在一條無故障的長度為22n-2的從x到y(tǒng)路.也就是說，BHn是(n-1)-邊容錯(cuò)強(qiáng)哈密爾頓交織的.
　　第五章，主要研究網(wǎng)絡(luò)的診斷，包括悲觀診斷，條件診斷

5、以及g-好鄰診斷.
　　第一節(jié)研究了PMC模型下的悲觀診斷.首先得到了k-正則k-連通圖類Gn在滿足某些條件下的悲觀診斷.作為應(yīng)用，我們導(dǎo)出了交錯(cuò)群圖AGn，交錯(cuò)群網(wǎng)絡(luò)ANn，k-元n-立方體網(wǎng)絡(luò)Qkn，星圖Sn以及匹配組合網(wǎng)絡(luò)MCN的悲觀診斷.這些圖類具有共同的特點(diǎn)，相鄰兩個(gè)點(diǎn)的最大公共鄰點(diǎn)的個(gè)數(shù)小于等于2.其次，考慮了沒有公共鄰點(diǎn)個(gè)數(shù)限制的幾類網(wǎng)絡(luò)的悲觀診斷，包括（n，k)-排列圖An,k，（n，k）-星圖Sn，k，平衡超立方

6、體BHn，泡沫排序星圖BSn，增廣k-元n-立方體AQn,k以及數(shù)據(jù)中心網(wǎng)絡(luò)Dk，n等.
　　第二節(jié)研究數(shù)據(jù)中心網(wǎng)絡(luò)Dk,n的條件診斷.通過分析Dk,n在至多刪去n+4k-5個(gè)點(diǎn)后所得連通分支的情況，得到了Dk,n在PMC模型和MM模型下的條件診斷分別是n+4k-3(k≥2，n≥4)和n+3k-3(k≥2，n≥2).
　　第三節(jié)研究g-好鄰診斷.令tc(G)和tg(G)分別表示圖G的條件診斷度和g-好鄰診斷度.對(duì)于大多數(shù)的網(wǎng)