# 網路流 (Network Flow)

## 介紹
  Flow network 是一種特殊的有向圖 (如果是無向也會拆成雙向)，這個圖的邊上有一個 capacity 跟 flow。你可以把這個邊想像成是水管，水管會一個最大的流量上限，也就是 capacity；和他實際流過的量，也就是 flow。實際還可以被對比到很多應用，像是交通運輸量、通訊傳輸流量、電壓傳輸等等，這個問題最早就是俄羅斯的學者提出來要處理鐵路規劃的問題。Flow network 是一門很深的學問，單獨介紹這種問題便可以出一本教科書。他常被用來解決資源分配的問題，可以說只要有一個資源分配的問題出現，大家就一定會先使用 flow network 來求解看看。
  具體來說，一個最簡單的 flow network 的簡單定義如下：
* 每條邊 $e$ 都有一個大於等於 0 的 capacity $c_e$。
* 在所有節點中會有一個節點稱為 source，是產生 flow 的源頭；有一個節點稱為 sink，是接收 flow 的終點；其餘節點則稱為 internal node。


  flow network 在處理時有一個動作叫做 undo flow，這個動作是指在某個情況下，假設 a 節點至 b 節點有大於 0 以上的 flow，那這時候 b 節點至 a 節點就存在反流的可能，若之後發生反流，則我們稱這個情況為 undo flow。具體情況如下，假設我們在找剛剛那個範例的最大流，最大流意思是從 source 至 sink 可以產生的最大流量。我們第一步先找某條從 source 至 sink 的 path，假設找到 s->a->b->t，也就是下面左圖的情況，這條路的 bottleneck 是 2，也就是最大可以流經的流量，所以目前的最大流是 2。此時 a->s、b->a、t->d 各有一條可能的反流，反流流量剛剛找到的路的流量，所以是 2。接著我們找第二條路徑，s->b->a->t，請注意，反流也可以拿來找路徑使用，此時 a->b 就稱為 undo flow，如下面右圖所示。其實換個角度來看，你也可以想成 s->a 流經 2 個流量，而這 2 個流量 1 個從 a->t 流出，另一個從 a->b 流出，a->b 的再與 s->b 的匯合變成 2 個流量，從 b->t，這樣想就完全沒有什麼反流或 undo flow。不過這樣只能用來思考，因為數學家們提出的演算法必須要藉由 undo flow 來實現。


## Maximum Flow Problem
  接著，我們就來講在一個給定的 flow network 下該如何求解最大流。但在講之前，我們在對 flow 做一些更精確的定義:
* flow 一定是大於等於 0 的實數。
* 我們用 $f(e)$ 來代表邊 $e$ 的 flow。
* 我們用 $v(f)=\sum_{\text{e out of s}}f(e)$ 來代表目前的 flow
* flow 的性質:
* Capacity conditions:必定大於等於 0 且小於等於 capacity。
* Conservation conditions: Internal node 的流入量一定等於流出量。

  在 flow network 中，我們的目的通常是找到最大流。但在開始找之前，我們想先看看可不可以找到最大流的 upper bound。其實很簡單，我們只要在圖中切一刀，將圖一分為二，且這刀可以使 source 跟 sink 分離，那我們看從 source 那邊流向 sink 那邊的總流量便是某個 upper bound。但這個 upper bound 如果要緊一點，我們就希望找到切下去的那刀可以是使分割的流量是最小的。等等我們會證明，如果我們找出切下去那刀是使分割流量最小的那刀，那個最小流量便是最大流。


### 解法
  這個問題被 Ford-Fulkerson 求解出來，是的，就是 Bellman-Ford Algorithm 的 Ford。解法流程是這樣的:
1. 先將 flow netowrk 複製重畫一次，其中邊改成 $0/c_e$
2. 畫出複製的 flow network 的 residual graph，在 residual graph 產生的 flow 又被稱為 Augmenting path
3. 從 residual graph 隨意找出一條 s->t 的 path，以這條路的 bottleneck 為流量。
4. 更新複製的 flow network 的邊 $f(e)/c_e$
* 若 residual graph 找出的 path 的某邊 $e$ 跟 flow network 的邊 $e$ 同向，則更新 flow network 的邊 $f(e)=f(e)+bottleneck$
* 若 residual graph 找出的 path 的某邊 $e$ 跟 flow network 的邊 $e$ 反向，則更新 flow network 的邊 $f(e)=f(e)-bottleneck$
6. 重複 2~4 步直到無法再找出路徑

其中 residual graph $G_f$ 是根據一個 flow network $G$ 的 flow 產生的圖，其產生方式為:
1. $G_f$ 所有的節點與原圖 $G$ 相同，即 $V(G_f)=V(G)$
2. $G_f$ 的邊為:
* 只要 $G$ 的某邊 $f(e)<c_e$，則產生一條同向的邊 $c'_e=c_e-f(e)$
* 只要 $G$ 的某邊 $0<f(e)$，則產生一條反向的邊 $c''_e=f(e)$

舉例：
<div style="text-align: center;"><img src="https://hackmd.io/_uploads/Sksl64btWg.png, "style="display: block; margin: 0 auto; width: 40%;"></div>
### 完整範例流程如下：
第1步: 最初複製的 flow netowrk
第2、3步: 畫出 residual graph 並找出路徑
第4步: 更新 flow netowrk
第2、3步: 畫出 residual graph 並找出路徑
第4步: 更新 flow netowrk
第2、3步: 畫出 residual graph 並找出路徑
第4步: 更新 flow netowrk
第2、3步: 畫出 residual graph 並找出路徑
第4步: 更新 flow netowrk
第2、3步: 畫出 residual graph 並找出路徑
第4步: 更新 flow netowrk

