# 最大流量-最小割定理 Max-flow Min-cut Theorem
這篇筆記會藉由 Ford-Fulkerson 演算法來聊聊最大流量-最小割定理。記得當初在修演算法課時聽老師說這是一個偉大的發現，我是覺得這定理真的很猛但沒那麼誇張啦。在介紹 Ford-Fulkerson 演算法之前，需要先介紹流量網路 (network flow)，一些性質與引理也順便聊聊

流量網路圖有許多不同的應用，像是現實中可以把水管當作邊，水管交界處用節點，這樣就可以表示成一張流量網路的圖。其他像是公路、電路跟網路傳輸等等都可以用網路流量的圖來建模。如果要說比較抽象的問題，像是二分圖最大匹配問題、二分圖最大點覆蓋問題、最小邊割問題等等都可以用流量網路來轉換

## 流量網路 Network Flow
<!-- West -->

### 網路圖 Network
一張路網圖 $N$ 是一張有向圖，其中 :
- 存在一個源點 (source vertex) $s$
- 存在一個與原點不同的匯點 (sink vertex) $t$
- 每條邊 $e$ 都有非負的容量 (capacity) $cap(e) \geq 0$
- 每條邊 $e$ 都有一個流量 (flow) $f(e)$

註 : 對於每個節點 $v$，可以把流入 $v$ 的流量寫作 $f^+(v)$，流出 $v$ 的流量寫作 $f^-(v)$

### 流量的限制
- 若邊 $e$ 的 flow 符合 $0\leq f(e)\leq cap(e)$，則稱此 flow 是可行的 (feasible)
- 對於每個 $v\notin\{s,t\}$，流量會守恆，$f^+(v)=f^-(v)$，即流入等於流出

### 最大流量 Maximum Network Flow
首先定義 flow $f$ 的值 $val(f)$ (或寫作 $|f|$) 為流入 $t$ 的總流量 $f^+(t)-f^-(t)$。最大流量 (maximum flow) 就是最大的 $val(f)$

註 : 有些書會定義 $val(f)$ 為流出 $s$ 的總流量，但其實種是等價的 (只是數值會為相反數)，以下會證明。我認為用流入 $t$ 的定義會比較直觀

### 流量網路圖的割 Cuts
割的定義與[這篇 Menger 定理](https://hackmd.io/@ShanC/Menger-Theorem)相同，只差多重邊的數量要轉為權重

在流量網路需特別定義割 $[A, B]$ 的容量為 :
$$
cap(A, B)=\begin{split}\sum_{e~out~of~A}cap(e) \end{split}
$$

## 剩餘網路圖 Residual Graph
<!-- Cormen 交叉比對-->
由於證明會用到剩餘網路圖，所以這裡先來定義一下
### 剩餘邊 Residual Edge
設有向邊 $e=(u, v)$。定義 $e^R=(v, u)$，就是 $N$ 中把方向倒轉過來的邊。每條邊 $e$ 有剩餘容量 (residual capacity) :

$c_f(e)=\begin{cases}
cap(e)-f(e) ~~~\text{if}~ e\in E\\
f(e) ~~~~~~~~~~~~~~~~~~~\text{if}~ e^R\in E
\end{cases}$

註 : 這邊說 $e^R$ 倒過來的邊是指，相對於路徑 $s\rightarrow t$ 倒過來的邊

### 剩餘網路圖 Residual Graph
- 邊集合 $E_f=\{e~|~f(e) < cap(e)\} ~\cup~ \{e^R~|~f(e) > 0\}$
- 剩餘圖 $G_f=(V, E_f)$
- 一條增廣路徑 (augmenting path) 是一條 $G_f$ 上的 $s, t$ 路徑，可以寫作 $f$-augmenting path
- 容忍度 (tolerance) 是一條增廣路徑 $P$ 上的最小 $c_f(e)$，即 $min_{e\in E(P)} ~c_f(e)$

註 : West 的書裡只定義了增廣路徑，而 Cormen 的書定義了整張剩餘圖，兩者所使用的剩餘邊定義相同

## 最大流量-最小割定理 Max-flow Min-cut Theorem
以下一連串的引理與證明，都有一些目的
- 引理 1 : 用來處理演算法
- 引理 2 : 把守恆性拓展到割
- 引理 3 : 把割與 flow 兩種觀念結合起來
- 引理 4 : 說明割的 flow 也須遵守的條件

然後增廣路徑定理就很莫名其妙地出現在課本跟講義上，也很奇妙的證明完
最大流量-最小割定理的證明手法也是很玄，到底怎麼想到的啊

### 引理 1
<!-- West -->
若 $P$ 為一條 $f$-augmenting path 且 tolerance 為 $min_{e\in E(P)} ~c_f(e)=z$，則將 $P$ 對應到流量網路圖中順向邊的 flow 加上 $z$，逆向的減去 $z$。如此一來會產生一個全新的 flow $f'$，其值為 $val(f')=val(f)+z$

