2015年5月22日 星期五

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 的弧, 而那些弧就會是最小割集。


技術提供:Blogger.