最大流（Maximum Flow）

一個菜🐔倔強的取經之路，
為了知識的嚴謹性，本文相關的定義是按照演算法導論(第三版) copy and paste，我的理解和總結會適當的添加在這些定義后面用來幫助大家理解，我認為一些重要東西都已經加粗和高光標記了，本文算是對這一塊內容的學習總結，如有錯誤歡迎大家指正，交流，

1.流網路和流（Flow networks and flows）

首先我們來看看流網路和流的定義，

流網路(Flow networks): G = ( V ， E ) G=(V，E) G=(V，E) 是一個有向圖，圖中每條邊 ( u , v ) ∈ E (u,v) \in E (u,v)∈E 有一個非負的 容量值(Capacity) c ( u , v ) ≥ 0 c(u,v) \geq 0 c(u,v)≥0，如果邊集合 E E E 包含一條邊 ( u , v ) (u,v) (u,v)，則圖中不存在反方向的邊 ( v , u ) (v,u) (v,u)，如果 ( u , v ) ? E (u,v) \notin E (u,v)∈/?E，則為方便起見，定義 c ( u , v ) = 0 c(u,v)=0 c(u,v)=0，并且在圖中不允許自回圈(self-loop)，

在流網路中，我們需要區分兩個節點: 源結點(Source) s s s 和 匯點(Sink) t t t，對于每個節點 v ∈ V v \in V v∈V，流網路都包含一條路徑 s → v → t s \rightarrow v \rightarrow t s→v→t，因此, 流網路圖是連通的，并且由于除源結點外的每個結點都至少有一條進入的邊，我們有 ∣ E ∣ ≥ ∣ V ∣ ? 1 |E| \geq |V|-1 ∣E∣≥∣V∣?1，

流(Flow): 設 G = ( V ， E ) G=(V，E) G=(V，E) 為一個流網路，其容量函式為 c c c， 設 s s s 為網路的源結點， t t t 為匯點. G G G 中的 流 是一個實值函式 f : V × V → R f: V \times V \rightarrow \mathbb {R} f:V×V→R，并且需要滿足下面兩條性質:

容量限制(Capacity constraint): 對于所有的結點 u , v ∈ V u,v \in V u,v∈V，要求 0 ≤ f ( u , v ) ≤ c ( u , v ) 0 \leq f(u,v) \leq c(u,v) 0≤f(u,v)≤c(u,v)，理解容量限制很簡單，舉個栗子，比方說電梯限載1000kg，你上去如果超重了=，=它肯定就報警不走了，所以放在流網路圖上也是一樣，這條邊上的流量值 f ( u , v ) f(u,v) f(u,v) 不可以超過這條邊的容量值 c ( u , v ) c(u,v) c(u,v)，

流量守恒(Flow conservation): 對于所有的結點 u ∈ V ? { s , t } u \in V -\{s, t\} u∈V?{s,t}，要求

∑ v ∈ V f ( v , u ) = ∑ v ∈ V f ( u , v ) \sum_{v \in V}f(v,u) = \sum_{v \in V}f(u,v) v∈V∑?f(v,u)=v∈V∑?f(u,v)
我對于流量守恒的理解就是進入一個結點的流量必須等于離開這個結點的流量，（可能有偏差，演算法導論中的解釋都提到了進出結點的速率，我也不太清楚怎么解釋，）

當 ( u , v ) ? E (u,v) \notin E (u,v)∈/?E 時，從結點 u u u 到結點 v v v 之間沒有流，因此 f ( u , v ) = 0 f(u,v)=0 f(u,v)=0，我們稱非負數值 f ( u , v ) f(u,v) f(u,v) 為從結點 u u u 到結點 v v v 的流. 一個流 f f f 的值 ∣ f ∣ |f| ∣f∣ 定義如下:

∣ f ∣ = ∑ v ∈ V f ( s , v ) ? ∑ v ∈ V f ( v , s ) |f| = \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s) ∣f∣=v∈V∑?f(s,v)?v∈V∑?f(v,s)
也就是說，流 f f f 的值是從源結點流出的總流量減去流入源節點的總流量，( ∣ f ∣ |f| ∣f∣ 表示流的值，不是絕對值或者基數值)，通常來說，一個流網路不會有任何進入源結點的邊，因此上面這個公式的求和項 ∑ v ∈ V f ( v , s ) \sum_{v \in V}f(v,s) ∑v∈V?f(v,s) 值為0，所以當我們計算流的值時，只需計算源結點流出的總流量即可，

在這里這兩個 " f " "f" "f" 可能會有點繞，其實很簡單， f ( u , v ) f(u,v) f(u,v) 是"流量" ; ∣ f ∣ |f| ∣f∣ 是"流的值"， 前者就是標記在圖的每條邊旁邊的 f ( u , v ) / c ( u , v ) f(u,v)/c(u,v) f(u,v)/c(u,v) 中的 f ( u , v ) f(u,v) f(u,v)，后者則需要前者和上面這個公式計算得到，

接下來繼續舉一個演算法導論中的栗子，


圖(a)是一個流網路 G = ( V , E ) G= (V,E) G=(V,E)，在該流網路中，Vancouver 是源結點 s s s，Winnipeg 是匯點 t t t，中間途徑多個城市，但是城市之間的運載量有限，每條邊標明的是不同城市之間的貨運容量，圖(b)是 G G G 中的一個流 f f f， f = 19 f=19 f=19 (Hint:11+8)，每條邊上的數字內容是 f ( u , v ) / c ( u , v ) f(u,v)/c(u,v) f(u,v)/c(u,v)，這里 “/” 只起到分隔作用，并無數學意義，

反平行(Antiparallel): 同樣還是這個例子，這次我們稍做一點改變，如果我們假定貨運公司要從 v 1 v_1 v1?運10個單位的貨物到 v 2 v_2 v2?，這時候會出現一個問題，邊 ( v 1 , v 2 ) (v_1,v_2) (v1?,v2?) 和 邊 ( v 2 , v 1 ) (v_2,v_1) (v2?,v1?)用時存在，我們稱這兩條邊為 反平行，那就違反了我們之前的定義，所以我們需要將這條邊轉換成等價的兩條邊，并且再新增加一個結點 v ′ v' v′，如下圖所示：


超級源結點&超級匯點: 當我們面對的最大流問題含有多個源結點和多個匯點時，我們可以將網路轉換為一個只有一個源結點和一個匯點的普通流網路，轉換方法就是加入一個 超級源結點 s s s 和 超級匯點 t t t，如下圖所示:


接下一篇演算法筆記（Chapter26）———最大流（Maximum Flow）之Ford-Fulkerson