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

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

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

3、制邊連通度的概念推廣到有向圖，提出限制弧連通度的概念，并給出限制弧連通度的一個(gè)上界ξ(D).有向圖的限制弧連通度能夠比弧連通度更精確的度量網(wǎng)絡(luò)的可靠性和容錯(cuò)性.稱有向圖D的一個(gè)弧子集S是D的限制弧割，如果D-S中存在一個(gè)非平凡的強(qiáng)連通分支D1使得D-V(D1)包含至少一條弧.若強(qiáng)連通的有向圖D存在限制弧割，則稱D是λ'-連通的.λ'-連通圖D的最小限制弧割所含的弧數(shù)稱為D的限制弧連通度，記為λ'(D).設(shè)D的圍長(zhǎng)為g，任取長(zhǎng)度為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)性.對(duì)有向圖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)}.若一個(gè)λ'-連通有向圖D滿足λ'(D)=ξ('D)，則稱D是λ'-最優(yōu)的.
　　本文主要研究有向圖的限制弧連通度及其上界優(yōu)化問(wèn)題.本文分為三章.

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

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