2015年5月22日 星期五

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

1 Comment
 

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

一道網絡流是一個對於所有結點uv都有以下特性的實數函數f:V×VR
  • 容量限制(Capacity Constraints): f(u,v)c(u,v),所有流量不大於容量。
  • 流量守恆(Flow Conservation):除非u=su=t,否則 wVf(u,w)=0
    • i. 對所有的非源點或匯點的點,流入的流量和等於流出的流量和
    • ii. 源點流出的總流量等於流進匯點的總流量
  • 斜對稱(Skew Symmetry):f(u,v)=f(v,u),由u到v的淨流必須是由v到u的淨流的相反。




剩餘容量 (Residual Capacity)
每條邊上定義一個非負數 Cf(u,v)=C(u,v)F(u,v) 為該邊的剩餘容量,而剩餘容量的集合則稱為剩餘網路(Residual Network),Gf(V,Ef)

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





增廣路 (Augmenting Path)
一條路徑(u1,u2,,uk),而u1=suk=tcf(ui,ui+1)>0,也就是說,可以在這條增廣路徑上的每一條邊上加一流量 d,使整個流仍然是可行的流並使網路的總流量增加 d。




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

AA 的最小的子集(邊的集合),使得 G 中去掉 A 後成為兩個不相交的子圖 G1(S,A1)G2(S,A2),分別以 S,S 為頂點集,則稱 A 是關於 (S,S) 的割集,記為 A=(S,S),而 A 裡的總容量則稱為割的容量。

AG 所能產生的割集中容量和最小的,則稱 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.