發(fā)布時(shí)間：2017-11-15 03:29

  本文關(guān)鍵詞：有向圖和定向圖的邊連通性研究

  更多相關(guān)文章： 有向圖 定向圖 極大(超級(jí))邊連通性 極大(超級(jí))局部邊連通性 倒數(shù)度

【摘要】：圖論是一門古老而又活躍的學(xué)科,也是一門很有實(shí)用價(jià)值的學(xué)科.它是研究工程技術(shù),自然科學(xué)等的重要數(shù)學(xué)工具,應(yīng)用極為廣泛.在現(xiàn)代社會(huì)中,人們的日常生活,學(xué)習(xí)和工作與多處理機(jī)互聯(lián)網(wǎng)絡(luò)的關(guān)系也越來(lái)越密切.因此網(wǎng)絡(luò)的可靠性和容錯(cuò)性受到人們的普遍關(guān)注,從而網(wǎng)絡(luò)的可靠性和容錯(cuò)性的研究成為了近年來(lái)國(guó)內(nèi)外研究的一大熱點(diǎn).在設(shè)計(jì)和分析大規(guī)�；ヂ�(lián)網(wǎng)的可靠性和容錯(cuò)性時(shí),一個(gè)很重要的模型是將網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)抽象成圖或有向圖D=(V,E).D的頂點(diǎn)代表處理機(jī),連接頂點(diǎn)的邊表示一對(duì)處理機(jī)之間的直接通信聯(lián)系(有向邊則表示只能進(jìn)行單向聯(lián)系).研究這種模型時(shí),假設(shè)其節(jié)點(diǎn)不會(huì)失效,但每條邊相互獨(dú)立地以相等的概率p∈(0,1)失效.則D不連通的概率為：其中m表示D的邊數(shù),λ(D)表示D的邊連通度,Ci(D)表示D的邊數(shù)為i的邊割數(shù)目,因而可用D連通的概率R(D,p)=1—P(D,p)來(lái)衡量網(wǎng)絡(luò)的可靠性.顯然P(D,p)越小,網(wǎng)絡(luò)的可靠性越好,但是對(duì)于一般圖,確定所有的系數(shù)G是NP-困難的.對(duì)此,Colbour[2]做了進(jìn)一步的闡述.當(dāng)假設(shè)D的邊不會(huì)失效,但其節(jié)點(diǎn)相互獨(dú)立地以相等的概率p∈(0,1)失效時(shí)也有類似的討論.圖或有向圖的邊連通度是反映其連通性質(zhì)的一個(gè)重要參數(shù).而在精確刻畫圖或有向圖的連通性方面,經(jīng)典邊連通度存在一些不足：首先,邊連通度相同的圖或有向圖的可靠性可能有所不同.其次,不能區(qū)分刪掉λ-割后所得圖或有向圖的不同類型.最后,默認(rèn)圖或有向圖的任何子集中所有元素可能潛在地同時(shí)失效.為了克服以上缺陷,自1983年Harary[5]提出了條件邊連通度的概念,經(jīng)過(guò)三十多年的發(fā)展,邊連通性所涉及的內(nèi)容日益豐富和具體,其中包括極大邊連通性、超級(jí)邊連通性、極大局部邊連通性和超級(jí)局部邊連通性等.目前,對(duì)于這一鄰域已有了廣泛而深入的研究.本人在前人工作的基礎(chǔ)上,繼續(xù)研究圖或有向圖的邊連通的相關(guān)性質(zhì).本文主要研究有向圖與定向圖的邊連通性的一些條件.在第一章中,主要介紹本文的研究背景和一些已有的結(jié)果,以及文章中涉及的一些基本概念、術(shù)語(yǔ)符號(hào).在第二章中,首先給出定向圖依賴于團(tuán)數(shù)的超級(jí)邊連通性的度序列條件：為簡(jiǎn)潔起見(jiàn),本章所討論的定向圖的階數(shù)n為偶數(shù)時(shí),令v=1,否則,令v=0；當(dāng)所討論的定向圖的團(tuán)數(shù)ω(D)≤p,最小出度,最小入讀,最小度分別為δ+,δ-,δ時(shí),令定理2.1.5 設(shè)D是n階定向圖,團(tuán)數(shù)ω(D)≤p且p≥4,出度序列為d1+≥d2+≥…≥dn+(=δ+≥2),入度序列為d1-≥d2-≥…≥dn-(=δ-≥2).若則D是超級(jí)邊連通的.定理2.1.6 設(shè)D是n階定向圖,團(tuán)數(shù)ω(D)≤p且p≥4,度序列為d1≥d2≥…≥若則D是超級(jí)邊連通的.定理2.1.7 設(shè)D是n階定向圖,團(tuán)數(shù)ω(D)≤p且p≥4,n為偶數(shù),度序列為d1≥若則D是超級(jí)邊連通的.然后又討論了有向圖和定向圖極大局部和超級(jí)局部邊連通依賴于團(tuán)數(shù)的度序列條件,得到了以下結(jié)果：定理2.2.4 設(shè)D為n階定向圖,團(tuán)數(shù)ω(D)≤p,度序列為d1≥d2≥…≥dn(=δ),△’=△’(D).若n≤4[pδ/p-1]-1或若n≥4[pδ/p-1]且對(duì)某整數(shù)k,1≤k≤2δ+1,有則D是極大局部邊連通的.定理2.3.4 設(shè)D為n階有向圖,團(tuán)數(shù)ω(D)≤p,度序列為d1≥d2≥…≥dn(=δ),△’=△’(D).若n≤2[pδ/p-1]-1或若n≥2[pδ/p-1]且對(duì)某整數(shù)k,1≤k≤[pδ/p-1],有則D是極大局部邊連通的.定理2.3.11設(shè)D為n階有向圖,團(tuán)數(shù)ω(D)≤p,度序列為d1≥d2≥…≥dn(=δ≥3),△'=△'(D).若n≤2[pδ/p-1]-3或若n≥2[pδ/p-1]-2且對(duì)某整數(shù)k,1≤k≤[pδ/p-1]-1,有則D是超級(jí)局部邊連通的.在第三章,首先給出了有向圖極大局部邊連通的度序列條件：定理3.1.3設(shè)D為n階有向圖,度序列為d1≥d2≥…≥dn(=d),△'=△'(D).若δ≥[n/2]或若δ≤[n2/]-1且對(duì)某整數(shù)k,1≤k≤δ+1,有則D是極大局部邊連通的.接著又討論了二部有向圖和定向圖的邊連通性的度序列條件：定理3.2.3設(shè)D為n階二部有向圖,度序列為d1≥d2≥…≥dn(=δ).若δ≥[到+1或若δ≤[n/4]且對(duì)某整數(shù)k,1≤k≤δ,有則D是極大邊連通的.定理3.2.5設(shè)D為n階二部定向圖,度序列為d1≥d2≥…≥dn(=δ≥2).若δ≥[n+3/8]或若δ≤[n+2/8]且對(duì)某整數(shù)k,1≤k≤4δ-1,有則D是超級(jí)邊連通的.定理3.2.7(1)設(shè)D為n階二部定向圖,度序列為d1≥如≥…≥dn(=δ≥1),△’=△’(D).若δ≥[n+1/8]或若δ≤[n/8]且對(duì)某整數(shù)k,1≤k≤4δ,有則D是極大局部邊連通的.(2)設(shè)D為n階二部定向圖,度序列為d1≥d2≥…≥dn(=δ≥2),△'=△'(D).若δ≥[n+/3]或若δ≤[n+2/8]且對(duì)某整數(shù)k,1≤k≤4δ-1,有則D是超級(jí)局部邊連通的.最后,主要討論了定向圖極大邊連通與超級(jí)邊連通的倒數(shù)度條件：定理4.1.4設(shè)圖D為無(wú)三角形連通n階定向圖,最小度為δ,邊連通度為λ,若δ≥[n/8]+1或若δ≤[n/8]且則D是極大邊連通的.定理4.2.3令D為強(qiáng)連通無(wú)三角形n階定向圖,最小度為δ≥2,邊連通度為λ.若δ≥[n+3/8]或δ≤[n+2/8]且則D是超級(jí)邊連通的.
【學(xué)位授予單位】：山東師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前1條

1 邵光鳳;高敬振;;極大局部邊連通和超級(jí)局部邊連通有向圖的度條件[J];科學(xué)技術(shù)與工程;2011年23期

，

本文編號(hào)：1188209