最大流最小割定理.docx

《最大流最小割定理.docx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、最大流最小割默認(rèn)分類2010-06-2015:39:10閱讀293評(píng)論0??字號(hào)：大中小?訂閱最大流問(wèn)題最大流問(wèn)題是一類極為廣泛的問(wèn)題。不僅在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流、供水網(wǎng)絡(luò)中有水流、金融系統(tǒng)中有現(xiàn)金流、通訊網(wǎng)絡(luò)中信息流……等。五十年代，F(xiàn)ord(福特)、Fulkerson(富克遜)建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。網(wǎng)絡(luò)與流的概念對(duì)于有向圖D=(V,A)，如果V中有一發(fā)點(diǎn)vs（亦稱源還有一收點(diǎn)（亦稱為匯）記為vt其余均為中間點(diǎn)，且對(duì)A中的每條弧均有權(quán)W(vi,vj)?0（簡(jiǎn)記為Wij，并稱為弧容量），則稱這樣的賦權(quán)有向圖D

2、為容量網(wǎng)絡(luò)，記為D=(V,A,W)。通過(guò)D中弧(vi,vj)的物流量fij，稱為弧(vi,vj)的流量。所有弧上流量的集合f={fij}稱為該網(wǎng)絡(luò)D的一個(gè)流。最大流最小截量定理：???任一網(wǎng)絡(luò)D中，最大流的流量=最小截集的截量。最大流算法的鄰接陣實(shí)現(xiàn)1.???最大流最小割定理介紹：把一個(gè)流網(wǎng)絡(luò)的頂點(diǎn)集劃分成兩個(gè)集合S和T，使得源點(diǎn)s∈S且匯點(diǎn)t∈T，割(S,T)的容量C(S,T)=∑Cuv,其中u∈S且v∈T。從直觀上看，截集(S,T)是從源點(diǎn)s到匯點(diǎn)t的必經(jīng)之路，如果該路堵塞則流從s無(wú)法到達(dá)t。于是我們可以得到下面的定理：最大流最小割定理：任意一

3、個(gè)流網(wǎng)絡(luò)的最大流量等于該網(wǎng)絡(luò)的最小的割的容量。這個(gè)定理的證明這里就不給出了，可以參考圖論方面的資料。2.???求最大流的Edmonds-Karp算法簡(jiǎn)介：若給定一個(gè)可行流F=(Fij)，我們把網(wǎng)絡(luò)中使Fij=Cij的弧稱為飽和弧，F(xiàn)ij

4、們可以向這條路徑上壓入更多的流，使得其中的一條弧達(dá)到飽和。這樣的路徑p叫做可改進(jìn)路，可壓入的流量叫做該可改進(jìn)路的可改進(jìn)流量。重復(fù)這個(gè)過(guò)程，直到整個(gè)網(wǎng)絡(luò)找不到一條可改進(jìn)路，顯然這時(shí)候網(wǎng)絡(luò)的流量達(dá)到最大。Edmonds-Karp算法就是利用寬度優(yōu)先不斷地找一條從s到t的可改進(jìn)路，然后改進(jìn)流量，一直到找不到可改進(jìn)路為止。由于用寬度優(yōu)先，每次找到的可改進(jìn)路是最短的可改進(jìn)路，通過(guò)分析可以知道其復(fù)雜度為O(VE2)。Edmonds-Karp算法的偽代碼如下：設(shè)隊(duì)列Q--存儲(chǔ)當(dāng)前未檢查的標(biāo)號(hào)點(diǎn)，隊(duì)首節(jié)點(diǎn)出隊(duì)后，成為已檢查的標(biāo)點(diǎn)；path--存儲(chǔ)當(dāng)前已標(biāo)號(hào)可改進(jìn)路

5、經(jīng)；repeat??????path置空;??????源點(diǎn)s標(biāo)號(hào)并進(jìn)入path和Q;??????whileQ非空and匯點(diǎn)t未標(biāo)號(hào)do?????????????begin????????????????????移出Q的隊(duì)首頂點(diǎn)u;????????????????????for每一條從u出發(fā)的弧(u,v)do???????????????????????????ifv未標(biāo)號(hào)and弧(u,v)的流量可改進(jìn)thenv進(jìn)入隊(duì)列Q和path;?????????????endwhile??????if匯點(diǎn)已標(biāo)號(hào)then從匯點(diǎn)出發(fā)沿著path修正可改進(jìn)路的流量;

6、until匯點(diǎn)未標(biāo)號(hào);Edmonds-Karp算法有一個(gè)很重要的性質(zhì)：當(dāng)匯點(diǎn)未標(biāo)號(hào)而導(dǎo)致算法結(jié)束的時(shí)候，那些已經(jīng)標(biāo)號(hào)的節(jié)點(diǎn)構(gòu)成集合S，未標(biāo)號(hào)的節(jié)點(diǎn)構(gòu)成集合T，割(S,T)恰好是該流網(wǎng)絡(luò)的最小割；且這樣求出的最小割(S,T)中集合S的元素?cái)?shù)目一定是最少的。尋找最大流的基本方法是Ford-Fulkerson方法，該方法有多種實(shí)現(xiàn)，其基本思想是從某個(gè)可行流F出發(fā)，找到關(guān)于這個(gè)流的一個(gè)可改進(jìn)路經(jīng)P，然后沿著P調(diào)整F，對(duì)新的可行流試圖尋找關(guān)于他的可改進(jìn)路經(jīng)，如此反復(fù)直至求得最大流?，F(xiàn)在要找最小費(fèi)用的最大流，可以證明，若F是流量為V(F)的流中費(fèi)用最小者，而P

7、是關(guān)于F的所有可改進(jìn)路中費(fèi)用最小的可改進(jìn)路，則沿著P去調(diào)整F,得到的可行流F'一定是流量為V(F')的所有可行流中的最小費(fèi)用流。這樣，當(dāng)F是最大流時(shí)候，他就是所要求的最小費(fèi)用最大流。注意到每條邊的單位流量費(fèi)用B(i,j)≥0，所以F=0必是流量為0的最小費(fèi)用流，這樣總可以從F=0出發(fā)求出最小費(fèi)用最大流。一般的，設(shè)已知F是流量V(F)的最小費(fèi)用流，余下的問(wèn)題就是如何去尋找關(guān)于F的最小費(fèi)用可改進(jìn)路。為此我們將原網(wǎng)絡(luò)中的每條弧變成兩條方向相反的?。?。前向弧，容量C和費(fèi)用B不變，流量F為0；2。后向弧，容量C為0，費(fèi)用為-B

8、，流量F為0；每一個(gè)頂點(diǎn)上設(shè)置一個(gè)參數(shù)CT，表示源點(diǎn)至該頂點(diǎn)的通路上的費(fèi)用和。如果我們得出一條關(guān)于F的最小費(fèi)用可改進(jìn)路時(shí)，