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

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

2、).在研究這種模型時(shí),經(jīng)常假設(shè)其節(jié)點(diǎn)不會(huì)失效,但每條邊相互獨(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)來(lái)衡量網(wǎng)絡(luò)的可靠性.顯然P(D,p)越小,網(wǎng)絡(luò)的可靠性越好.但是對(duì)于一般圖,確定所有的系數(shù)Ci是一個(gè)NP-困難問(wèn)題.對(duì)此,colbour做了進(jìn)一步的闡述.當(dāng)假

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

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

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