有向圖和圖的邊連通性與點連通性.pdf

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

2、).在研究這種模型時,經(jīng)常假設其節(jié)點不會失效,但每條邊相互獨立地以相等的概率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)絡的可靠性.顯然P(D,p)越小,網(wǎng)絡的可靠性越好.但是對于一般圖,確定所有的系數(shù)Ci是一個NP-困難問題.對此,colbour做了進一步的闡述.當假

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

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

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