最大流最小割定理

最大流最小割定理是最優化理論的定理。根據該定理，在一個網路流中，從源點到匯點的最大的流量，等於它的最小割中每一條邊的容量之和。「割」指的是一種邊的集合，如果移除這個集合的全部邊，就會斷開源點和匯點的連接。

最大流最小割定理是線性規劃中的對偶問題的一種特殊情況，並且可以用來推導門格爾定理和König–Egerváry定理。

## 定義

最大流和最小割定理是圖論的一部分，因此為了準確定義，我們需要先定義圖、流、割，然後再定義這個定理。

### 圖

設 $G=(V,E)$ 為一個有向圖，其中有一個起源點 $s$ 和一個超匯點 $t$，代表 $s$ 是所有流的源頭，$t$ 是所有流的終點。這個圖的每一條邊都有一個容量 c : E → R+，記做 $c_{uv}$ 或者 $c(u,v)$，代表著能通過邊 $(u,v)$ 的最大流量。

### 最大流

定義：流量代表一種映射 $f:E \rightarrow \mathbb{R}^+$，記做$f_{uv}$ 或者 $f(u,v)$，代表通過邊 $(u,v)$ 的流量。每一條邊所通過的流有以下兩個限定條件：

- 流量限制：$f_{uv} \le c_{uv} \quad \forall\, (u,v)\in E.$ 也就是說，一條邊上的流量不可以超過它的容量。
- 流量守恆：$\sum\nolimits_{\{ u : (u,v)\in E\}} f_{uv} = \sum\nolimits_{\{w : (v,w)\in E\}} f_{vw} \quad \forall\, v \in V\setminus\{s,t\}.$ 也就是說，除了源點和匯點以外，進入一個節點的流量等於流出這個節點的流量，節點內不能保存流。

規定在一個圖中，流的值是

$$|f| = \sum\nolimits_{v:(s,v) \in E} f_{sv} = \sum\nolimits_{v:(v,t) \in E} f_{vt}.$$

也就是說，一個圖的流是自其源點流出的流量之和，也是向其匯點流入的流量之和。或者說，由源點向匯點移動多少內容，這個圖的流就是多少。

最大流問題：計算$|f|$的最大值，即從$s$到$t$的最大流量。

### 最小割

定義： s-t割 $C=(S,T)$ 將圖 $G$ 完全劃分為兩部分，使得 $s \in S, t \in T,$ 也就是一側有源，一側有匯。$C$ 的割集 $X_C$ 是 $\{ (u, v) \in E \ : \ u \in S, v \in T \}.$ 也就是說，一條邊若且唯若騎在這個劃分方法上，一個節點位於劃分出來的源側，另一個位於匯側，那麼它包含在 $X_C$ 里。因此如果 $C$ 的割集是空集，或者我們把一個割集裡的邊全都從圖中拿走，則 $|f| = 0$。通俗地說，割集就是一個圖的斷面，而割則是劃分斷面的方法。

規定在一個圖中，s-t割的容量是

$c (S,T) = \sum\nolimits_{(u,v) \in X_C} c_{uv} = \sum\nolimits_{(i,j) \in E } c_{ij}d_{ij},$ 其中當 $i \in S,j \in T$ 時，$d_{ij}$ 為 $1$, 否則為 $0$。

通俗地說，割的容量就是斷面中所有邊的總容量。

最小 s-t 割問題：計算 $c(S,T)$ 的最小值。即找到一種割法，使割的容量最小。也就是說，找到通過能力最弱的斷面。

### 主定理

可以證明一切流都不能超過任何s-t割，所以經過圖的最大流就是圖的最小割。我們直觀上就可以知道，通過能力最弱的斷面就是整個網路的最大流量。這個理論把最大流問題和最小割問題聯繫了起來。

## 線性規劃公式

最大流最小割問題可以被看做為一對線性規劃對偶問題。

最大流（原問題）｜最小割（對偶問題）

