最大流最小割定理

最大流最小割定理是最优化理论的定理。根据该定理，在一个网络流中，从源点到汇点的最大的流量，等于它的最小割中每一条边的容量之和。“割”指的是一种边的集合，如果移除这个集合的全部边，就会断开源点和汇点的连接。

最大流最小割定理是线性规划中的对偶问题的一种特殊情况，并且可以用来推导门格尔定理和König–Egerváry定理。

定义

最大流和最小割定理是图论的一部分，因此为了准确定义，我们需要先定义图、流、割，然后再定义这个定理。

图

设 $G=(V,E)$ 为一个有向图，其中有一個起源点 $s$ 和一個超匯点 $t$，代表 $s$ 是所有流的源頭，$t$ 是所有流的終點。这个图的每一条边都有一个容量 Template:Math，记做 $c_{uv}$ 或者 $c(u,v)$，代表着能通过边 $(u,v)$ 的最大流量。

最大流

定义： 流量代表一种映射 $f:E\to {ℝ}^{+}$，记做$f_{uv}$ 或者 $f(u,v)$，代表通过边 $(u,v)$ 的流量。每一条边所通过的流有以下两个限定条件：

1. 流量限制：$f_{uv}\le c_{uv}\mathrm{\forall }(u,v)\in E.$ 也就是说，一条边上的流量不可以超过它的容量。
2. 流量守恒：$\sum _{\{u:(u,v)\in E\}}{f}_{uv}=\sum _{\{w:(v,w)\in E\}}{f}_{vw}\mathrm{\forall }v\in V\setminus \{s,t\}.$ 也就是说，除了源点和汇点以外，进入一个节点的流量等于流出这个节点的流量，节点内不能保存流。

规定在一个图中，流的值是

$|f|=\sum _{v:(s,v)\in E}{f}_{sv}=\sum _{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 _{(u,v)\in X_C}{c}_{uv}=\sum _{(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割，所以经过图的最大流就是图的最小割。我们直观上就可以知道，通过能力最弱的断面就是整个网络的最大流量。这个理论把最大流问题和最小割问题联系了起来。

线性规划公式

最大流最小割问题可以被看做为一对线性规划對偶问题。

	Max-flow (Primal)	Min-cut (Dual)
variables	$f_{uv}$ $\mathrm{\forall }(u,v)\in E$ [a variable per edge]	$d_{uv}$ $\mathrm{\forall }(u,v)\in E$ [a variable per edge] $z_v$ $\mathrm{\forall }v\in V\setminus \{s,t\}$ [a variable per non-terminal node]
objective	maximize $\sum _{v:(s,v)\in E}{f}_{sv}$ [max total flow from source]	minimize $\sum _{(u,v)\in E}{c}_{uv}{d}_{uv}$ [min total capacity of edges in cut]
constraints	subject to $\begin{array}{cccc}{f}_{uv}& \le c_{uv}& & \mathrm{\forall }(u,v)\in E\\ \sum _u{f}_{uv}-\sum _w{f}_{vw}& =0& & v\in V\setminus \{s,t\}\end{array}$ [a constraint per edge and a constraint per non-terminal node]	subject to $\begin{array}{cccc}{d}_{uv}-z_u+z_v& \ge 0& & \mathrm{\forall }(u,v)\in E,u\ne s,v\ne t\\ d_{sv}+z_v& \ge 1& & \mathrm{\forall }(s,v)\in E,v\ne t\\ d_{ut}-z_u& \ge 0& & \mathrm{\forall }(u,t)\in E,u\ne s\\ d_{st}& \ge 1& & \text{if }(s,t)\in E\end{array}$ [a constraint per edge]
sign constraints	$\begin{array}{cccc}{f}_{uv}& \ge 0& & \mathrm{\forall }(u,v)\in E\\ \end{array}$	$\begin{array}{cccc}{d}_{uv}& \ge 0& & \mathrm{\forall }(u,v)\in E\\ z_v& \in ℝ& & \mathrm{\forall }v\in V\setminus \{s,t\}\end{array}$

最大流的线性规划公式是容易理解的，对于最小割的线性规划公式的理解如下：

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

$z_u=\{\begin{array}{cc}1,& u\in S\\ 0,& \text{Otherwise}\end{array}$

最小化目标是使在割中的边最小。

下列限制保证了这些变量可以确保一个合法的割。

• 限制 $d_{uv}-z_u+z_v\ge 0$(即 $d_{uv}\ge z_u-z_v$) 确保了对两个非源点或汇点 u,v, 如果u 在 S中 且 v 在 T中, 那么边 (u,v)一定会被记在割中 ($d_{uv}\ge 1$)。
• 限制 $d_{sv}+z_v\ge 1$(即 $d_{sv}\ge 1-z_v$) 确保了如果 v 在 T 中, 那么边 (s,v) 一定会被记在割中。
• 限制 $d_{ut}-z_u\ge 0$(即 $d_{ut}\ge 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* ，並且两个解相等。

举例

一个流量等于s-t 割的容量的流网络

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

应用

廣義最大流最小割定理

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

$\mathrm{\forall }v\in V\setminus \{s,t\}:\sum _{\{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 割的容量最小值。

門格爾定理

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

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

計畫選擇問題

計畫選擇問題的網絡型態

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

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

$\underset{P,Q}{\max }\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 的選擇無關，故只需求後兩項和的最小值，即

$\underset{P,Q}{\min }\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^{\prime }\setminus P)\cup Q\text{、 }\{t\}\cup P\cup (Q^{\prime }\setminus Q)$

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

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

	計畫收入 Template:Math	設備價格 Template:Math	備註
1	100	200	執行計畫 Template:Math 須購買設備 Template:Math、Template:Math。
2	200	100	執行計畫 Template:Math 須購買設備 Template:Math。
3	150	50	執行計畫 Template:Math 須購買設備 Template:Math。

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

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

影像分割問題

Each black node denotes a pixel.

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

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

$\underset{P,Q}{\max }\sum _{i\in P}{f}_i+\sum _{i\in Q}{b}_i-\sum _{i\in P,j\in Q\vee j\in P,i\in Q}{p}_{ij}$

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

$\underset{P,Q}{\min }\sum _{i\in Q}{f}_i+\sum _{i\in P}{b}_i+\sum _{i\in P,j\in Q\vee j\in P,i\in Q}{p}_{ij}$

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

历史

最大流最小割问题最早在1956年被P. Elias, A. Feinstein，和 C.E. Shannon 证明， 并且L.R. Ford, Jr. 和 D.R. Fulkerson 也在同年证明了该定理。

证明

同之前的設定，Template:Math 是一個網絡(有向圖) ，s 點和 t 點分別為 G 的起源點和超匯點。

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

設 f 達到最大流，令 Template:Math 是 f 的殘留網絡，定義

1. A：在 Template:Math 中可以從 s 出發到達的點
2. A^c：A 以外的點，即 V − A

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

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

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

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

• 所有從 A 流向 A^c 的邊流量均已達飽和。
• 所有從 A^c 流向 A 的邊流量均為 0。

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

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

於是，聲稱得證。

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

参见

• 线性规划
• 最大流
• 最小割
• 网络流
• Edmonds–Karp 算法
• Ford–Fulkerson 算法
• 近似最大流最小割定理

参考文献

• Template:Cite book
• Template:Cite book
• Template:Cite book