《算法導(dǎo)論》最大流學(xué)習(xí)筆記

一、流網(wǎng)絡(luò)

G=（V，E）是一個有向圖，其中每條邊（u，v）有一個非負的容量值c（u，v），而且如果E中包含一條邊（u，v），那么圖中就不存在它的反向邊。在流網(wǎng)絡(luò)中有兩個特殊的結(jié)點，源結(jié)點s和匯點t。

下面給出流網(wǎng)絡(luò)的形式化定義。令G=（V，E）為一個流網(wǎng)絡(luò)，其容量函數(shù)為c，設(shè)s我為網(wǎng)絡(luò)的源點，t為匯點。G中的流是一個實值函數(shù)f，滿足以下兩條性質(zhì)：

1. 容量限制（capacity contraint）：對于所有的結(jié)點u，v，要求

2. 流量守恒（flow conservation）：對于所有的非源點和匯點的結(jié)點u，要求：

下圖是一個流網(wǎng)絡(luò)的示例圖，幫助大家理解，其中的“/”只是分隔符而不是運算符，“/”前代表的是流的值，后面的數(shù)值則是該條邊的容量（capacity）：

流網(wǎng)絡(luò)常見的一種應(yīng)用場景是運輸問題，需要將貨物從s運輸?shù)絫，途經(jīng)幾個中轉(zhuǎn)站，每次運輸?shù)矫總€中轉(zhuǎn)站的貨物的數(shù)量是有限制的。在實際應(yīng)用中我們可能會在某條邊上雙向運輸，這樣便違反了我們之前對流網(wǎng)絡(luò)的定義，但是我們可以將包含反平行邊的圖來改造成流網(wǎng)絡(luò)，具體的方法是引入一個是虛構(gòu)的中轉(zhuǎn)結(jié)點，方法如下圖。

考慮另外一種特殊情形，從多個工廠發(fā)出貨物最終運輸?shù)絼e的多個工廠，這時候我們具有了多個源點和多個匯點，這也很好解決，解決的方法就是人為添加超級源點（supersource）和超級匯點（supersink），具體方法見下圖。

二、Ford-Fulkerson方法

將實際問題轉(zhuǎn)化成流網(wǎng)絡(luò)后，我們就可以來解決最大流問題了。理解這個方法需要先理解幾個關(guān)于流網(wǎng)絡(luò)的基礎(chǔ)概念。

1. 殘存網(wǎng)絡(luò)（residual network）

假定有一個流網(wǎng)絡(luò)G=（V，E），其源點為s，匯點為t，f為G中的一個流。對即誒點對u，v，定義殘存容量（residual capacity），有：

殘存網(wǎng)絡(luò)可能包含圖G中不存在的邊，殘存網(wǎng)絡(luò)中的反向邊允許算法將已經(jīng)發(fā)送出來的流量發(fā)送回去。一個殘存網(wǎng)絡(luò)示例圖如下：

圖a是一個流網(wǎng)絡(luò)，b是a對應(yīng)的殘存網(wǎng)絡(luò)，注意每條邊上的值，殘存網(wǎng)絡(luò)中針對每條正向邊計算出該條邊在存在流的情況下的剩余容量，并畫出一條反向邊，反向邊的容量即是發(fā)出流的大小，方便將發(fā)出的流運輸回發(fā)送地，并將權(quán)重為0的邊省略。

殘存網(wǎng)絡(luò)是如何增大原始流網(wǎng)絡(luò)中的流的一種指示。如果f是G的一個流，對應(yīng)的有一個殘存網(wǎng)絡(luò)，殘存網(wǎng)絡(luò)中我們可以定義一個流。此時我們可以定義一個函數(shù)，我們將其稱作流對f的增量（augmentation）。

2. 增廣路徑（augmenting paths）

給定流網(wǎng)絡(luò)G和流f，增廣路徑p是殘存網(wǎng)絡(luò)中一條從源結(jié)點s到匯點t的簡單路徑。根據(jù)殘存網(wǎng)絡(luò)的定義，對于一條增廣路徑上的邊（u，v），我們可以增加其流量的幅度最大為，即我們之前定義的殘存容量（residual capacity）。我們將這里討論的情形總結(jié)成一條引理：

引理 設(shè)G為一個流網(wǎng)絡(luò)，設(shè)f為圖G中的一個流，設(shè)p為殘存網(wǎng)絡(luò)中的一條增廣路徑。定義一個函數(shù)如下：

其中是殘存網(wǎng)絡(luò)中的一個流，其值。

推論?設(shè)G為一個流網(wǎng)絡(luò)，設(shè)f為G中的一個流，設(shè)p為殘存網(wǎng)絡(luò)中的一條增廣路徑。設(shè)如上述引理所定義，假定將f增加的量，則函數(shù)是圖G中的一個流，其值為。

3. 流網(wǎng)絡(luò)的切割（cuts of networks）

流網(wǎng)絡(luò)G中的一個切割（S，T）將結(jié)點集合V劃分為S和T=V-S兩個集合，使得、。若f是一個流，則定義橫跨切割（S，T）的凈流量f（S，T）如下：

切割（S，T）的容量是：

一個網(wǎng)絡(luò)的最小切割是整個網(wǎng)絡(luò)中容量最小的切割。

舉例說明切割的計算方法：

橫跨該切割的凈流量：

該切割的容量：

引理?設(shè)f為流網(wǎng)絡(luò)G的一個流，該流網(wǎng)絡(luò)的源結(jié)點為s，匯點為t，設(shè)（S，T）為流網(wǎng)絡(luò)G的任意切割，則橫跨切割（S，T）的凈流量為。

推論 流網(wǎng)絡(luò)G中任意流f的值不能超過G的任意切割的容量。

定理（最大流最小切割定理） 設(shè)f為流網(wǎng)絡(luò)G=（V，E）中的一個流，該流網(wǎng)絡(luò)的源結(jié)點為s，匯點為t，則下面的條件是等價的：

1. f是G的一個最大流。

2. 殘存網(wǎng)絡(luò)不包含任何增廣路徑

3. |f|=c（S，T），其中（S，T）是流網(wǎng)絡(luò)G的某個切割。

4. 基本的Ford-Fulkerson算法

在Ford-Fulkerrson方法的每次迭代中，尋找某條增廣路徑p，然后使用p來對流f進行修改（增加）。我們不斷地在圖中尋找增廣路徑，并依據(jù)來增大f的值，直到圖中不含增廣路徑。偽代碼實現(xiàn)如下：

Ford-Fulkerson算法的運行時間取決與尋找增廣路徑的方法，這也是Edmonds-Karps算法對基礎(chǔ)Ford-Fulkerson算法做改進的理論基礎(chǔ)。

我們在殘存網(wǎng)絡(luò)中選擇的增廣路徑是一條從源結(jié)點s到匯點t的最短路徑，其中每條邊的權(quán)重為單位距離，我們稱如此實現(xiàn)的Ford-Fulkerson算法為Edmonds-Karp算法。

?

?

?

?

總結(jié)

以上是生活随笔為你收集整理的最大流（Maximum Flow）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。