#### 證明
- feasible : 根據 tolerance 的定義，可以保證每條 $e$ 的 flow $0\leq f'(e)\leq cap(e)$
- 守恆性 : 只需要確認 $P$ 上的 flow 就好，因為其他並沒有被影響到。對於一個 $P$ 上的任意中間節點而言，可以分成四種狀況 (如下圖)。可以發現，每種狀況對於「流入等於流出」這項規定並沒有影響

<img src="https://hackmd.io/_uploads/ryNFyPc1gx.png" style="margin: 0 auto; display: block; width: 600px">

$~$
綜合上述兩點，從 $P$ 流入 $t$ 的總流量會加上 $z$。得證 $val(f')=val(f)+z$

### 引理 2 : 淨流入等於淨流出
若 $U$ 是 $N$ 的節點集合，則流出 $U$ 的淨流量會等於每個點流出的流量加總，即 $\begin{split}f^+(U)-f^-(U)=\sum_{v\in U}\left( f^+(v)-f^-(v)\right)\end{split}$

#### 證明
考慮一條邊 $xy$ 的 flow
- 若 $x, y\in U$，則會貢獻在等式右邊，但是都被守恆性抵銷掉了
- 若 $x, y\notin U$，則對於等式沒有貢獻
- 若 $xy\in [U, \bar{U}]$，則對於等式兩邊貢獻皆為正且相同
- 若 $yx\in [U, \bar{U}]$，則對於等式兩邊貢獻皆為負且相同

因此等式成立

### 引理 3 : Flow Value Lemma
<!-- Cormen -->
若 $f$ 是 feasible 且集合 $[S, T]$ 是一個 $s, t$-割 (整張圖切分為 $S, T$，$s\in S, t\in T$)，則 $f^-(S)-f^+(S)=val(f)$

#### 證明
考慮 $f^-(S)=f^+(T)$ 與 $f^+(S)=f^-(T)$，由以下等式可以證明此引理

$\begin{split}
f^-(s) - f^+(s)&=\sum_{v\in S}~\left( f^-(v) - f^+(v)\right)
\\&=f^-(S)-f^+(S)
\\&=f^+(T)-f^-(T)
\\&=\sum_{v\in T}~\left( f^+(v) - f^-(v)\right)
\\&=f^+(t)-f^-(t)
\\&=val(f)
\end{split}$

這也順便證明了流出源點 $s$ 的淨流量等於流入匯點 $t$ 的淨流量

### 引理 4 : Weak Duality
<!-- Cormen -->
設 flow $f$ 是 feasible 且 $[S, T]$ 是一個 $s, t$-割，則 $val(f)\leq cap(S, T)$

#### 證明
$\begin{split}val(f)=f^-(S)-f^+(S)\leq f^-(S)\leq\sum_{e ~out~of~A}cap(e)=cap(S, T)\end{split}$

### 增廣路徑定理 Augmenting path Theorem
一個 flow 是最大流量若且唯若不存在任何增廣路徑

#### 證明
下面跟最大流量-最小割定理一起證

### 最大流量-最小割定理 Max-flow Min-cut Theorem
<!-- Cormen -->
一張流量網路圖的最大流量會等於最小割容量

#### 證明
可以把增廣路徑定理跟最大流量-最小割定理拆分成以下三句話，並證明三者彼此等價 :
(1) 存在一個割 $[A, B]$ 使得 $val(f)=cap(A, B)$
(2) $f$ 是最大流量
(3) 不存在相對於 $f$ 的增廣路徑

- (1)$\Rightarrow$(2) : 根據引理 weak duality 得證
- (2)$\Rightarrow$(3) : 使用反證法，假設 $f$ 是 $N$ 的最大流量且 $G_f$ 中存在一條增廣路徑 $P$。在存在 $P$ 代表可以找到最小 tolerance $z$，使 $val(f')=val(f)+z$ 為新的流量且 $val(f')>val(f)$，這與假設「$f$ 是最大流量」相矛盾。
- (3)$\Rightarrow$(1) : 設 $f$ 為沒有增廣路徑的 flow，$s\in A$ 且 $t\notin A$，可以推出等式如下
$\begin{split}
val(f)&=f^-(A)-f^+(A)
\\&=\sum_{~e~out~of~A}f(e)-\sum_{~e~in~to~A}f(e)
\\&=\sum_{e~out~of~A}cap(e)
\\&=cap(A, B)
\end{split}$

證畢

## 舉些例子
### 例 1
這個例子中，紅線表示割，可以算出流量 $val(f)=10+3+11=24$，容量 $cap(S, T)=10+5+15=30$

<img src="https://hackmd.io/_uploads/Bkzh-hikxe.png" style="margin: 0 auto; display: block; width: 600px">

### 例 2
這個例子中，紅線表示割，可以算出流量 $val(f)=6+0+8-1+11=24$，容量 $cap(S, T)=9+15+8+30=62$

<img src="https://hackmd.io/_uploads/BymAW2jJex.png" style="margin: 0 auto; display: block; width: 600px">

### 例 3
這個例子中，紅線表示割，可以算出流量 $val(f)=10-4+8-0+10=24$，容量 $cap(S, T)=10+8+10=28$

<img src="https://hackmd.io/_uploads/HyCPMhjkel.png" style="margin: 0 auto; display: block; width:550px">

### 例 4
這個例子中，與上圖的流量不同，紅線表示割，可以算出流量 $val(f)=10-0+8-0+10=28$，容量 $cap(S, T)=10+8+10=28$。因 $val(f)=cap(S, T)$，所以這就是最大流量與最小割

<img src="https://hackmd.io/_uploads/Hyl_XX3skeg.png" style="margin: 0 auto; display: block; width:550px">

## Ford-Fulkerson 演算法
### 演算法
<!-- West 交叉比對-->
- 輸入 : 圖 $N$、源點 $s$、匯點 $t$
- 輸出 : flow $f$
- 想法 : 每次只要能找到一條增廣路徑 $P$，就代表還可以找到更大的 flow，所以就執行引理 1 所描述的方法。如此迭代，直到沒有 $P$ 存在，就回傳 flow $f$。根據最大流-最小割定理，此時的 $f$ 就是最大流量

### Pseudocode
<!-- Cormen -->

FordFulkerson(N, s, t)
    let Gf as the residual graph and cf be the residual capacity
    for each e in N.E
        f(e) = 0
    while there exists a path P from s to t in Gf
        cf(P) = min{cf(e) | e is in P}
        for each e in P
            let eR be the reversed edge
            if e in N.E
                then f(e) = f(e) + cf(P)
            else f(eR) = f(eR) - cf(P)
    return f

### 時間複雜度分析
- 初始化 : $O(E)$
- 每找一次擴充路徑，都是花一次遍歷整張圖的時間 : $O(V+E)$
- 若容量介於 $1$ 到 $F$，在最差情況下，所有擴充路徑容量都是 $1$，共找到 $F$ 條，則 $F$ 為最大流量，因此時間為 $O((V+E)\times F)$
- 總時間複雜度簡寫為 $O(EF)$

由於任何數值在電腦的編碼方式中，皆以二進制存取，因此可以將 $F$ 看作是 $2^k$
$\Rightarrow$ **Ford-Fulkerson 演算法實際上的時間複雜度可以看成是指數時間 (exponential running time)**

### 為什麼流量一定要是有理數
Ford 跟 Fulkerson 有在論文中提出一個 $10$ 節點的圖當作例子，但之後也有人提出更簡單的例子來說明為何容量不能是無理數。以下使用 [Zwick 的例子](https://www.sciencedirect.com/science/article/pii/030439759500022O)

此圖的 $r=\cfrac{\sqrt{5}-1}{2}$，其餘沒有標的邊都是 $M\geq 4$

<img src="https://hackmd.io/_uploads/HJUr6Wikge.png" style="margin: 0 auto; display: block; width: 300px">

$~$
在這個例子中，永遠找的到一條增廣路徑，所以演算法會陷入無限迴圈

## 整數流 Integral Flows
### Integrality Theorem
若所有容量都是整數，則存在一個最大流量 $f$ 使每條邊的流量 $f(e)$ 都是整數

### 證明
整數在加法與減法會閉合，因此當所有容量都是整數，不會形成非整數的流量

## ShanC 的讀書心得與後記

本篇參考的書籍有三本，關於最大流量-最小割定理的證明方法也各有千秋。其中證明最詳細且難懂的是 Cormen 最經典的演算法那本 "Introduction to Algorithms" 第 24 章，D.B.West 的圖論第 4 章比較像是 Cormen 那本寫的簡略版，而 Diestel 的圖論第 6 章是用完全不同的方法證明。但有一點我覺得很讚的是 West 有說為什麼流量一定要是有理數而不是連無理數都可以

在應用方面，Cormen 本沒有多加著墨，只舉了一個二分圖匹配問題轉成網路最大流量的例子，感覺他那本單純只是把演算法的部分講清楚而已。而 West 本把相關定理講的非常完備，他那本的重點就是要把圖論中的 dual problems 都講完並且可以互相轉換，有點討厭的是他把一些重要的知識 left as exercises......。Diestel 重點在將網路流量圖當成是一種圖的結構，把一些相關的知識點都講一講，而最大流問題只是其中一個。~~整章甚至連 plannar graph, abelian group 都出現了~~ 🤮，重點不與上述兩本完全不同，我也還沒讀完，沒很清楚他想做什麼

總之，這篇筆記整理了書上、網路上與我的修課筆記，簡單來說就是一篇縫合怪，但作為競程的重要知識點已經很足夠了 (~~甚至是太多了~~)。希望大家看完這篇後可以多想想看 flow 可以做啥，在[下一篇](https://hackmd.io/@ShanC/bipartite-and-flow)會講要怎麼轉化最大流和最小割變成其他問題或是定理，然後[下下一篇](https://hackmd.io/@ShanC/Edmonds-Karp-and-Dinic)會講講更快的演算法

----

## 參考資料

- D.B.West - Introduction to Graph Theory 2/e
- Introduction to Algorithms, Fourth Edition
- Reinhard Diestel - Graph Theory
- [The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate](https://www.sciencedirect.com/science/article/pii/030439759500022O)
- [台師大演算法筆記 - flow](https://web.ntnu.edu.tw/~algo/Flow.html)
- [Howard Wang - 圖形理論](https://hackmd.io/@HowWang/rkts6dUMo#Ch4-Connectivity-and-Paths)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/4/29