一、流網(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ò)中我們可以定義一個流 f’。此時我們可以定義一個函數(shù) f↑f’，我們將其稱作流f’對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ù) f↑是圖G中的一個流，其值為。