图论 —— 网络流 —— 基本概念与建模技巧
【基本概念】
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)