# Max_flow_algo
:::spoiler
[TOC]
:::
## 介紹
:::success

1. Capacity constraint：從vertex(X)流向vertex(Y)的flow，不能比edge(X,Y)的capacity還大，f(X,Y)≤c(X,Y)。
若每單位時間內，水管孔徑只能容納5單位，那flow最多就是5單位。
以圖二(b)為例，在Path:S−A−C−D−T上的edge之capacity皆大於6，因此在此路徑上流入6單位的flow是可行的。
<font color="red">左邊</font>為花費/右邊為總數
:::
:::success

2. Skew symmetry：若定義「從vertex(X)指向vertex(Y)」之edge(X,Y)上，有5單位的flow，f(X,Y)=5，這就等價於，從vertex(Y)到vertex(X)之edge(Y,X)上，有−5單位的flow，f(Y,X)=−5。
與「電子流(負電荷)」與「電流(正電荷)」之概念雷同，從「左到右的電流」與「從右到左的電子流」具有等價的物理意義。
:::
:::success

3. Flow conservation：對Graph中除了source與sink以外的vertex(X)而言，所有「流進flow」之總和要等於所有「流出flow」的總和。
也就是水流不會無故增加或無故減少，可視為一種能量守恆。
以圖二(b)為例，流入vertex(A)的flow為6，流出vertex(A)的flow也是6，對vertex(C)、vertex(D)也是。
:::
## Ford-Fulkerson Algorithm
:::success

Ford-Fulkerson Algorithm需要兩個輔助工具：

- Residual Networks(剩餘網路)
- Augmenting Paths(增廣路徑)
:::
### Residual Networks(剩餘網路)
:::success

Residual Networks的概念為，記錄Graph上之edge還有多少「剩餘的容量」可以讓flow流過。
:::
:::info

以圖三(a)為例，若在Path:S−A−C−D−T上的所有edge都有6單位的flow流過，那麼這些edge(edge(S,A)、edge(A,C)、edge(C,D)、edge(D,T))的可用「剩餘capacity」，都應該要「減6」，例如，edge(S,A)只能「再容納9−6=3單位」的flow，edge(C,D)只能「再容納7−6=1單位」的flow。
:::
:::info

這些「**剩餘capacity**」就稱為residual capacity，以c~f~表示。
若edge(X,Y)上有flow流過，f(X,Y)，便將edge(X,Y)上的residual capacity定義為：

c~f~(X,Y)=c(X,Y)−f(X,Y)
c(X,Y)為原來水管孔徑大小；
f(X,Y)表示目前水管已經有多少流量；
c~f~(X,Y)表示水管還能再容納多少流量。
:::
:::warning

因為**Skew symmetry**，f(C,A)=−f(A,C)；
再根據定義，c~f~(C,A)=c(C,A)−f(C,A)=c(C,A)+f(A,C)=0+6=6
==如果想要重新配置水流方向來形容會很好(回來的方向)==
:::

### Augmenting Paths(增廣路徑)
:::success

在Residual Networks裡，所有能夠「從source走到termination」的路徑，也就是所有能夠「增加flow的path」，就稱為Augmenting Paths。
:::
:::danger
他不會超過 residual flow
:::

### 演算法概念
:::success

Ford-Fulkerson Algorithm(若使用BFS搜尋路徑，又稱為Edmonds-Karp Algorithm的方法如下：
:::
:::info

在**Residual Networks**上尋找**Augmenting Paths**。
1. 若以BFS()尋找，便能確保每次找到的Augmenting Paths一定經過「最少的edge」。
2. 找到Augmenting Paths上的「最小residual capacity」加入總flow。
3. 再以「最小residual capacity」更新Residual Networks上的edge之residual capacity。
4. 重複上述步驟，直到再也沒有**Augmenting Paths**為止。
5. 便能找到**Maximum Flow**。
:::

以圖二(a)之Flow Networks作為範例，尋找Maximum Flow之步驟如下：

先以「flow為零」對residual networks進行初始化，如圖五(a)。
觀察後發現，Gf就是Adjacency Matrix。
:::success
利用「已經求取完最大流量」的 Residual network 可得到「原本流量網路」的 Minimum cut

Minimum cut：有 (S,T) 兩個子圖，滿足
- S ∪ T = V 且 S ∩ T = ϕ
從子圖 S 連至子圖 T 之所有邊的權重和為所有「Cut」中最小
在求完最大流量的「**Residual network**」中，令

- S：｛自 S 可以到達的節點｝
- T：｛自 T 可以到達的節點｝
則 (S, T) 是原本「Flow network」的「**Minimum cut**」
:::