Algorithm - Ch5 網路流 與 最大流最小割定理 Network Flow and Maximum Flow Minimum Cut Theorem

Chapter 5  網路流 Network Flow

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) \in E$都有一個非負值實數的容量$c(u, v)$。如果$(u, v) \not \in E$，我們假設$c(u, v) = 0$。我們區別兩個頂點：一個源點$s$和一個匯點$t$。

一道網絡流是一個對於所有結點$u$和$v$都有以下特性的實數函數$f:V \times V \rightarrow \mathbb{R}：$

• 容量限制(Capacity Constraints)：$\ f(u, v) \le c(u, v)$，所有流量不大於容量。
• 流量守恆(Flow Conservation)：除非$u = s$或$u = t$，否則$\ \sum_{w \in V} f(u, w) = 0$
• i. 對所有的非源點或匯點的點，流入的流量和等於流出的流量和
• ii. 源點流出的總流量等於流進匯點的總流量
• 斜對稱(Skew Symmetry)：$f(u, v) = - f(v,u)$，由u到v的淨流必須是由v到u的淨流的相反。

剩餘容量 (Residual Capacity)
每條邊上定義一個非負數 $C_f(u, v) = C(u, v) – F(u, v)$ 為該邊的剩餘容量，而剩餘容量的集合則稱為剩餘網路(Residual Network)，$G_f(V, E_f)$。

*注意：就算在原網絡中由u到v沒有邊，在剩餘網絡仍可能有由u到v的邊。因為相反方向的流抵消，減少由v到u的流等於增加由u到v的流，看下圖例子便可理解。

增廣路 (Augmenting Path)
一條路徑$(u_1, u_2, \dots, u_k)$，而$u_1 = s$、$u_k = t$及$c_f(u_i, u_{i+1}) > 0$，也就是說，可以在這條增廣路徑上的每一條邊上加一流量 d，使整個流仍然是可行的流並使網路的總流量增加 d。

割 (Cut)
割集(Cut set)，設流量網路 $G = ( V , A )$ 的頂點集 $V$ 是兩不交的部分 $S, S’$ 的聯集，使源點在 $S$ 中，匯點在 $S’$中。

若 $A’$ 是 $A$ 的最小的子集(邊的集合)，使得 $G$ 中去掉 $A’$ 後成為兩個不相交的子圖 $G_1(S,A_1)$ 與 $G_2(S’,A_2)$，分別以 $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 的弧, 而那些弧就會是最小割集。