最大流最小割定理

在最优化理论中，最大流最小割定理提供了对于一个网络流，从源点到目标点的最大的流量等于最小割的每一条边的和。即对于一个如果移除其中任何一边就会断开源点和目标点的边的集合的边的容量的总和。

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

定义

令G = (V, E)为一个网络（有向图），并且有一個起源点 s 和一個超匯点 t，代表 s 是所有流的源頭，t 是所有流的終點。

最大流

定义： 一条边的容量是一个映射c : E → R⁺，记做 c_uv 或者 c(u, v)，代表着能通过这条边的最大的流量。

定义： 一个流是一个映射 f : E → R⁺，记做 f_uv 或者  f (u, v)。每一条流有以下两个限定条件：

1. 流量限制：${\displaystyle \forall (u,v)\in E:\qquad f_{uv}\leq c_{uv}}$ 
2. 流量守恒：${\displaystyle \forall v\in V\setminus \{s,t\}:\qquad \sum \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\sum \nolimits _{\{w:(v,w)\in E\}}f_{vw}.}$ 

定义： 流的流量的定义是

${\displaystyle |f|=\sum \nolimits _{v\in V}f_{sv},}$ 

${\displaystyle s}$ 为${\displaystyle N}$ 的源点，代表着从源点流向目标点的流量。

最大流问题：计算${\displaystyle |f|}$ 的最大值，即从${\displaystyle s}$ 到${\displaystyle t}$ 的最大流量。

最小割

定义：一个 s-t 割 C = (S, T) 是一种 V 的劃分使得 s ∈ S, t ∈ T。C 的割集是集合

${\displaystyle \{(u,v)\in E\ :\ u\in S,v\in T\}.}$ 

因此如果 C 的割集是空集合，則 | f | = 0.

定义： 一个s-t割的容量是

${\displaystyle c(S,T)=\sum \nolimits _{(u,v)\in (S\times T)\cap E}c_{uv}=\sum \nolimits _{(i,j)\in E}c_{ij}d_{ij},}$ 

其中 ${\displaystyle d_{ij}=1}$  如果 ${\displaystyle i\in S}$  并且 ${\displaystyle j\in T}$ , 0 反之。

最小 s-t 割问题： 计算 c(S, T) 的最小值。即找到 S 和 T 使 s-t 割的容量达到它的最小值。

线性规划公式

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

最大流問題	最小割問題
變數： ${\displaystyle |f|,\{f_{uv}\mid (u,v)\in E\}}$	變數： ${\displaystyle \{d_{uv}\mid (u,v)\in E\},\{p_{u}\mid u\in V\}}$
求 ${\displaystyle |f|}$  的最大值	求 ${\displaystyle \sum _{(u,v)\in E}c_{uv}d_{uv}}$  的最小值
滿足 ${\displaystyle {\begin{array}{rclr}f_{uv}&\leq &c_{uv}&(u,v)\in E\\\sum _{v:(v,u)\in E}f_{vu}-\sum _{v:(u,v)\in E}f_{uv}&\leq &0&u\in V,u\neq s,t\\|f|+\sum _{v:(v,s)\in E}f_{vs}-\sum _{v:(s,v)\in E}f_{sv}&\leq &0&\\-|f|+\sum _{v:(v,t)\in E}f_{vt}-\sum _{v:(t,v)\in E}f_{tv}&\leq &0&\\f_{uv}&\geq &0&(u,v)\in E\\\end{array}}}$	滿足 ${\displaystyle {\begin{array}{rclr}d_{uv}-p_{u}+p_{v}&\geq &0&(u,v)\in E\\p_{s}-p_{t}&\geq &1&\\p_{u}&\geq &0&u\in V\\d_{uv}&\geq &0&(u,v)\in E\end{array}}}$

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

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

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

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

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

• 限制 ${\displaystyle d_{uv}-p_{u}+p_{v}\geq 0}$ (即 ${\displaystyle d_{uv}\geq p_{u}-p_{v}}$ ) 确保了对两个非源点或汇点 u,v, 如果u 在 S中 且 v 在 T中, 那么边 (u,v)一定会被记在割中 (${\displaystyle d_{uv}\geq 1}$ )。
• 限制 ${\displaystyle d_{sv}+p_{v}\geq 1}$ (即 ${\displaystyle d_{sv}\geq 1-p_{v}}$ ) 确保了如果 v 在 T 中, 那么边 (s,v) 一定会被记在割中。
• 限制 ${\displaystyle d_{ut}-p_{u}\geq 0}$ (即 ${\displaystyle d_{ut}\geq p_{u}}$ ) 确保了 u 在 S 中, 那么边 (u,t) 一定会被记在割中。

需要注意的是，这是一个最小化问题，我们不需要确保一条边不在割里，我们只要保证每条应当在割里的边被计算了。

注意到在给定的 s-t 割 ${\displaystyle C=(S,T)}$  中，如果 ${\displaystyle i\in S}$  那么 ${\displaystyle p_{i}=1}$  并且 0 反之。 所以 ${\displaystyle p_{s}}$  应该等于 1 并且 ${\displaystyle p_{t}}$  应该等于0。由线性规划中的强對偶定理推得最大流最小割問題中的等式，也就是說如果原问题有一个最优解 x*，則对应问题也有一个最优解 y* ，並且两个解相等。

举例

 

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

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

应用

廣義最大流最小割定理

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

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

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

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

門格爾定理

参见：門格爾定理

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

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

計畫選擇問題

参见：最大流問題

 

計畫選擇問題的網絡型態

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

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

${\displaystyle \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})}$ 

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

${\displaystyle \min _{P,Q}\sum _{p_{i}\in P}r(p_{i})+\sum _{q_{j}\in Q}c(q_{j})}$ 

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

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

在此，${\displaystyle P'=\{p_{1},\dots ,p_{n}\}}$ ，${\displaystyle 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 割是選擇計畫 p₂、p₃ 與設備 q₂、q₃，容量為 250。三個計劃的總收益是 450，因此最大淨利為 450 − 250 = 200。

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

影像分割問題

 

Each black node denotes a pixel.

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

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

${\displaystyle \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}}$ 

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

${\displaystyle \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 個像素連上一條容量為  f_i 的有向邊；第 i 個像素至超匯點連上一條容量為 b_i 的有向邊。相鄰的像素 i、j 之間連上來回兩條容量為 p_ij 的有像邊。則一個 s-t 割代表一種將部分像素歸類為前景 P、其餘歸類為背景 Q 的安排。

历史

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

证明

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

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

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

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

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

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

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

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

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

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

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

於是，聲稱得證。

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

参见

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

参考文献

1. Dantzig, G.B.; Fulkerson, D.R. On the max-flow min-cut theorem of networks (PDF). RAND corporation. 9 September 1964: 13 [10 January 2018]. （原始内容 (PDF)于2018-05-05）. 
2. Trevisan, Luca. Lecture 15 from CS261: Optimization (PDF). （原始内容 (PDF)于2019-11-01）. 
3. 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

• Eugene Lawler. 4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem. Combinatorial Optimization: Networks and Matroids. Dover. 2001: 117–120. ISBN 0-486-41453-1. 
• Christos H. Papadimitriou, Kenneth Steiglitz. 6.1 The Max-Flow, Min-Cut Theorem. Combinatorial Optimization: Algorithms and Complexity. Dover. 1998: 120–128. ISBN 0-486-40258-4. 
• Vijay V. Vazirani. 12. Introduction to LP-Duality. Approximation Algorithms. Springer. 2004: 93–100. ISBN 3-540-65367-8.