图论 —— 网络流 —— 基本概念与建模技巧
【基本概念】
1.網(wǎng)絡流
給定一個有向圖 G=(V,E)，在這個圖中：
- 有唯一的一個源點 S（入度為 0，出發(fā)點）
- 有唯一的一個匯點 T（出度為 0，結束點）
- 圖中的每條弧（u,v）都有一非負容量 c(u,v)
此時稱圖 G 為網(wǎng)絡流圖（容量網(wǎng)絡），記為：G=(V,E,c)
簡單來說，圖就是一種管道，管道有最大通過流量的限制，圖中的邊權就是容量
2.可行流
對于一個網(wǎng)絡流圖 G=(V,E,c)，每條弧（u,v）上給定一個實數(shù) f(u,v)，滿足：0<=f(u,v)<=c(u,v)，則稱 f(u,v) 為?c(u,v) 上的流量。
若有一組流量滿足：
- 源點 S 的流出量 = 整個網(wǎng)絡的流量
- 匯點 T 的流出量 = 整個網(wǎng)絡的流量
- 中間點的總流量 = 總流出量
那么整個網(wǎng)絡的流量稱為一個可行流（流量網(wǎng)絡）。
此時要注意容量與流量的區(qū)別，即要注意 f(u,v) 的范圍：0<=f(u,v)<=c(u,v)，不會出現(xiàn)流量大于容量的情況，也不會出現(xiàn)負流量的情況。
3.最大流
最大流即在所有的可行流中，流量最大的一個流量。
要注意的是，最大流可能不止一個。
在最大流問題中，任意時刻容量 c 與流量 f 滿足三個性質：
- 容量限制：f(u,v) ≤ c(u,v)
- 斜對稱性：f(u,v) = -f(v,u)，即從 u 到 v 的流量一定是從 v 到 u 的流量的反值。
- 流量守恒：對除 S、T 外的任意結點 u，，即：u 到相鄰節(jié)點的流量之和為 0，因為流入 u 的流量和流出 u 的流量相等，u 點本身不會制造、消耗流量。
4.弧與鏈
1）弧的劃分：在容量網(wǎng)絡?G(V, E)?中, 設有一可行流?f={f(u,v)}，根據(jù)每條弧上流量的多少、流量和容量的關系，可將弧分四種類型：
- 飽和弧：f(u,v)=c(u,v)
- 非飽和弧：f(u,v)<c(u,v)
- 零流弧：f(u,v)=0
- 非零流弧：f(u,v)>0
2）鏈：在容量網(wǎng)絡中，稱頂點序列 (u,u1,u2,…,un,v) 為一條鏈，要求相鄰兩個頂點之間有一條弧，如：<u, u1>?或?<u1, u>?為容量網(wǎng)絡中一條弧。沿著 Vs 到 Vt 的一條鏈, 各弧可分為兩類：
- 前向弧：方向與鏈的正方向一致的弧，其集合記為：P+
- 后向弧：方向與鏈的正方向相反的弧，其集合記為：P-
5.殘留容量與殘留網(wǎng)絡
1）殘留容量：給定容量網(wǎng)絡?G(V, E)?及可行流 f，弧?<u,v>?上的殘留容量記為?c′(u,v) = c(u,v) – f(u,v)。
每條弧的殘留容量表示該弧上可以增加的流量，由于從頂點 u 到頂點 v 流量的減少，等效于頂點 v 到頂點 u 流量增加，因此每條弧?<u,v>?上還有一個反方向的殘留容量?c′(v,u) = -f(u,v)
簡單來說，一個容量網(wǎng)絡中還可以壓入的流量，即每條邊上的容量與流量的差稱為殘留容量。
2）殘留網(wǎng)絡：給定容量網(wǎng)絡?G(V, E)?及其上的網(wǎng)絡流 f，G 關于 f 的殘留網(wǎng)絡記為?G'(V', E')，其中 G’ 的頂點集 V’ 和 G 的頂點集 V 相同，即 V’ = V，對于 G 中的任何一條弧?<u, v>，如果?f(u,v) < c(u,v)，那么在 G’ 中有一條弧?<u,v>∈E'，其容量為?c′(u,v) = c(u,v) – f(u,v)，如果?f(u,v)>0，則在 G’ 中有一條弧?<v, u>∈E'，其容量為?c′(v,u) = f(u,v)
簡單來說，由殘留的容量以及源點匯點構成的網(wǎng)絡就是殘留網(wǎng)絡。
6.增廣路徑
在一網(wǎng)絡中，若存在從 S 到 T 的一條簡單路徑，且邊 (u,v) 的方向與該路徑方向一致，則稱 (u,v) 為正向邊，否則稱為逆向邊。
若路徑上的所有邊都滿足：
- 所有的正向邊：f(u,v) < c(u,v)
- 所有的逆向邊：f(u,v) > 0
則稱該路徑為一條增廣路徑（可增加流量）。
簡單來說，增廣路徑，就是找到一條流量不滿，未達到容量上限的一條路徑，因此所有的增廣路在一起便構成了殘留網(wǎng)絡。
7.割與凈流量
1）割：是一種點的劃分方式，對于一個網(wǎng)絡流圖 G=(V,E)，設 E' ? E，若將 E' 在 G 中刪除后，使得圖 G 不在連通，則稱 E' 是圖 G 的割。割將所有的點劃分為 S 和 T=V-S 兩部分，記作：(S,T)
2）s-t 割：如果割所劃分的兩個子集使得源點 s∈S，匯點 t∈T，則該割稱為 s-t 割，其中弧<u,v>|u∈S,v∈T?稱為割的前向弧，弧 <u,v>| u∈T,v∈S?稱為割的反向弧。
2）割的容量：所有前向弧的容量和，即起點在 S 終點在 T 中的所有邊的容量和，記作：c(S,T) = Σc(u,v) | u∈S,v∈T
3）最小割：容量網(wǎng)絡的最小割即容量最小的割。
4）凈流量：對于一個割 (S,T)，用凈流量來表示穿過割 (S,T) 的流量之和，即：|f| = f(S,T) = Σf(u,v) | u∈S,v∈T
8.層次網(wǎng)絡
層次網(wǎng)絡，就是將原圖中的點按照點到源的距離進行分層，只保留不同層之間的邊的圖。
構建層次網(wǎng)絡，簡單的說，就是求出每個點 u 的層次，u 的層次是從源點到該點的最短路徑（這個最短路是指弧的權都為 1 的情況下的最短路），若與源點不連通，層次置為 -1
要注意的是，當網(wǎng)絡流進行分層后，弧可能有三種情況：
2) 從第 i 層指向第 i 層
3) 從第 i 層指向第 j 層頂點，j<i
【常用定理】
1.網(wǎng)絡流流量與割的凈流量之間的關系：在一個容量網(wǎng)絡 G(V, E) 中，設其任意一個流為 f，關于 f?的任意一個割為 (S,T)，則有?f(S,T)=|f|，即：網(wǎng)絡流的流量等于任何割的凈流量
2.網(wǎng)絡流流量與割的容量之間的關系：在一個容量網(wǎng)絡 G(V, E) 中，設其任意一個流為 f，任意一個割為 (S, T)，則有 f(S,T) ≤ c(S,T)，即：網(wǎng)絡流的流量小于或等于任何割的容量
3.殘留網(wǎng)絡與原網(wǎng)絡的關系：設 f 是容量網(wǎng)絡 G(V, E) 的可行流，f’ 是殘留網(wǎng)絡 G’ 的可行流，則 f + f’ 仍是容量網(wǎng)絡 G 的一個可行流，其中 f + f’ 表示對應弧上的流量相加
4.最小割最大流定理：網(wǎng)絡的最大流的流量等于最小割的容量
5.增廣路定理：網(wǎng)絡達到最大流當且僅當殘留網(wǎng)絡中沒有增廣路
6.幾個等價命題：對于一個網(wǎng)絡流圖 G=(V,E)，其有源點 s 和匯點 t，那么下面三個條件是等價：
- 流 f 是圖?G 的最大流
- 殘留網(wǎng)絡 G' 中不存在增廣路
- 對于 G 的某一個割 (S,T)，有 f = C(S,T)
【模型建立與模型變換】
1.多源多匯問題
問題：源有多個，匯有多個，流可以從任意一個源流出，最終可以流向任意一個匯，總流量等于所有源流出的總流量，也等于所有匯流入的總流量。
解決：加一超級源點 S、超級匯點 T，然后從 S 向每個源引入一條有向弧，每個匯點向 T 引出一條有向弧，容量均為無窮大。
2.結點容量
問題：每個點都有一個允許通過的最大流量，稱為結點容量。
解決：將每個原始結點 u 分成 u1、u2 兩個結點（一般將編號改為：u1=u、u2=u+n），中間連一有向弧，令弧的容量等于 u 的結點容量。原先到達 u 的弧改成到達 u1，原先從 u 出發(fā)的弧改為從 u2 出發(fā)。
3.無源無匯有容量下界網(wǎng)絡的可行流
問題：無源無匯且每條弧除有容量上界 c 外，還有一個容量下界 b（原始最大流問題中的容量下界為 0，故零流即是可行流）
解決：由于無源無匯，因此所有結點都滿足? "入流=出流 " 這個平衡條件。
可以建立附加源 S 與附加匯 T，然后對弧 u->v 進行改造，即添加弧 u-T> 與弧 S->v?設容量為無窮大，并將每條下界為 b 弧拆為 3 條，再進行合并，最后求改造后的網(wǎng)絡的 S-T?最大流即可。
要注意的是，當且僅當所有附加弧滿載時，原網(wǎng)絡有可行流。
4.有容量下界網(wǎng)絡的 S-T 最大/小流
問題：容量同時有上下界，且源點 S?和匯點 T?各有一個，求 S->T 的最大流與最小流
解決：可先用 "?無源無匯有容量下界網(wǎng)絡的可行流 " 的方法求出可行流，然后用傳統(tǒng)的 S-T 增廣路算法得到最大流，然后將 T 看做源點，S 看作匯點，并令反向弧的容量等于原來的容量下界，最后再運行增廣路算法求出 T-S 最大流即為 S-T 最小流
要注意的是，若沒有下界，最小流就是零流，即原來每條弧 u->v 的反向弧容量為 0，沒有什么好求的。
5.費用與流量平方成正比的最小流
問題：容量 c 均為整數(shù)，且每條弧有一個費用系數(shù) a，表示該弧流量為 x 時費用為 ax^2，求最小費用最大流
解決：使用拆邊法，如下圖所示，將費用系數(shù)為 a 容量為 5 的邊進行拆分，拆成 5 條容量為 1 費用各異的弧
由于求的是最小費用流，如果這條弧的流量為 1，則走的肯定是 cost=1 的弧；如果流量為 2，則走的肯定是 cost=1 與 cost=3 的弧；如果流量為 3，則走的是 cost=1、cost=3、cost=5 的三條弧?？梢则炞C，無論流量是 1~5 的哪一個，左右兩個圖都是等價的，這樣問題就轉為普通的最小費用最大流問題。
要注意的是，由于有重邊，普通的鄰接矩陣無法滿足，因此要么使用鄰接表實現(xiàn)，要么將鄰接矩陣加一維，表示某兩點間的第幾條弧。
6.流量不固定的 S-T?最小費用流
問題：如果網(wǎng)絡中的費用有正有負，且流量不固定，求最小費用流。
解決：如果費用都是正的，那么顯然最小費用流就是零流。由于費用存在負值，那么最短增廣路的權值就是負的，這樣增廣后可能得到更小的費用。
最小費用類似一下凸函數(shù)，費用隨著流量增大先減小，再增大，由于三分的效率較低，因此可隨著增廣的進行，當增廣路的權值逐漸增大最后變?yōu)檎龜?shù)時，停止增廣。
【建模技巧】
網(wǎng)絡流的問題難點在于模型的建立。建立模型時，一般根據(jù)題意建立一個最直觀的模型，然后再用合并邊、合并點、拆點等思想去簡化模型，最后得出一個有效的模型。
當要求刪邊后再進行詢問最大、最小值時，問題可以轉化為求最小割
當詢問是否存在不相交路徑時，一般可采用最大流來解決，其核心是用拆點來使得每個點只能走一次，若路徑帶權，那么問題可轉化為求最小費用最大流
合并邊、合并點的常見規(guī)律有：
- 若幾個結點的流量的來源完全相同，則可以把它們合并成一個
- 若幾個結點的流量的去向完全相同，則可以把它們合并成一個
- 若從點 u 到點v有一條容量為 ∞ 的邊，并且點 v 除了點 u 以外沒有別的流量來源，則可以把這兩個結點合并成一個
?
總結
以上是生活随笔為你收集整理的图论 —— 网络流 —— 基本概念与建模技巧的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 理论基础 —— 线性表 —— 双向链表
- 下一篇： 最长高地（51Nod-2509）