5.1 網路流 Network Flow
網絡流 (Network Flow) 是指在一個每條邊都有容量 (Capacity) 的有向圖分配流,使一條邊的流量不會超過它的容量。邊有附帶容量的圖稱為網絡。一道流必須符合一個結點的進出的流量相同的限制,除非這是一個源點或是一個匯點。一個網絡可以用來模擬道路系統的交通量、管中的液體、電路中的電流或類似一些東西在一個結點的網絡中遊動的任何事物。
- 網路(Network):圖 G=(V,A) 為一邊有附帶容量的有向圖,稱為網路。
- 源點與匯點(Source and Sink):令一點 S 為源點、一點 T 為匯點,其餘點則為中間點。
- 容量(Capacity):每條邊上定義一個非負數 c(u,v) 為該邊的容量。
- 流量(Flow):每條邊上定義一個非負數 f(u,v) 為流量,所有流量的集合則稱為網路的一個流。下面是一個流網路範例。
網路流正式定義
假設G(V,E)是一個有限的有向圖,它的每條邊(u,v)∈E都有一個非負值實數的容量c(u,v)。如果(u,v)∉E,我們假設c(u,v)=0。我們區別兩個頂點:一個源點s和一個匯點t。
一道網絡流是一個對於所有結點u和v都有以下特性的實數函數f:V×V→R:
- 容量限制(Capacity Constraints): f(u,v)≤c(u,v),所有流量不大於容量。
- 流量守恆(Flow Conservation):除非u=s或u=t,否則 ∑w∈Vf(u,w)=0
- i. 對所有的非源點或匯點的點,流入的流量和等於流出的流量和
- ii. 源點流出的總流量等於流進匯點的總流量
- 斜對稱(Skew Symmetry):f(u,v)=−f(v,u),由u到v的淨流必須是由v到u的淨流的相反。
每條邊上定義一個非負數 Cf(u,v)=C(u,v)–F(u,v) 為該邊的剩餘容量,而剩餘容量的集合則稱為剩餘網路(Residual Network),Gf(V,Ef)。
*注意:就算在原網絡中由u到v沒有邊,在剩餘網絡仍可能有由u到v的邊。因為相反方向的流抵消,減少由v到u的流等於增加由u到v的流,看下圖例子便可理解。
一條路徑(u1,u2,…,uk),而u1=s、uk=t及cf(ui,ui+1)>0,也就是說,可以在這條增廣路徑上的每一條邊上加一流量 d,使整個流仍然是可行的流並使網路的總流量增加 d。
割 (Cut)
割集(Cut set),設流量網路 G=(V,A) 的頂點集 V 是兩不交的部分 S,S′ 的聯集,使源點在 S 中,匯點在 S′中。
割集(Cut set),設流量網路 G=(V,A) 的頂點集 V 是兩不交的部分 S,S′ 的聯集,使源點在 S 中,匯點在 S′中。
若 A′ 是 A 的最小的子集(邊的集合),使得 G 中去掉 A′ 後成為兩個不相交的子圖 G1(S,A1) 與 G2(S′,A2),分別以 S,S′ 為頂點集,則稱 A′ 是關於 (S,S′) 的割集,記為 A′=(S,S′),而 A′ 裡的總容量則稱為割的容量。
若 A′為 G 所能產生的割集中容量和最小的,則稱 A′ 為最小割(Minimum Cut)。
5.2 Maximum Flow problem
- Maximum Flow problem
- 給定一個流量網路 G = ( V , A ),並指定源點、匯點,要求求出此網路的最大流量為何。
- Ford-Fulkerson method
- 利用殘餘網路的概念每次隨意找一條增廣路徑, 修正殘餘網路(亦須對後向弧作更正),並增加路徑中 最小的容量作為增加流量,直到找不到增廣路徑為止, 而先前累積的流量則為最大流量,複雜度為 O(Ef),f 為網路的最大流。
- Edmonds-Karps algorithm
- 同 Ford-Fulkerson 方法,原理相同,但在每次找增廣路徑時以廣度優先搜尋(BFS)尋找,效率較高。
- 以點來看,每找一次增廣路徑並修正後,就等於消除一條在殘餘網路的最短路徑(假設一條弧的距 離為 1),而修正之後的後向弧也不會縮短最短路徑的長度。
- 以弧來看,一條弧成為增廣路徑一部分的次數一定會低於 V/2,所以一個網路最多只有 O(VE)條增 廣路徑,加上 BFS 找增廣路徑的效率為 O(E),所以的複雜度為 O(V + E) = O(E),複雜度為 O(VE^2)。
5.3 Maximum Flow Minimum Cut Theorem
- Maximum Flow Minimum Cut Theorem
- 在一個流量網路 G 中,以下三個條件為等價條件 :
- 1. 有一流 f 為 G 的最大流
- 2. G 的殘餘網路沒有增廣路徑
- 3. 存在一割 C,其容量為流量 f
- 假設割集中連接分屬兩點集的 u,v,我們可以確定 Cf(u, v) = 0(否則會產生一條增廣路徑使得 v 在所 屬的集合中),又因為 Cf(u, v) = C(u, v) - F (u, v),得到 C(u, v) = F (u, v),又因為定理中 1,3,所以推得 C 為最小割 。
- 最小割集的求法
- 由於最大流等於最小割,因此最小割的弧一定是飽和弧,在剩餘網路的容量則為 0。所以我們可以從源點開始沿著剩餘網路的前向弧搜索,直到找到每條路徑的第一條容量為 0 的弧, 而那些弧就會是最小割集。