發(fā)布時(shí)間：2017-12-09 03:00

  本文關(guān)鍵詞：網(wǎng)絡(luò)的連通性和診斷

  更多相關(guān)文章： 互連網(wǎng)絡(luò) 圖 容錯(cuò) 連通度 診斷

【摘要】：用圖來表示互連網(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í)際意義.診斷度是測(cè)量網(wǎng)絡(luò)容錯(cuò)性的重要參數(shù).本文主要研究圖的外連通度,網(wǎng)絡(luò)的容錯(cuò)哈密爾頓性以及故障診斷.本文的結(jié)構(gòu)如下:第一章是引言部分,主要介紹圖的條件連通度,網(wǎng)絡(luò)容錯(cuò)哈密爾頓性以及故障診斷的研究背景.第二章,給出了本文所用到的圖論的基本概念.第三章,研究了k-元立方體Qnk的外連通度.當(dāng)n ≥ 3時(shí),證明了 3-元n-立方體Qn3的3-外連通度是8n-12,其結(jié)果大概是傳統(tǒng)連通度的4倍.當(dāng)n ≥ 3和k≥4時(shí),證明了k-元n立方體Qnk的3-外連通度是8n-9,此結(jié)果與k的取值無關(guān).這一結(jié)論擴(kuò)展了 Zhao等人關(guān)于Qn3的2-外連通度以及Hsieh等人關(guān)于Qnk的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| ≤ 2n-2且|Fv|≤n-1,則BHn中存在一個(gè)無故障的長(zhǎng)度為22n-2|Fv|的圈.其次證明了平衡超立方體在故障邊數(shù)目不超過n-1的情況下具有強(qiáng)哈密爾頓交織性.設(shè)x和y是BHn中同一部中的任意兩點(diǎn).令Fe是一些故障邊的集合.如果|Fe|≤n-1且n≥1,那么在BHn中存在一條無故障的長(zhǎng)度為22n-2的從x到y(tǒng)路.也就是說,BHn是(n-1)-邊容錯(cuò)強(qiáng)哈密爾頓交織的.第五章,主要研究網(wǎng)絡(luò)的診斷,包括悲觀診斷,條件診斷以及g-好鄰診斷.第一節(jié)研究了 PMC模型下的悲觀診斷.首先得到了 k-正則k-連通圖類Gn在滿足某些條件下的悲觀診斷.作為應(yīng)用,我們導(dǎo)出了交錯(cuò)群圖AGn,交錯(cuò)群網(wǎng)絡(luò)ANn,k-元n-立方體網(wǎng)絡(luò)Qnk,星圖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,平衡超立方體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,在PMC模型和MM模型下的條件診斷分別是n + 4k-3 ≥ 2,n≥4)和n + 3k-3(k ≥ 2,n≥2).第三節(jié)研究g-好鄰診斷.令tc(G)和tg(G)分別表示圖G的條件診斷度和g-好鄰診斷度.對(duì)于大多數(shù)的網(wǎng)絡(luò),1-好鄰診斷度與條件診斷度并不相等.本節(jié)主要考慮平衡超立方體BHn,得到了 BHn的1,2-好鄰診斷度.并證明了其1-好鄰診斷度與條件診斷度相等.第六章,總結(jié)全文并提出一些待研究的問題.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5
，

本文編號(hào)：1268790