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

1、近年來(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)注.圖論中圖的連通性分析為此類問(wèn)題的研究提供了重要的理論依據(jù).
　　設(shè)計(jì)和分析多處理機(jī)互聯(lián)網(wǎng)絡(luò)時(shí)，通常會(huì)涉及某些類型的網(wǎng)絡(luò)模型，利用圖的點(diǎn)和邊來(lái)代替網(wǎng)絡(luò)的節(jié)點(diǎn)和連線，以此構(gòu)成相互連通的網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).通常將網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)抽象成圖或

2、有向圖（此處公式省略）.這時(shí)D的頂點(diǎn)代表處理機(jī)，連接頂點(diǎn)的邊表示一對(duì)處理機(jī)之間的直接通信聯(lián)系(有向邊則表示只能進(jìn)行單向聯(lián)系).在研究這種模型時(shí)，經(jīng)常假設(shè)其節(jié)點(diǎn)不會(huì)失效，但每條邊相互獨(dú)立地以相等的概率pG(0,1)失效.用m表示D的邊數(shù)，A(D)表示D的邊連通度，Q(D)表示D的邊數(shù)為i的邊割數(shù)目，則D連通的概率為：（此處公式省略）要準(zhǔn)確的計(jì)算出D的可靠度，需要計(jì)算出每個(gè)系數(shù).但是，Provan和Ball在1983年指出計(jì)算出所有這些系數(shù)

3、是困難的.對(duì)此作了進(jìn)一步闡述.
　　但是，在精確刻畫(huà)圖或有向圖的連通性方面，邊連通度或點(diǎn)連通度存在一些不足：首先，邊連通度或點(diǎn)連通度相同的圖或有向圖的可靠性可能有所不同.其次，不能區(qū)分刪掉A-割或k-割后的圖或有向圖的不同類型，即未考慮網(wǎng)絡(luò)的破壞程度.第三，默認(rèn)圖或有向圖的任何子集中所有元素可能潛在地同時(shí)失效.為克服以上缺陷，自1983年Harary提出了條件邊連通度的概念，為該領(lǐng)域的研究開(kāi)辟了新的道路.經(jīng)過(guò)二十多年的發(fā)展，邊連通

4、性所涉及的內(nèi)容日益豐富和具體，包括超級(jí)邊連通性、極大局部邊連通性和超級(jí)局部邊連通性等.類似的，在圖的點(diǎn)連通性方面，也出現(xiàn)了極大連通性、極大局部連通性等概念.這些參數(shù)都能更深刻地刻畫(huà)圖或有向圖的邊、點(diǎn)連通性質(zhì).本人在前人工作的基礎(chǔ)上，繼續(xù)研究圖或有向圖的超級(jí)邊連通性以及圖的的超級(jí)局部連通性等相關(guān)性質(zhì).
　　在第一章中，主要介紹本文的研究背景和一些已有的結(jié)果，以及文章中涉及的一些基本概念、術(shù)語(yǔ)符號(hào).
　　在第二章中，主要研究定向

5、圖極大與超級(jí)局部邊連通的充分條件，首先，給出了利用度序列的低度端保證定向圖是極大和超級(jí)局部邊連通的充分條件.
　　定理2.1.3設(shè)D為n階定向圖，度序列（此處公式省略）.
　　(1)若（此處公式省略）則D是極大局部邊連通的.
　　(2)若（此處公式省略）則D是超級(jí)局部邊連通的.
　　其次，給出了二部定向圖極大局部邊連通的度和條件.
　　定理2.2.4設(shè)D為n階二部定向圖，最小度5>2.若對(duì)任意同部頂點(diǎn)u,v

6、,有（此處公式省略）,則D是極大局部邊連通的.
　　在第三章，主要研究有向圖與定向圖的依賴團(tuán)數(shù)的局部邊連通性.首先給出有向圖依賴團(tuán)數(shù)的極大局部邊連通的充分條件.
　　定理3.1.3設(shè)D為n階有向圖，團(tuán)數(shù)w(D)< p,度序列為（此處公式省略）.若（此處公式省略）或（此處公式省略）且對(duì)某整數(shù)（此處公式省略）,有（此處公式省略）則D是極大局部邊連通的.
　　定理3.1.4設(shè)D為n階有向圖，團(tuán)數(shù)w(D)< p,度序列為（此處

7、公式省略）,（此處公式省略）（此處公式省略）.若（此處公式省略）,或n>2L吳」且對(duì)某整數(shù)k,（此處公式省略）,有（此處公式省略）則D是極大局部邊連通的.
　　然后，又給出了依賴團(tuán)數(shù)的超級(jí)局部邊連通的充分條件，即有如下結(jié)果：
　　定理3.2.4設(shè)D為n階有向圖，團(tuán)數(shù)（此處公式省略）,最小度6>3,度序列為（此處公式省略）.右（此處公式省略），或（此處公式省略）且對(duì)某整數(shù)（此處公式省略）,有（此處公式省略）則D是超級(jí)局部邊連通

8、的.
　　定理3.2.5設(shè)D為n階定向圖，團(tuán)數(shù)（此處公式省略）,最小度為5>2，度序列為（此處公式省略）,（此處公式省略）.若（此處公式省略），或（此處公式省略）且對(duì)某整數(shù)（此處公式省略）,有（此處公式省略）則D是超級(jí)局部邊連通的.
　　在第四章中，主要研究有向圖極大邊連通的倒數(shù)度條件.得到如下結(jié)果：
　　定理4.1.2設(shè)D是n>2階強(qiáng)連通有向圖，最小度（此處公式省略）若（此處公式省略），或（此處公式省略）且（此處公式

9、省略）則D是極大邊連通的.
　　定理4.2.2設(shè)D是n階強(qiáng)連通無(wú)三角形有向圖，最小度（此處公式省略）若（此處公式省略），或（此處公式省略）且滿足（此處公式省略）則D是極大邊連通的.
　　在第五章中，得到保證無(wú)p-鉆圖與不含K2,3圖局部連通性的充分條件.
　　定理5.2設(shè)p>2為整數(shù)，G是n階連通無(wú)p-鉆圖，（此處公式省略）,貝憶是超級(jí)局部連通的，若（此處公式省略）其中（此處公式省略）.
　　定理5.5不含化3，