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

【文章來源】：山西大學山西省

【文章頁數】：52 頁

【學位級別】：碩士

【部分圖文】：

圖１．超立方體ｑ３??

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

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

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



本文編號：3422200