有向圖的限制弧連通度.pdf

1、當(dāng)前VLSI技術(shù)的進(jìn)步，使得建造具有數(shù)千甚至數(shù)萬個處理器的超大型并行分布式系統(tǒng)已經(jīng)可以實(shí)現(xiàn)了.而在這些并行分布式系統(tǒng)中，最重要的一個步驟就是決定各個處理器之間連接的拓?fù)浣Y(jié)構(gòu)，即互連網(wǎng)絡(luò)（簡稱網(wǎng)絡(luò)）.這是因?yàn)榫W(wǎng)絡(luò)的拓?fù)湫再|(zhì)直接影響到并行分布式系統(tǒng)的硬件和軟件兩個層面的各種設(shè)計.
　　多處理機(jī)系統(tǒng)的互連網(wǎng)絡(luò)通常以有向圖或無向圖作為模型，因此網(wǎng)絡(luò)拓?fù)涞男阅芸梢酝ㄟ^圖的性質(zhì)和參數(shù)來度量.在設(shè)計大規(guī)模多處理機(jī)系統(tǒng)的網(wǎng)絡(luò)拓?fù)鋾r，我們要考慮的一

2、個問題是系統(tǒng)的可靠性和容錯性.邊（?。┻B通度是度量網(wǎng)絡(luò)可靠性和容錯性的一個重要參數(shù)，然而這個參數(shù)存在明顯的缺陷:它假定系統(tǒng)的任何部分都可能同時損壞，這在實(shí)際應(yīng)用中幾乎不可能發(fā)生;而且當(dāng)兩個圖具有相同的邊連通度的時候，可靠性就無法比較.為彌補(bǔ)這個缺陷，人們推廣邊連通度，提出限制邊連通度的概念.
　　Esfahanian指出:在度量網(wǎng)絡(luò)的容錯性和可靠性時，限制邊連通度比傳統(tǒng)的度量工具邊連通度更加精確.在2007年，Volkmann將限

3、制邊連通度的概念推廣到有向圖，提出限制弧連通度的概念，并給出限制弧連通度的一個上界ξ(D).有向圖的限制弧連通度能夠比弧連通度更精確的度量網(wǎng)絡(luò)的可靠性和容錯性.稱有向圖D的一個弧子集S是D的限制弧割，如果D-S中存在一個非平凡的強(qiáng)連通分支D1使得D-V(D1)包含至少一條弧.若強(qiáng)連通的有向圖D存在限制弧割，則稱D是λ'-連通的.λ'-連通圖D的最小限制弧割所含的弧數(shù)稱為D的限制弧連通度，記為λ'(D).設(shè)D的圍長為g，任取長度為g的有向

4、圈Cg=u1u2...ugu1，令ξ(Cg)=min{gΣi=1d+(ui)-g，g∑i=1d-(ui)-g}且ξ(D)=min{ξ(q)}.在2008年，王世英和林上為提出最小弧度ξ'（D）的概念，證明在多數(shù)情形下最小弧度作為限制弧連通度的上界比ξ(D)更好，并討論了有向圖的λ'-最優(yōu)性.對有向圖D的任意弧xy∈A(D)，定義xy的弧度，若yx(∈)A(D)，則ξ'（xy）=min{d+(x)+d+（y）-1，d-(x)+d-(y)-

5、1，d+(x)+d-(y)-1，d-(x)+d+（y）}.若yx∈A(D)，則ξ'（xy）=min{d+(x)+d+(y)-2，d-(x)+d-(y)-2，d+(x)+d-(y)-1，d-(x)+d+（y）-1}.有向圖D的最小弧度為ξ'(D)=min{ξ'（xy）:xy∈A(D)}.若一個λ'-連通有向圖D滿足λ'(D)=ξ('D)，則稱D是λ'-最優(yōu)的.
　　本文主要研究有向圖的限制弧連通度及其上界優(yōu)化問題.本文分為三章.

6、r>　　第一章介紹了一些本文將要用到的有關(guān)圖論方面的基本概念.
　　第二章研究了有向圖的限制弧連通度問題，給出了強(qiáng)連通有向圖D是λ'-連通的且λ'(D)≤ξ(D)的幾個充分條件，主要結(jié)果如下:
　　(1)階至少為6，圍長為4的強(qiáng)連通有向圖D是λ'-連通的且滿足λ(D)≤λ'(D)≤ξ(D)，除非D是某幾類特殊圖.
　　(2)階至少為7，圍長為5的強(qiáng)連通有向圖D是λ'-連通的且滿足λ(D)≤λ'(D)≤ξ(D)，除非D是

7、某幾類特殊圖.
　　(3)設(shè)D是階數(shù)n≥4的強(qiáng)連通有向圖，若對任意的x∈V(D)，滿足d+(x)≥2且d-(x)≥2，則D是λ'-連通的且λ(D)≤λ'(D)≤ξ(D).
　　(4)設(shè)D是階數(shù)n≥4的強(qiáng)連通有向圖，在D中存在長為g的最短有向圈C1和長為g'的次短有向圈C2.若g'≥g+2，則D是λ'-連通的;若g'=g+1且|V(C1)∩ V(C2)|≤g-1，則D是λ'-連通的.
　　第三章改進(jìn)了圍長為2時有向圖D的