變量｜$f_{uv}$ $\forall (u,v)\in E$ 每條邊一個變量｜$d_{uv}$ $\forall (u,v)\in E$ 每條邊一個變量 $z_{v}$ $\forall v\in V\setminus \{s,t\}$ 每個非源點、非匯點一個變量

目標函數｜最大化 $\sum\nolimits_{v: (s,v)\in E} f_{sv}$ 最大化從源點流出的總流量｜最小化 $\sum\nolimits_{(u,v) \in E } c_{uv}d_{uv}$ 最小化割中邊的總容量

約束條件｜滿足： :$\begin{align} f_{uv} & \leq c_{uv} && \forall (u, v) \in E \\ \sum_{u} f_{uv} - \sum_{w} f_{vw} & = 0 && v \in V\setminus \{s,t\} \end{align}$ 每條邊一個約束，每個非源點、非匯點一個約束｜滿足： :$\begin{align} d_{uv} - z_u + z_v & \geq 0 && \forall (u, v) \in E, u\neq s, v\neq t \\ d_{sv} + z_v & \geq 1 && \forall (s, v) \in E, v\neq t \\ d_{ut} - z_u & \geq 0 && \forall (u, t) \in E,u\neq s \\ d_{st} & \geq 1 && \text{若 } (s, t) \in E \end{align}$ 每條邊一個約束

符號約束｜$\begin{align} f_{uv} & \geq 0 && \forall (u, v) \in E\\ \end{align}$｜$\begin{align} d_{uv} & \geq 0 && \forall (u, v) \in E \\ z_v & \in \R && \forall v \in V\setminus \{s,t\} \end{align}$

最大流的線性規劃公式是容易理解的，對於最小割的線性規劃公式的理解如下：

$$d_{uv} = \begin{cases} 1, & u \in S , v \in T \\ 0, & \text{Otherwise} \end{cases}$$

$$z_{u} = \begin{cases} 1, & u \in S \\ 0, & \text{Otherwise} \end{cases}$$

最小化目標是使在割中的邊最小。

下列限制保證了這些變量可以確保一個合法的割。

- 限制 $d_{uv} - z_u + z_v \geq 0$(即 $d_{uv} \geq z_u - z_v$) 確保了對兩個非源點或匯點 u,v, 如果u 在 S中 且 v 在 T中, 那麼邊 (u,v)一定會被記在割中 ($d_{uv} \geq 1$)。
- 限制 $d_{sv} + z_v \geq 1$(即 $d_{sv} \geq 1 - z_v$) 確保了如果 v 在 T 中, 那麼邊 (s,v) 一定會被記在割中。
- 限制 $d_{ut} - z_u \geq 0$(即 $d_{ut} \geq z_u$) 確保了 u 在 S 中, 那麼邊 (u,t) 一定會被記在割中。

需要注意的是，這是一個最小化問題，我們不需要確保一條邊不在割里，我們只要保證每條應當在割里的邊被計算了。

注意到在給定的 s-t 割 $C = (S,T)$ 中，如果 $i \in S$ 那麼 $z_i = 1$ 並且 0 反之。所以 $z_s$ 應該等於 1 並且 $z_t$ 應該等於0。由線性規劃中的強對偶定理推得最大流最小割問題中的等式，也就是說如果原問題有一個最優解 x*，則對應問題也有一個最優解 y*，並且兩個解相等。

## 舉例

<image>

上圖是一個網路，上有流量為 7 的流。令 S 集合和 T 集合分別包含所有白色和灰色的點，從而形成了一個割集包含圖中虛線的 s-t 割，並且其容量為 7，與流量相同。故由大流最小割定理知，前述的流與 s-t 割皆達到流量及容量的極值。

## 應用

### 廣義最大流最小割定理

額外規定映射 $c \colon V \rightarrow R^+$為點的容量，記做 c(v)，使得一個流 f 不只要滿足邊的流量限制與流量守恆，還要滿足點的流量限制，即

