網絡的連通性和診斷.pdf

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

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

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

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

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

6、體BHn，泡沫排序星圖BSn，增廣k-元n-立方體AQn,k以及數(shù)據(jù)中心網絡Dk，n等.
　　第二節(jié)研究數(shù)據(jù)中心網絡Dk,n的條件診斷.通過分析Dk,n在至多刪去n+4k-5個點后所得連通分支的情況，得到了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-好鄰診斷度.對于大多數(shù)的網