當(dāng)一個多處理器系統(tǒng)的網(wǎng)絡(luò)用圖來建模時,該網(wǎng)絡(luò)的可靠性可以通過圖的連通性來衡量.圖的局部連通度是比連通度更準(zhǔn)確的指標(biāo).眾所周知,圖的局部連通度越大,對應(yīng)的網(wǎng)絡(luò)就越可靠.極大局部連通圖是使局部連通度達(dá)到最大的一類圖.在多處理器系統(tǒng)的運(yùn)行過程中,處理器出現(xiàn)故障是難以避免的,因此必須考慮系統(tǒng)的容錯性.容錯度是度量系統(tǒng)容錯性的參數(shù).人們將容錯度與極大局部連通性結(jié)合,提出了一個圖關(guān)于極大局部連通性的容錯度的概念.實(shí)際應(yīng)用中系統(tǒng)的故障分布將遵循一定的規(guī)律,基于此,我們將關(guān)于極大局部連通性的容錯度這個概念推廣,提出了關(guān)于極大局部連通性的g-好鄰容錯度的概念.在一些應(yīng)用中,有向網(wǎng)絡(luò)比無向網(wǎng)絡(luò)具有更多的優(yōu)勢,因此研究有向網(wǎng)絡(luò)的性質(zhì)是有意義的.在本文我們也將關(guān)于極大局部連通性的容錯度推廣到有向圖,提出了有向圖關(guān)于極大局部連通性的容錯度的概念.超立方體網(wǎng)絡(luò)憑借其良好的拓?fù)湫再|(zhì)以及簡潔的實(shí)現(xiàn)方式而成為最為流行的網(wǎng)絡(luò)之一.為了改進(jìn)和推廣超立方體,一些類超立方體網(wǎng)絡(luò)被提出,如kk元n方體和單向k元n方體.本文分四章研究了超立方體、kk元n方體和單向k元n方體關(guān)于極大局部連通性的容錯度.第一章主要介紹了一些圖論方面的... 

【文章來源】：山西大學(xué)山西省

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

【學(xué)位級別】：碩士

【部分圖文】：

圖１．超立方體ｑ３??

ｕ?＝?ａｎ－ｉａｒｔ－２…郵與Ｖ?＝?ｋ－ｉ６ｎ－２…知相鄰當(dāng)且僅當(dāng)存在整數(shù)ｄ，使得ａｄ?＝?Ｗ士ｌ（ｍｏｄ??ｆｃ）且對任意的ｉ?＃?ｄ都有ａ；二ｂｉ？此時，稱邊ｍ；為一＇條ｄ維邊．??圖２給出了?５元２方體Ｑｉ．??００?１０?２０?３０?４０??才３４?＾＾４ｙ??圖２．?５元２方體防．??二、有向網(wǎng)絡(luò)??由于ｆｃ元ｎ方體具有對稱性、正則性和哈密爾頓性等優(yōu)良的性質(zhì)而成為一些多??處理機(jī)系統(tǒng)的拓?fù)浣Y(jié)構(gòu)．在實(shí)際應(yīng)用中，網(wǎng)絡(luò)中的一對處理器間的直接通信聯(lián)系往往??由兩個方向相反的通信信道實(shí)現(xiàn)的，基于此觀察，可將網(wǎng)絡(luò)中的一條邊看成兩條端點(diǎn)??相同方向相反的弧，由此一個無向網(wǎng)絡(luò)可看成一個有向網(wǎng)絡(luò)．為了減低構(gòu)造網(wǎng)絡(luò)的費(fèi)??用和復(fù)雜性，單向網(wǎng)絡(luò)的概念被提出１３，４１．特別地，張國珍問在２０１５年提出了單向Ａ：??元ｎ方體這一概念．??定義１．１．３．（問）對給定整數(shù)ｎ＞ｌ和ｆｃ＞３．單向／ｃ元ｎ方體￥的頂點(diǎn)集為??｛ａｒｅ—ｉａｒａ＿２?…ａ〇?：叫?６?｛０，１，…，Ａ；?—?ｌ｝，ｉ?＝?０，１，…，ｎ?＿?１｝?？頂點(diǎn)?ｗ?＝?ａｒａ＿ｉａ？＿２?…ａ〇?控制??頂點(diǎn)ｗ?＝?ｂｎ＿ｉｂｎ—２?？．．知當(dāng)且僅當(dāng)存在整數(shù)ｄ?＃牐?枺?牐保?浚??

§１．２極大局部連通性??無向圖的極大局部連通性??和選擇網(wǎng)絡(luò)時的一個基本考量是網(wǎng)絡(luò)的可靠性，它通Ｇ中任意兩個不同的頂點(diǎn)Ｕ和Ｖ之間都存在路，則１．２．１．（網(wǎng)）連通圖Ｇ中的一個點(diǎn)子集Ｓ是一個點(diǎn)最小點(diǎn)割的基數(shù)稱為Ｇ的連通度，記為ｋ（Ｇ）．??是連通度“割”版本的定義，下面給出連通度“路”版本明這兩個定義是等價的．??１．２．２．?（［６］）設(shè)ｕ和？；是連通圖Ｇ中不同的兩點(diǎn)，用ｘ－ｗ路的最大數(shù)目．定義Ｇ的連通度為ｋ（Ｇ）?＝?ｍｉｎ｛ＫＣ１．２．１．（叩設(shè)ｕ和是圖Ｇ中不相鄰的兩點(diǎn)．則Ｇ

【參考文獻(xiàn)】：
期刊論文
[1]在PMC模型下單向k元n立方體的診斷度[J]. 張雯麗,林上為,李藝海,郭慧鈴.  計算機(jī)工程與應(yīng)用. 2019(04)
[2]單向k-元n-立方體網(wǎng)絡(luò)[J]. 張國珍.  計算機(jī)工程與應(yīng)用. 2015(20)
[3]On Restricted Connectivity and Extra Connectivity of Hypercubes and Folded Hypercubes[J]. 徐俊明,朱強(qiáng),侯新民,周濤.  Journal of Shanghai Jiaotong University. 2005(02)
[4]無向de-Bruijn圖的超級邊連通性和限制性邊連通度[J]. 呂長虹,張克民.  應(yīng)用數(shù)學(xué)學(xué)報. 2002(01)



本文編號：3422200