$$\forall v \in V \setminus \{s,t\} : \qquad \sum\nolimits_{\{u\in V\mid (u,v)\in E\}} f_{uv} \le c(v).$$

換句話說，流過 v 點的總流量不能超過 v 的容量 c(v)。一個 s-t 割 的定義為一個包含一些點和邊的集合，滿足與任一條由 s 到 t 的路徑皆不互斥。並且 s-t 割的容量 定義成所有點和邊的容量總和。

在此定義之下，廣義最大流最小割定理的敘仍為流量的最大值等於所有 s-t 割的容量最小值。

### 門格爾定理

不共邊路徑問題為給定無向圖 $G=(V,E)$ 及兩頂點 s、t，求從 s 到 t 彼此沒有共同邊的路徑數量的最大值。

門格爾定理的敘述為從 s 到 t 彼此沒有共同邊的路徑數量的最大值等於在所有 G 的 s-t 割(以原本的定義)中，頂點分別在不同集合的邊數的最小值。

### 計畫選擇問題

<image>

計畫選擇問題敘述如下：當下有 n 個計畫 $p_1, \dots ,p_n$可以被實施、m 種設備 $q_1, \dots ,q_m$ 可以被購買，要執行計畫必須擁有該計畫要求的設備，執行計畫 $p_i$可獲得 $r(p_i)$ 的收益，但購買設備 $q_j$ 要支付 $c(q_j)$ 的費用。如何選擇執行計畫並購買所需設備以獲得淨利的最大值？

設 P 為不被執行的計畫的集合，Q 為所購買的設備，則問題變成求最大值

$$\max_{P,Q} \sum_{i=1}^n r(p_i) - \sum_{p_i \in P} r(p_i) - \sum_{q_j \in Q} c(q_j)$$

注意到 $\sum_{i} r(p_i)$與 P、Q 的選擇無關，故只需求後兩項和的最小值，即

$$\min_{P,Q} \sum_{p_i \in P} r(p_i) + \sum_{q_j \in Q} c(q_j)$$

現在考慮一個網路，起源點 s 連接到 n 個點 $p_1, \dots ,p_n$，邊的容量分別為 $r(p_i)$，超匯點 t 連接到 m 個點 $q_1, \dots ,q_m$，邊的容量分別為 $c(q_j)$，若執行任務 $p_i$需購買設備 $q_j$，則在 $p_i$、$q_j$ 之間連上一條容量為無限大的邊，若不需購買設備，則不連上邊。則 $\sum_{p_i \in P} r(p_i) + \sum_{q_j \in Q} c(q_j)$ 對應到一個 s-t 割的容量，其中的兩個集合是要執行的計畫與要購買的設備和它的餘集，也就是

$$\{s\}\cup (P'\setminus P) \cup Q \text{、 } \{t\}\cup P \cup (Q'\setminus Q)$$

在此，$P'=\{p_1, \dots ,p_n\}$，$Q'=\{q_1, \dots ,q_m\}$。於是，原問題轉成求該圖的最大流問題，並且可以藉由各種演算法求得其極值。

以下給出一個計畫選擇問題的例子，右圖是該問題對應到的網路。

計畫收入 r(pi)｜設備價格 c(qj)｜備註

1｜100｜200｜執行計畫 p1 須購買設備 q1、q2。

2｜200｜100｜執行計畫 p2 須購買設備 q2。

3｜150｜50｜執行計畫 p3 須購買設備 q3。

該網路的最小 s-t 割是選擇計畫 p2、p3 與設備 q2、q3，容量為 250。三個計劃的總收益是 450，因此最大淨利為 450 − 250 = 200。

以上解法可以理解為將計畫所給予的收益流過所需設備，如果無法流滿設備至 t 的邊，代表執行計畫不合成本，最小割將選擇穿過 s 到計畫的邊而非穿過設備到 t 的邊。

### 影像分割問題

<image>

