任意無(wú)向圖的R點(diǎn)連通擴(kuò)充.pdf

1、連通擴(kuò)充問(wèn)題是圖論中連通性理論的一個(gè)重要組成部分,也是一個(gè)組合優(yōu)化問(wèn)題,在電網(wǎng)絡(luò)可靠性分析與設(shè)計(jì)等領(lǐng)域具有重大理論指導(dǎo)意義.本文研究了無(wú)向不加權(quán)連通圖的R點(diǎn)連通擴(kuò)充問(wèn)題,即給定一個(gè)無(wú)向圖G<,0>=(V<,0>,E<,0>),和一個(gè)連通要求矩陣R=[r<,ij>],在G<,0>中增加一個(gè)最小邊集E,使得G<,0>+E=(V<,0>+E<,0>∪E)中的任意兩點(diǎn)之間的點(diǎn)連通度均滿足κ(v<,i>,v<,j>;G<,0>+E)≥r<,ij>

2、.本文提出了一個(gè)復(fù)雜度為O( 32r'|V(G<,0>)|<'5>)的算法RUCA,能擴(kuò)充G<,0>為R點(diǎn)連通圖.在一些情況下,得到的R點(diǎn)連通圖是最小的;而在其他一些情況下,可以保證所得到的R點(diǎn)連通圖是極小的.算法的主要設(shè)計(jì)思想是:首先利用UTD變換將無(wú)向圖轉(zhuǎn)化為有向圖,再把有向圖經(jīng)SPLIT構(gòu)造把點(diǎn)連通擴(kuò)充問(wèn)題轉(zhuǎn)化為邊連通擴(kuò)充問(wèn)題.在對(duì)有向圖的邊連通擴(kuò)充中,采用先增廣擴(kuò)充再檢驗(yàn)的方法,如果不滿足要求,再將其分解成一系列不可壓縮子圖,分