Ford-Fulkerson Algorithm 做到最後我們可以發現，當 source 無路可走時，從他可以抵達的最遠端那裡開始切，便就是我們要找的最小 upper bound。

詳細演算法如下：
<div style="text-align: center;"><img src="https://hackmd.io/_uploads/HJg1bt-Y-g.png, "style="display: block; margin: 0 auto; width: 80%;"></div>

## Bipartite Matching
&emsp;&emsp;這次我們考慮一個不一樣的配對問題，同樣有一群男生跟一群女生，他們有各自可以接受的幾個女生跟幾個男生，這邊不管喜好程度，我們希望的是配對最多對男女，且一人不能同時對到多人。如下圖所示，$X$ 是男生節點，$Y$ 是女生節點，$X$ 中的節點跟 $Y$ 中的節點有邊代表這對男女互相可以接受。我們目標就是要找出最多的邊
<div style="text-align: center;"><img src="https://hackmd.io/_uploads/rJep6dbtZl.png, "style="display: block; margin: 0 auto; width: 25%;"></div>

### 解法
&emsp;&emsp;這個問題其實有特定的演算法可以求解，但這邊我們使用 Ford-Fulkerson algorithm 求解。這邊使用了一個我覺得很酷的技巧，讓配對問題變成 flow network 問題，大家可以學起來。這個技巧對原本的圖做了以下幾件事：
1. 將所有邊變成從 $X$ 中的節點到 $Y$ 中的節點的有向邊
2. 在 $X$ 前面加入 source 節點，在 $Y$ 後面加入 sink 節點。
3. source 會各連一條有向邊到所有 $X$ 的節點，所有 $Y$ 的節點會連一條有向邊到 sink。
4. 將所有邊的 capacity 設成 1，這樣確保了每個人僅會有一個配偶。如果有兩個配偶，在流進或流出必定會超過 capacity。
接著我們就可以使用 Ford-Fulkerson algorithm 求解這個問題了
<div style="text-align: center;"><img src="https://hackmd.io/_uploads/H1GogFZF-e.png, "style="display: block; margin: 0 auto; width: 45%;"></div>
## Network Flow 後續分析
&emsp;&emsp;接著我們對 Network Flow 跟 Ford-Fulkerson algorithm 進行一些後續的分析。

### Ford-Fulkerson algorithm 的正確性
&emsp;&emsp;首先，我們想證明「使用 Ford-Fulkerson algorithm 找出來的新 flow $f'$ 是一個 flow」。前面我們講過一個 flow 要滿足 capacity 和 conservation conditions ，因此我們要證明這兩件事，證明如下：

### Integer Capacity
&emsp;&emsp;考慮一個 flow network，如果要使用 Ford-Fulkerson algorithm 找最大流，所有邊的 capacities 一定都要是整數。如果不是，一定要先進行正規化，讓所有邊的 capacities 都變成整數再繼續做。同理，如果所有邊的 capacity 都是整數，那 residual graph 裡所有邊的 capacities 也都會是整數，因為他們只是對原來的邊進行加法或減法。

### Ford-Fulkerson algorithm 的遞增性
&emsp;&emsp;使用 Ford-Fulkerson algorithm 時，每找到新的一個流，總流量一定會變大。證明如下：

### Running Time
&emsp;&emsp;令 $C$ 為從 source 離開的邊的 capacities 的總和，則 Ford-Fulkerson algorithm 最多只會執行 $C$ 個迴圈，因為每次一定可以增加一個流量，那「從 source 離開的邊的 flow 的總和」一定會小於「從 source 離開的邊的 capacities 的總和」，因此最多就是做 $C$ 次迴圈讓 flow 增加至 $C$。
&emsp;&emsp;每個迴圈的執行時間是 $O(m)$，其中 $m$ 為邊的數量，因此總時間複雜度是 $O(Cm)$，這同樣是一個 pseudo polynomial，因為 $C$ 可能會很大。

### Choosing Good Augmenting Paths
&emsp;&emsp;如果 $C$ 很大，有時候找到錯的路徑會花很久的時間。如下圖，如果找的路徑一直經過中間，那會需要找總共 200 次才結束。但如果不找中間的路徑，那 2 次就結束了。
<div style="text-align: center;"><img src="https://hackmd.io/_uploads/Hyfg9YbFbg.png, "style="display: block; margin: 0 auto; width: 90%;"></div>

因此，這邊給出幾個找路徑的建議：
1. 找 bottleneck capacity 最大的那個路徑
2. 找經過最少 edge 的路徑
3. 給定一個閥值，先找 bottleneck capacity 大於此閥值的那幾個路徑

## Max-Flow Min-Cut Theorem
&emsp;&emsp;「最大流其實會等於我們用一刀切法找到的最小 upper bound」，這是我們上面有提到的一個觀察，但其實這是一個定理。這個定理的證明會用下面三個性質來證明，用第 2 個證明第 3 個，用第 1 個證明第 2 個，用第 3 個證明第一個：



用第 1 個證明第 2 個之前，我們先證明這個定理




## 參考
[交大電機工程學系江蕙如老師演算法課程 OCW](https://ocw.nycu.edu.tw/?course_page=all-course%2Fcollege-of-electrical-and-computer-engineering%2F%E6%BC%94%E7%AE%97%E6%B3%95-algorithms-%E9%9B%BB%E6%A9%9F%E5%B7%A5%E7%A8%8B%E5%AD%B8%E7%B3%BB-%E6%B1%9F%E8%95%99%E5%A6%82%E8%80%81%E5%B8%AB)