設原圖有 n 像素，想要把該圖分割為前景和背景，並且將 i 像素歸類為前景有效益 fi，歸類為背景有效益 bi，但是若 i、j 像素相鄰且被歸類為不同塊，則會減少 pij 的效益。求將該圖分割為前後景的最有效益方法。

令 P 為前景的集合，Q 為背景的集合，於是問題轉化成求最大值

$$\max_{P,Q} \sum_{i \in P} f_i + \sum_{i \in Q} b_i - \sum_{i \in P,j \in Q \lor j \in P,i \in Q } p_{ij}$$

因為 fi、 bi 的總合是與 P、Q的選取無關，因此等價於求以下最小值

$$\min_{P,Q} \sum_{i \in Q} f_i + \sum_{i \in P} b_i + \sum_{i \in P,j \in Q \lor j \in P,i \in Q } p_{ij}$$

以上的最小值問題可以被描述為一個網路的最小割問題，其中該網路如右圖，以橘點為起源點；紫點為超匯點。各個像素被描述為網路的頂點，起源點至第 i 個像素連上一條容量為 fi 的有向邊；第 i 個像素至超匯點連上一條容量為 bi 的有向邊。相鄰的像素 i、j 之間連上來回兩條容量為 pij 的有向邊。則一個 s-t 割代表一種將部分像素歸類為前景 P、其餘歸類為背景 Q 的安排。

## 歷史

最大流最小割問題最早在1956年被P. Elias, A. Feinstein，和 C.E. Shannon 證明P. Elias, A. Feinstein, and C. E. Shannon, A note on the maximum flow through a network, IRE. Transactions on Information Theory, 2, 4 (1956), 117–119，並且L.R. Ford, Jr. 和 D.R. Fulkerson 也在同年證明了該定理。

## 證明

同之前的設定，G = (V, E) 是一個網路(有向圖)，s 點和 t 點分別為 G 的起源點和超匯點。

將所有流考慮成一個歐式空間的有界閉子集，滿足流量限制與流量守恆，而流量是一個連續函數，因此有極大值 |f|。

設 f 達到最大流，令 (Gf ) 是 f 的殘留網路，定義

- A：在 (Gf ) 中可以從 s 出發到達的點
- Ac：A 以外的點，即 V − A

換句話說，v∈A 若且唯若 s 可以流出更多流量到 v。

我們宣稱 $|f|=c(A,A^c)$，其中該 s-t 割的容量定義為

$c (S,T) = \sum\nolimits_{(u,v) \in (S \times T) \cap E} c_{uv}$.

由於 $|f|$ 的大小等於所有流出集合 A 的流量總和減所有流入集合 A 的流量總和，故 $|f| \leq c(A,A^c)$，並且等號成立若且唯若

- 所有從 A 流向 Ac 的邊流量均已達飽和。
- 所有從 Ac 流向 A 的邊流量均為 0。

我們用反證法分別證明以上兩點：

- 假設存在從 A 流向 Ac 的邊 $(x,y) \in A \times A^c$ 並未達到飽和，即 $f(x,y)<c_{xy}$。因此，可以從 x 流更多的流量到 y，(x,y) 是 Gf 的一條邊。由 x∈A 知 Gf 圖中有一條中的路徑從 s 到 x，其中只經過 A 中的點，所以 y∈A，產生矛盾。是故所有從 A 流向 Ac 的邊流量均已達飽和。
- 假設存在從 Ac 流向 A 的邊 $(y,x) \in A^c \times A$ 其流量不為 0，即 $f(x,y)>0$。因此，可以從 y 流更少的流量到 x，(x,y) 是 Gf 的一條邊。由 x∈A 知 Gf 圖中有一條中的路徑從 s 到 x，其中只經過 A 中的點，所以 y∈A，產生矛盾。是故所有從 Ac 流向 A 的邊流量均為 0。

於是，聲稱得證。

由於流量恆不超過容量，|f| 是容量的下界，所以 $c(A,A^c)$ 是容量的最小值，由聲稱知，最大流最小割定理得證。