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

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

【摘要】：近年來(lái),隨著大規(guī)模集合電路,微電子技術(shù),大規(guī)模互聯(lián)網(wǎng)絡(luò)的飛速發(fā)展,人們對(duì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)要求越來(lái)越高.圖的理論及其在各個(gè)領(lǐng)域的廣泛應(yīng)用越來(lái)越受到數(shù)學(xué)界和其他科學(xué)界的重視.網(wǎng)絡(luò)的可靠性和容錯(cuò)性受到人們的普遍關(guān)注.圖論中圖的連通性分析為此類(lèi)問(wèn)題的研究提供了重要的理論依據(jù).設(shè)計(jì)和分析多處理機(jī)互聯(lián)網(wǎng)絡(luò)時(shí),通常會(huì)涉及某些類(lèi)型的網(wǎng)絡(luò)模型,利用圖的點(diǎn)和邊來(lái)代替網(wǎng)絡(luò)的節(jié)點(diǎn)和連線(xiàn),以此構(gòu)成相互連通的網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).通常將網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)抽象成圖或有向圖D=(V,E).這時(shí)D的頂點(diǎn)代表處理機(jī),連接頂點(diǎn)的邊表示一對(duì)處理機(jī)之間的直接通信聯(lián)系(有向邊則表示只能進(jìn)行單向聯(lián)系).在研究這種模型時(shí),經(jīng)常假設(shè)其節(jié)點(diǎn)不會(huì)失效,但每條邊相互獨(dú)立地以相等的概率p∈(0,1)失效.用m表示D的邊數(shù),λ(D)表示D的邊連通度,Ci(D)表示D的邊數(shù)為i的邊割數(shù)目,則D連通的概率為：要準(zhǔn)確的計(jì)算出D的可靠度,需要計(jì)算出每個(gè)系數(shù)Ci(D).但是,Provan和Ball在1983年指出計(jì)算出所有這些系數(shù)是NP-困難的.Colbour對(duì)此作了進(jìn)一步闡述.但是,在精確刻畫(huà)圖或有向圖的連通性方面,邊連通度或點(diǎn)連通度存在一些不足：首先,邊連通度或點(diǎn)連通度相同的圖或有向圖的可靠性可能有所不同.其次,不能區(qū)分刪掉λ-割或κ-割后的圖或有向圖的不同類(lèi)型,即未考慮網(wǎng)絡(luò)的破壞程度.第三,默認(rèn)圖或有向圖的任何子集中所有元素可能潛在地同時(shí)失效.為克服以上缺陷,自1983年Harary提出了條件邊連通度的概念,為該領(lǐng)域的研究開(kāi)辟了新的道路.經(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ì).在第一章中,主要介紹本文的研究背景和一些已有的結(jié)果,以及文章中涉及的一些基本概念、術(shù)語(yǔ)符號(hào).在第二章中,主要研究定向圖極大與超級(jí)局部邊連通的充分條件,首先,給出了利用度序列的低度端保證定向圖是極大和超級(jí)局部邊連通的充分條件.定理2.1.3設(shè)D為n階定向圖,度序列為d1≥d2≥…≥dn(=δ),△'=△'(D).(1)若δ≥[n-1/4],或δ≤[n-2/4]且對(duì)某整數(shù)k,1≤k≤2δ+1,有∑ dn+1-i≥k(n-1-k)+1+max{0, △'+k-2δ-2,2△'+2k-n-2},則D是極大局部邊連通的.(2)若δ≥[(n+1)/4],或δ≤[n/4]且對(duì)某整數(shù)k,1≤k≤2δ有∑ dn+1-i≥k(n-1-k)+1+max{0, △'+k-2δ-2,2△'+2k-n-2},則D是超級(jí)局部邊連通的.其次,給出了二部定向圖極大局部邊連通的度和條件.定理2.2.4設(shè)D為n階二部定向圖,最小度δ≥2.若對(duì)任意同部頂點(diǎn)u,v,有d+(u) +d+(v)n/2-3/2,d-(u)+d-(v)n/2-3/2,則D是極大局部邊連通的.在第三章,主要研究有向圖與定向圖的依賴(lài)團(tuán)數(shù)的局部邊連通性.首先給出有向圖依賴(lài)團(tuán)數(shù)的極大局部邊連通的充分條件.定理3.1.3設(shè)D為n階有向圖,團(tuán)數(shù)w(D)≤p,度序列為d1≥d2≥…≥dn(=δ), △'=△'(D).若n≤2[(pδ)/(p-1)]-1,或n≥2[(pδ)/(p-1)]且對(duì)某整數(shù)k,1≤k≤[δ/(p-1)],有則D是極大局部邊連通的.定理3.1.4設(shè)D為n階有向圖,團(tuán)數(shù)w(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是極大局部邊連通的.然后,又給出了依賴(lài)團(tuán)數(shù)的超級(jí)局部邊連通的充分條件,即有如下結(jié)果：定理3.2.4設(shè)D為n階有向圖,團(tuán)數(shù)w(D)≤p,最小度δ≥3,度序列為d1≥d2≥...≥dn(=δ),△'=△'(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.2.5設(shè)D為n階定向圖,團(tuán)數(shù)w(D)≤p,最小度為δ≥2,度序列為d1≥d2≥…≥dn(=δ),△'=△'(D).若n≤2[(2pδ)/(p-1)]-3,或n≥2[(2pδ)/(p-1)]-2且對(duì)某整數(shù)k,1≤k≤[(2pδ)/(p-1)]-1,有則D是超級(jí)局部邊連通的.在第四章中,主要研究有向圖極大邊連通的倒數(shù)度條件.得到如下結(jié)果：定理4.1.2設(shè)D是n≥2階強(qiáng)連通有向圖,最小度δ.若δ≥[n-1/2],或δ≤[n-2/2]且則D是極大邊連通的.定理4.2.2設(shè)D是n階強(qiáng)連通無(wú)三角形有向圖,最小度δ.若δ≥[(n+1/4],或δ≤ [n/4]且滿(mǎn)足則D是極大邊連通的.在第五章中,得到保證無(wú)p-鉆圖與不含K2,3圖局部連通性的充分條件.定理5.2設(shè)p≥2為整數(shù),G是n階連通無(wú)p-鉆圖,u,v∈V(G),則G是超級(jí)局部連通的,若其中r=min{d(u),d(v)}-δ(≥0).定理5.5不含k2,3,最小度δ≥2的n階連通圖G為極大局部連通的,若階數(shù)n≤3δ-3.
【學(xué)位授予單位】：山東師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：O157.5

【參考文獻(xiàn)】

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 邵光鳳;有向圖的局部邊連通度的性質(zhì)[D];山東師范大學(xué);2012年

，

本文編號(hào)：1192418