有向圖和圖的邊連通性與點(diǎn)連通性.pdf

1、隨著社會的不斷進(jìn)步,人們的生活、工作和學(xué)習(xí)與多處理機(jī)互聯(lián)網(wǎng)絡(luò)的聯(lián)系越來越緊密.自然,網(wǎng)絡(luò)的可靠性與容錯性倍受關(guān)注,進(jìn)而網(wǎng)絡(luò)的可靠性與容錯性分析就成為近年來國內(nèi)外研究的熱點(diǎn)之一.圖論中圖的連通性分析為此問題的研究提供了重要的理論支撐.
　　在設(shè)計、分析大規(guī)?；ヂ?lián)網(wǎng)絡(luò)的可靠性和容錯性時,通常將網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)抽象成圖或有向圖D=(V,E).這里D的頂點(diǎn)代表處理機(jī),連接頂點(diǎn)的邊表示一對處理機(jī)之間的直接通信聯(lián)系f有向邊則表示只能進(jìn)行單向聯(lián)系

2、).在研究這種模型時,經(jīng)常假設(shè)其節(jié)點(diǎn)不會失效,但每條邊相互獨(dú)立地以相等的概率p∈(0,1)失效.用m表示D的邊數(shù),λ(D)表示D的邊連通度,Ci(D)表示D的邊數(shù)為i的邊割數(shù)目,則D不連通的概率P(D,p)為（公式略）.
　　從而可用D連通的概率R(D,p)=1-P(D,p)來衡量網(wǎng)絡(luò)的可靠性.顯然P(D,p)越小,網(wǎng)絡(luò)的可靠性越好.但是對于一般圖,確定所有的系數(shù)Ci是一個NP-困難問題.對此,colbour做了進(jìn)一步的闡述.當(dāng)假

3、設(shè)D的邊不會失效,但其節(jié)點(diǎn)相互獨(dú)立地以相等的概率p∈(0,1)失效時也有類似的討論.
　　圖或有向圖的邊連通度與點(diǎn)連通度是反映其連通性質(zhì)的兩個重要參數(shù).但是,在精確刻畫圖或有向圖的連通性方面,邊連通度或點(diǎn)連通度存在一些不足:首先,邊連通度或點(diǎn)連通度相同的圖或有向圖的可靠性可能有所不同.其次,不能區(qū)分刪掉λ-割或K-割后的圖或有向圖的不同類型,即未考慮網(wǎng)絡(luò)的破壞程度.第三,默認(rèn)圖或有向圖的任何子集中所有元素可能潛在地同時失效.為克服

4、以上缺陷,自1983年Harary提出了條件邊連通度的概念,經(jīng)過三十年的發(fā)展,邊連通性所涉及的內(nèi)容日益豐富和具體,包括超級邊連通性、極大局部邊連通性和超級局部邊連通性等.類似的,在圖的點(diǎn)連通性方面,也出現(xiàn)了極大連通性、極大局部連通性等概念.這些參數(shù)都能更深刻地刻畫圖或有向圖的邊、點(diǎn)連通性質(zhì).本人在前人工作的基礎(chǔ)上,繼續(xù)研究圖或有向圖的超級邊連通性以及圖的超級局部連通性等相關(guān)性質(zhì).
　　在第一章中,主要介紹本文的研究背景和一些已有的

5、結(jié)果,以及文章中涉及的一些基本概念、術(shù)語符號.記有限簡單圖或有向圖D=(y(D),E(D)),其中V(D)表示D的頂點(diǎn)集,E(D)表示D的邊集,稱D的階數(shù)為n=|V(D)|.不含來回邊的有向圖稱為定向圖.
　　在第二章中，本文給出了二部定向圖極大與超級局部邊連通的鄰域條件（公式略），然后又討論了二部定向圖超級局部邊連通的度序列條件，得到了以下結(jié)果（公式略）.
　　在第三章，首先給出了二部定向圖超級邊連通的度序列條件（公式略）