_最大流算法及其應(yīng)用

《_最大流算法及其應(yīng)用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、最大流算法及其應(yīng)用最大流算法及其應(yīng)用南京外國語學(xué)校賈志鵬【關(guān)鍵詞】網(wǎng)絡(luò)流、最大流問題、最小割問題【摘要】本文介紹了一種特殊的圖——流網(wǎng)絡(luò)及其相關(guān)問題，主要介紹的是最大流問題和最小割問題，并提出了解決方案。最后介紹了一些網(wǎng)絡(luò)流相關(guān)的建模問題?！灸夸洝恳?、網(wǎng)絡(luò)流相關(guān)的一些概念（1）流網(wǎng)絡(luò)（2）流（3）割（4）殘留網(wǎng)絡(luò)（5）增廣路徑（6）增廣二、最大流和最小割問題（1）最大流問題（2）最小割問題（3）最大流算法三、最大流算法的應(yīng)用（1）最大流模型（2）最小割模型四、總結(jié)第1頁共13頁最大流算法及其應(yīng)用一、網(wǎng)絡(luò)流相關(guān)的一些概念1.流網(wǎng)絡(luò)(FlowNetwork)流網(wǎng)絡(luò)G?(,)

2、VE是一個有向圖，其中每條邊(,)uv?E均有一非負容量cuv(,)0?。如果(,)uv?E，則假定cuv(,)0?。流網(wǎng)絡(luò)中有兩個特別的頂點：源點s和匯點t。213234st12546圖1一個流網(wǎng)絡(luò)的例子（邊上的數(shù)字表示該弧的容量）2.流(Flow)G的流是一個實值函數(shù)f，fuv(,)表示頂點u到頂點v的流，它可以為正，為零，也可以為負，且滿足下列三個性質(zhì)：容量限制：對所有uvV,?，要求fuv(,)?cuv(,)。反對稱性：對所有uvV,?，要求fuv(,)??fvu(,)。流守恒性：對所有uV??{,}st，要求?fuv(,)?0。vV?整個流網(wǎng)絡(luò)G的流量f??f

3、sv(,)或f??fut(,)。vV?uV?3.割(Cut)流網(wǎng)絡(luò)G?(,)VE的割(,)ST將V劃分成S和T??VS兩部分，使得sS?，tT?。定義割(,)ST的容量為cST(,)，則：第2頁共13頁最大流算法及其應(yīng)用cST(,)??cuv(,)uSvT??,213234st12546圖2一個割的例子（邊上的數(shù)字表示該弧的容量，割的容量即為2+2+1+6=11）4.殘留網(wǎng)絡(luò)(ResidualNetwork)給定一個流網(wǎng)絡(luò)G?(,)VE和流f，由f壓得的G的殘留網(wǎng)絡(luò)G?(,VE)，ff定義cuv(,)為殘留網(wǎng)絡(luò)G中邊(,)uv的容量。如果弧(,)uv?E或弧(,)vu?

4、E，則ff弧(,)uv?E，且cuv(,)??cuv(,)fuv(,)。在下面的各種概念和方法中，我們只ff考慮殘留網(wǎng)絡(luò)中容量大于0的弧，但是編程時為了方便還是保留了。5.增廣路徑(AugmentingPath)對于殘留網(wǎng)絡(luò)G中的一條s-t路徑p稱其為增廣路徑，定義增廣路徑p的殘f留容量為p上弧容量的最小值。后面求最大流要用到增廣路徑這個概念。6.增廣(Augment)對于殘留網(wǎng)絡(luò)G中的一條增廣路徑p，增廣的意思就是對于每一條屬于pf的弧(,)uv，將fuv(,)增加p的殘留容量，將fvu(,)減少p的殘留容量。這樣的話，新的流f仍然滿足流的三條性質(zhì)，并且原流網(wǎng)絡(luò)的流量

5、f增加了。一般來說，增廣過后就會修改殘留網(wǎng)絡(luò)，易得對于每一條屬于p的弧(,)uv，要將cuv(,)f第3頁共13頁最大流算法及其應(yīng)用減去p的殘留容量，cvu(,)加上p的殘留容量。（程序?qū)崿F(xiàn)基本都是通過直接修f改殘留網(wǎng)絡(luò)來實現(xiàn)增廣的）二、最大流和最小割問題1.最大流問題對于一個流網(wǎng)絡(luò)G?(,)VE，其流量f的最大值稱為最大流，最大流問題就是求一個流網(wǎng)絡(luò)的最大流。增廣路定理：當且僅當由當前的流f壓得的殘留網(wǎng)絡(luò)G中不存在增廣路徑f時，流f的流量f達到最大。（證明在此略去，可以參見相關(guān)書籍）根據(jù)增廣路定理，我們可以設(shè)計出最基本的求最大流的方法，一開始將流網(wǎng)絡(luò)G?(,)VE的流

6、f置為零流，即對于(,)uv?E時，fuv(,)0?。然后構(gòu)建殘留網(wǎng)絡(luò)，尋找增廣路徑增廣，再修改殘留網(wǎng)絡(luò)，重復(fù)此過程，直到無法找到增廣路徑。此方法（之所以不是算法，是因為實現(xiàn)方法很多）稱為Ford-Fulkerson方法。偽代碼如下：FORD-FULKERSON-METHORD(G,s,t)1initializeflowfto02whilethereexistsanaugmentingpathp3doaugmentflowfalongp4returnf2.最小割問題最小割是指流網(wǎng)絡(luò)中容量最小的割。Ford-Fulkerson定理（最小割最大流定理）：在流網(wǎng)絡(luò)中，最小割的

7、容量等于最大流的流量。（證明也在此略去）根據(jù)這個定理，我們就可以通過求流網(wǎng)絡(luò)的最大流來得到最小割。3.最大流算法前面所講的只是求最大流的一種方法，但怎樣高效地實現(xiàn)還是一個問題。這個方法的最大問題就在于怎樣快速地找到一條增廣路徑。當然我們可以用最基本的搜索（DFS或BFS），但是這種方法肯定不夠高效，這時我們就需要更高效的算法。本文將重點介紹一種高效且實用的最大流算法：SAP算法（最短增廣路算法）。最短增廣路算法(ShortestAugmentingPathAlgorithm)，即每次尋找包VE含弧的個數(shù)最少的增廣路進行增廣，可以證明，此算