圖和有向圖的邊連通性.pdf

1、多處理機系統(tǒng)的互連網(wǎng)絡(luò)拓?fù)渫ǔＲ裕ㄓ邢蚧驘o向）圖為數(shù)學(xué)模型.對互連網(wǎng)絡(luò)的性能的一個關(guān)鍵要求是希望網(wǎng)絡(luò)的可靠（容錯）性好，這對應(yīng)于圖論的術(shù)語來說，就是希望圖的連通度和邊連通度大.設(shè)G是無向簡單連通圖，最小度為δ,邊連通度為λ，則λ≤δ.如果圖G滿足λ=δ，那么稱圖G是極大邊連通的.如果圖G的任一最小邊割是與一個最小度頂點相關(guān)聯(lián)的邊集，則稱圖G是超級邊連通的.超級邊連通性是比極大邊連通性更精確的一個網(wǎng)絡(luò)可靠性指標(biāo).
　　在第一章第一節(jié)

2、，我們給出本文將用到的圖論方面的主要術(shù)語、記號.在第二節(jié)，我們介紹了邊連通性方面的基本概念和基本結(jié)論.
　　本文第二章主要研究有向圖邊連通度的下界，給出了有向圖、二部有向圖和定向圖的邊連通度的新的下界.
　　沒有2-圈的有向圖稱為定向圖.有許多作者已經(jīng)給出了定向圖極大邊連通的充分條件，但到目前為止，對于給定團數(shù)的圖和定向圖是極大邊連通和超級邊連通的相關(guān)條件卻不是很受關(guān)注.本文第三章我們將給出一些依賴于團數(shù)的圖和定向圖極大邊連

3、通和超級邊連通的度序列條件:
　　(1)設(shè)G是一個團數(shù)ω(G)≤p的n階圖，最小度為δ（≥4(p-1）/p)，邊連通度為λ,度序列為d1≥d2≥…≥dn.若n≤2([)pδ/2(p-1)」-1或滿足n≥2([)pδ/p-1」且存在整數(shù)k（1≤k≤δ）使得k∑i=1（di+dn+i-δ）≥k（n-2k+2k(p-1)/p）+2δ+1成立，則G是超級邊連通的.
　　(2)設(shè)D是一個團數(shù)ω(D)≤ p的n階定向圖，最小度為δ，邊連

4、通度為λ，度序列為d1≥d2≥…≥dn.若n≤2([)2pδ/p-1」-1或滿足n≥2([)2pδ/p-1」且存在整數(shù)k（1≤k≤2δ+1）使得k∑i=1（di+dn+i-2δ-1）≥k(n-2k+k(p-1)/p)+2δ-1成立，則λ=δ.
　　(3)設(shè)D是一個團數(shù)ω(D)≤p的n階定向圖，最小度為δ（≥2(p-1)/p），邊連通度為λ，度序列為d1≥d2≥…≥dn.若n≤2([)pδ/p-1」-1或滿足n≥2([)2pδ/p-

5、1」且存在整數(shù)k（1≤k≤([)δ/p-1」）使得k∑i=1di+(2p-1)k∑i=1dn+1-i≥k(p-1)(n-p)+2δ+1成立，則D是超級邊連通的.
　　第四章研究了直徑為2的圖的超級邊連通性質(zhì).Fiol在1992年給出了有向圖是超級邊連通的三個充分條件(a) diam(D)=2且D的頂點出度為δ的頂點集或入度為δ的頂點集M的導(dǎo)出子圖D[M]沒有δ階完全子圖K*δ:(b)對所有滿足d(x，y)≥2的任意一對頂點x，y，