流網(wǎng)絡(luò)
流網(wǎng)絡(luò)G（V琅关，E）是一個有向圖粪牲，每條邊有一個非負(fù)的容量值c，且每條邊沒有重邊（反向邊）帽揪。如果兩個節(jié)點沒有邊帮寻，為了方便我們設(shè)置其流量值為0
在流網(wǎng)絡(luò)的所有節(jié)點中弥鹦，我們特別地有兩個節(jié)點：源節(jié)點s和匯點t向抢。我們假定每個節(jié)點都在s和t之間迄本，從而形成一個流
對于流網(wǎng)絡(luò)硕淑，我們有兩個性質(zhì)：
1.容量守恒：對于所有節(jié)點間，兩點流量小于等于其間容量
2.流量守恒：流進(jìn)一個節(jié)點的流量等于流出這個節(jié)點的流量嘉赎。
邊上的數(shù)值：分子表示流置媳，分母表示容量
問題描述
在最大流問題中，給定一個流網(wǎng)絡(luò)G公条、一個源節(jié)點s拇囊、一個匯點t，希望找到一個值最大的一個流
Ford-Fulkerson方法
這個方法依賴于三種重要思想：殘存網(wǎng)絡(luò)靶橱，增廣路徑寥袭，切割
殘存網(wǎng)絡(luò)
對節(jié)點u、v关霸，定義殘存容量為
殘存網(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ā)出的流運(yùn)輸回發(fā)送地苍日，并將權(quán)重為0的邊省略惭聂。
殘存網(wǎng)絡(luò)是如何增大原始流網(wǎng)絡(luò)中的流的一種指示
如果f是G的一個流，對應(yīng)的有一個殘存網(wǎng)絡(luò)相恃，殘存網(wǎng)絡(luò)中我們可以定義一個流 f ’
又定義一個函數(shù)辜纲，為流f’對流f的增量（或遞增），它是一個VxV到R的函數(shù)
增廣路徑
給定流網(wǎng)絡(luò)G和流f，增廣路徑p是殘存網(wǎng)絡(luò)中一條從源結(jié)點s到匯點t的簡單路徑
我們稱在一條增廣路徑p上能夠為每條邊增加的流量的最大值為路徑p的殘存容量耕腾。表示為cf（p）
引理 設(shè)G為一個流網(wǎng)絡(luò)见剩，設(shè)f為圖G中的一個流，設(shè)p為殘存網(wǎng)絡(luò)中的一條增廣路徑扫俺。定義一個函數(shù)如下：
fp為殘存網(wǎng)絡(luò)的一個流苍苞，其值大于0
有了增廣路徑，使得我們找到的流更接近于最大流
切割
Ford算法核心就是沿著增廣路徑重復(fù)增加路徑上的流量狼纬，直到找到一個最大流為止羹呵。但我們怎么知道找到了呢？
定理：一個流是最大流當(dāng)且僅當(dāng)其殘存網(wǎng)絡(luò)不包含任何增廣路徑
切割：一個切割（S疗琉，T）將圖G（V冈欢，E）的節(jié)點集合V劃分為S和T=V-S兩個集合，使得節(jié)點s屬于S盈简，t屬于T凑耻。
若f為一個流，則定義橫向切割（S送火，T）的凈流量f（S拳话，T）如下：
切割（S，T）的容量是：
一個網(wǎng)絡(luò)的最小切割是整個網(wǎng)絡(luò)中容量最小的切割种吸。
如對于這個流網(wǎng)絡(luò)：
該切割凈流量：
該切割的容量：（只看從s到t方向的容量）
引理 設(shè)f為流網(wǎng)絡(luò)G的一個流弃衍，該流網(wǎng)絡(luò)的源結(jié)點為s，匯點為t坚俗，設(shè)（S镜盯，T）為流網(wǎng)絡(luò)G的任意切割，則橫跨切割（S猖败，T）的凈流量為f（S速缆，T）= ｜f｜。
推論 流網(wǎng)絡(luò)G中任意流f的值不能超過G的任意切割的容量恩闻。
最大流最小切割定理
設(shè)f為流網(wǎng)絡(luò)G=（V艺糜，E）中的一個流，該流網(wǎng)絡(luò)的源結(jié)點為s幢尚，匯點為t破停，則下面的條件是等價的：
- f是G的一個最大流。
- 殘存網(wǎng)絡(luò)不包含任何增廣路徑
- |f|=c（S尉剩，T）真慢，其中（S，T）是流網(wǎng)絡(luò)G的某個切割理茎。
因為一個流不可能大于一個切割容量黑界，當(dāng)一個切割容量最小時管嬉，其值就為最大流的大小
基本的Ford算法
在Ford-Fulkerrson方法的每次迭代中，尋找某條增廣路徑p朗鸠，然后使用p來對流f進(jìn)行修改（增加）蚯撩。找到一條增廣路徑后有對應(yīng)的fp，將其添加到f中烛占，知直到找不到一條增廣路徑p為止求厕。
偽代碼
1-2行：初始化流
3-8行：在殘存網(wǎng)絡(luò)中尋找一條增廣路徑p，然后使用殘存容量cf（p）來對流f加增扰楼。
因為路徑p上每條殘存邊要么是原來網(wǎng)絡(luò)中一條邊，要么是原來網(wǎng)絡(luò)中一條反向邊美浦。
故6-8行：如果殘存邊為原來一條邊弦赖，加增流量；為反向邊浦辨，減流量蹬竖。
當(dāng)沒有增廣路徑p時，流f就是最大流
算法運(yùn)行時間取決于尋找增廣路徑的時間流酬，當(dāng)我們使用基于廣度優(yōu)先搜索的算法時币厕，此時稱Ford算法為Edmonds-Karp算法，算法時間復(fù)雜度為O（V*E^2）
示例
