有向圖和定向圖的邊連通性和點連通性研究.pdf

1、近年來，隨著大規(guī)模集合電路，微電子技術(shù)，大規(guī)?；ヂ?lián)網(wǎng)絡(luò)的飛速發(fā)展，人們對網(wǎng)絡(luò)的拓撲結(jié)構(gòu)要求越來越高.圖的理論及其在各個領(lǐng)域的廣泛應用越來越受到數(shù)學界和其他科學界的重視.網(wǎng)絡(luò)的可靠性和容錯性受到人們的普遍關(guān)注.圖論中圖的連通性分析為此類問題的研究提供了重要的理論依據(jù).
　　設(shè)計和分析多處理機互聯(lián)網(wǎng)絡(luò)時，通常會涉及某些類型的網(wǎng)絡(luò)模型，利用圖的點和邊來代替網(wǎng)絡(luò)的節(jié)點和連線，以此構(gòu)成相互連通的網(wǎng)絡(luò)的拓撲結(jié)構(gòu).通常將網(wǎng)絡(luò)的拓撲結(jié)構(gòu)抽象成圖或

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

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

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

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

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

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

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

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