最大流最小割定理 是最优化理论 的定理。根据该定理,在一个网络流 中,从源点 到汇点 的最大的流量,等于它的最小割中每一条边的容量之和。“割”指的是一种边 的集合,如果移除这个集合的全部边,就会断开源点和汇点的连接。
最大流最小割定理 是线性规划 中的对偶问题 的一种特殊情况,并且可以用来推导门格尔定理 和König–Egerváry定理。[1]
定义 编辑
最大流和最小割定理是图论的一部分,因此为了准确定义,我们需要先定义图、流、割,然后再定义这个定理。
图 编辑 设 G = ( V , E ) {\displaystyle G=(V,E)} 为一个有向图,其中有一個起源点 s {\displaystyle s} 和一個超匯点 t {\displaystyle t} ,代表 s {\displaystyle s} 是所有流的源頭, t {\displaystyle t} 是所有流的終點。这个图的每一条边都有一个容量 c : E → R + ,记做 c u v {\displaystyle c_{uv}} 或者 c ( u , v ) {\displaystyle c(u,v)} ,代表着能通过边 ( u , v ) {\displaystyle (u,v)} 的最大流量。
最大流 编辑 定义: 流量 代表一种映射 f : E → R + {\displaystyle f:E\rightarrow \mathbb {R} ^{+}} ,记做 f u v {\displaystyle f_{uv}} 或者 f ( u , v ) {\displaystyle f(u,v)} ,代表通过边 ( u , v ) {\displaystyle (u,v)} 的流量。每一条边所通过的流有以下两个限定条件:
流量限制 : f u v ≤ c u v ∀ ( u , v ) ∈ E . {\displaystyle f_{uv}\leq c_{uv}\quad \forall \,(u,v)\in E.} 也就是说,一条边上的流量不可以超过它的容量。流量守恒 : ∑ { u : ( u , v ) ∈ E } f u v = ∑ { w : ( v , w ) ∈ E } f v w ∀ v ∈ V ∖ { s , t } . {\displaystyle \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 | = ∑ v : ( s , v ) ∈ E f s v = ∑ v : ( v , t ) ∈ E f v t . {\displaystyle |f|=\sum \nolimits _{v:(s,v)\in E}f_{sv}=\sum \nolimits _{v:(v,t)\in E}f_{vt}.} 也就是说,一个图的流是自其源点流出的流量之和,也是向其汇点流入的流量之和。或者说,由源点向汇点移动多少内容,这个图的流就是多少。
最大流问题 : 计算 | f | {\displaystyle |f|} 的最大值,即从 s {\displaystyle s} 到 t {\displaystyle t} 的最大流量。
最小割 编辑 定义: s-t割 C = ( S , T ) {\displaystyle C=(S,T)} 将图 G {\displaystyle G} 完全劃分 为两部分,使得 s ∈ S , t ∈ T , {\displaystyle s\in S,t\in T,} 也就是一侧有源,一侧有汇。 C {\displaystyle C} 的割集 X C {\displaystyle X_{C}} 是 { ( u , v ) ∈ E : u ∈ S , v ∈ T } . {\displaystyle \{(u,v)\in E\ :\ u\in S,v\in T\}.} 也就是说,一条边当且仅当骑在这个划分方法上,一个节点位于划分出来的源侧,另一个位于汇侧,那么它包含在 X C {\displaystyle X_{C}} 里。因此如果 C {\displaystyle C} 的割集是空集,或者我们把一个割集里的边全都从图中拿走,則 | f | = 0 {\displaystyle |f|=0} 。通俗地说,割集就是一个图的断面,而割则是划分断面的方法。
规定在一个图中,s-t割的容量 是
c ( S , T ) = ∑ ( u , v ) ∈ X C c u v = ∑ ( i , j ) ∈ E c i j d i j , {\displaystyle c(S,T)=\sum \nolimits _{(u,v)\in X_{C}}c_{uv}=\sum \nolimits _{(i,j)\in E}c_{ij}d_{ij},} 其中当 i ∈ S , j ∈ T {\displaystyle i\in S,j\in T} 时, d i j {\displaystyle d_{ij}} 为 1 {\displaystyle 1} , 否则为 0 {\displaystyle 0} 。通俗地说,割的容量就是断面中所有边的总容量。
最小 s-t 割问题: 计算 c ( S , T ) {\displaystyle c(S,T)} 的最小值。即找到一种割法,使割的容量最小。也就是说,找到通过能力最弱的断面。
主定理 编辑 可以证明一切流都不能超过任何s-t割,所以经过图的最大流就是图的最小割。我们直观上就可以知道,通过能力最弱的断面就是整个网络的最大流量。这个理论把最大流问题 和最小割问题联系了起来。
线性规划公式 编辑
最大流最小割问题可以被看做为一对线性规划對偶问题。[2]
Max-flow (Primal)
Min-cut (Dual)
variables f u v {\displaystyle f_{uv}} ∀ ( u , v ) ∈ E {\displaystyle \forall (u,v)\in E} [a variable per edge]
d u v {\displaystyle d_{uv}} ∀ ( u , v ) ∈ E {\displaystyle \forall (u,v)\in E} [a variable per edge]
z v {\displaystyle z_{v}} ∀ v ∈ V ∖ { s , t } {\displaystyle \forall v\in V\setminus \{s,t\}} [a variable per non-terminal node]
objective maximize ∑ v : ( s , v ) ∈ E f s v {\displaystyle \sum \nolimits _{v:(s,v)\in E}f_{sv}}
[max total flow from source]
minimize ∑ ( u , v ) ∈ E c u v d u v {\displaystyle \sum \nolimits _{(u,v)\in E}c_{uv}d_{uv}}
[min total capacity of edges in cut]
constraints subject to
f u v ≤ c u v ∀ ( u , v ) ∈ E ∑ u f u v − ∑ w f v w = 0 v ∈ V ∖ { s , t } {\displaystyle {\begin{aligned}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{aligned}}} [a constraint per edge and a constraint per non-terminal node]
subject to
d u v − z u + z v ≥ 0 ∀ ( u , v ) ∈ E , u ≠ s , v ≠ t d s v + z v ≥ 1 ∀ ( s , v ) ∈ E , v ≠ t d u t − z u ≥ 0 ∀ ( u , t ) ∈ E , u ≠ s d s t ≥ 1 if ( s , t ) ∈ E {\displaystyle {\begin{aligned}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{if }}(s,t)\in E\end{aligned}}} [a constraint per edge]
sign constraints f u v ≥ 0 ∀ ( u , v ) ∈ E {\displaystyle {\begin{aligned}f_{uv}&\geq 0&&\forall (u,v)\in E\\\end{aligned}}} d u v ≥ 0 ∀ ( u , v ) ∈ E z v ∈ R ∀ v ∈ V ∖ { s , t } {\displaystyle {\begin{aligned}d_{uv}&\geq 0&&\forall (u,v)\in E\\z_{v}&\in \mathbb {R} &&\forall v\in V\setminus \{s,t\}\end{aligned}}}
最大流的线性规划公式是容易理解的,对于最小割的线性规划公式的理解如下:
d u v = { 1 , u ∈ S , v ∈ T 0 , Otherwise {\displaystyle d_{uv}={\begin{cases}1,&u\in S,v\in T\\0,&{\text{Otherwise}}\end{cases}}} z u = { 1 , u ∈ S 0 , Otherwise {\displaystyle z_{u}={\begin{cases}1,&u\in S\\0,&{\text{Otherwise}}\end{cases}}} 最小化目标是使在割中的边最小。
下列限制保证了这些变量可以确保一个合法的割。
限制 d u v − z u + z v ≥ 0 {\displaystyle d_{uv}-z_{u}+z_{v}\geq 0} (即 d u v ≥ z u − z v {\displaystyle d_{uv}\geq z_{u}-z_{v}} ) 确保了对两个非源点或汇点 u,v , 如果u 在 S 中 且 v 在 T 中, 那么边 (u ,v )一定会被记在割中 ( d u v ≥ 1 {\displaystyle d_{uv}\geq 1} )。 限制 d s v + z v ≥ 1 {\displaystyle d_{sv}+z_{v}\geq 1} (即 d s v ≥ 1 − z v {\displaystyle d_{sv}\geq 1-z_{v}} ) 确保了如果 v 在 T 中, 那么边 (s,v) 一定会被记在割中。 限制 d u t − z u ≥ 0 {\displaystyle d_{ut}-z_{u}\geq 0} (即 d u t ≥ z u {\displaystyle d_{ut}\geq z_{u}} ) 确保了 u 在 S 中, 那么边 (u,t) 一定会被记在割中。 需要注意的是,这是一个最小化问题,我们不需要确保一条边不在割里,我们只要保证每条应当在割里的边被计算了。
注意到在给定的 s-t 割 C = ( S , T ) {\displaystyle C=(S,T)} 中,如果 i ∈ S {\displaystyle i\in S} 那么 z i = 1 {\displaystyle z_{i}=1} 并且 0 反之。 所以 z s {\displaystyle z_{s}} 应该等于 1 并且 z t {\displaystyle z_{t}} 应该等于0。由线性规划 中的强對偶定理推得最大流最小割問題 中的等式,也就是說如果原问题有一个最优解 x *,則对应问题也有一个最优解 y * ,並且两个解相等。
举例 编辑
一个流量等于s-t 割的容量的流网络 上圖是一個網絡,上有流量為 7 的流。令 S 集合和 T 集合分別包含所有白色和灰色的點, 從而形成了一個割集包含圖中虛線的 s-t 割,並且其容量為 7,與流量相同。故由大流最小割定理知,前述的流與 s-t 割皆達到流量及容量的極值。
应用 编辑
廣義最大流最小割定理 编辑 額外規定映射 c : V → R + {\displaystyle c\colon V\rightarrow R^{+}} 為點的容量,記做 c(v),使得一個流 f 不只要滿足邊的流量限制與流量守恆,還要滿足點的流量限制,即
∀ v ∈ V ∖ { s , t } : ∑ { u ∈ V ∣ ( u , v ) ∈ E } f u v ≤ c ( v ) . {\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 割的容量最小值。
門格爾定理 编辑 不共邊路徑問題為給定無向圖 G = ( V , E ) {\displaystyle G=(V,E)} 及兩頂點 s、t,求從 s 到 t 彼此沒有共同邊的路徑數量的最大值。
門格爾定理的敘述為從 s 到 t 彼此沒有共同邊的路徑數量的最大值等於在所有 G 的 s-t 割(以原本的定義)中,頂點分別在不同集合的邊數的最小值。
計畫選擇問題 编辑 計畫選擇問題的網絡型態 計畫選擇問題敘述如下:當下有 n 個計畫 p 1 , … , p n {\displaystyle p_{1},\dots ,p_{n}} 可以被實施、m 種設備 q 1 , … , q m {\displaystyle q_{1},\dots ,q_{m}} 可以被購買,要執行計畫必須擁有該計畫要求的設備,執行計畫 p i {\displaystyle p_{i}} 可獲得 r ( p i ) {\displaystyle r(p_{i})} 的收益,但購買設備 q j {\displaystyle q_{j}} 要支付 c ( q j ) {\displaystyle c(q_{j})} 的費用。如何選擇執行計畫並購買所需設備以獲得淨利的最大值?
設 P 為不 被執行的計畫的集合,Q 為所購買的設備,則問題變成求最大值
max P , Q ∑ i = 1 n r ( p i ) − ∑ p i ∈ P r ( p i ) − ∑ q j ∈ Q c ( q j ) {\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})} 注意到 ∑ i r ( p i ) {\textstyle \sum _{i}r(p_{i})} 與 P、Q 的選擇無關,故只需求後兩項和的最小值,即
min P , Q ∑ p i ∈ P r ( p i ) + ∑ q j ∈ Q c ( q j ) {\displaystyle \min _{P,Q}\sum _{p_{i}\in P}r(p_{i})+\sum _{q_{j}\in Q}c(q_{j})} 現在考慮一個網絡,起源点 s 連接到 n 個點 p 1 , … , p n {\displaystyle p_{1},\dots ,p_{n}} ,邊的容量分別為 r ( p i ) {\displaystyle r(p_{i})} ,超匯点 t 連接到 m 個點 q 1 , … , q m {\displaystyle q_{1},\dots ,q_{m}} ,邊的容量分別為 c ( q j ) {\displaystyle c(q_{j})} ,若執行任務 p i {\displaystyle p_{i}} 需購買設備 q j {\displaystyle q_{j}} ,則在 p i {\displaystyle p_{i}} 、 q j {\displaystyle q_{j}} 之間連上一條容量為無限大的邊,若不需購買設備,則不連上邊。則 ∑ p i ∈ P r ( p i ) + ∑ q j ∈ Q c ( q j ) {\textstyle \sum _{p_{i}\in P}r(p_{i})+\sum _{q_{j}\in Q}c(q_{j})} 對應到一個 s-t 割的容量,其中的兩個集合是要執行的計畫與要購買的設備和它的餘集,也就是
{ s } ∪ ( P ′ ∖ P ) ∪ Q 、 { t } ∪ P ∪ ( Q ′ ∖ Q ) {\displaystyle \{s\}\cup (P'\setminus P)\cup Q{\text{、 }}\{t\}\cup P\cup (Q'\setminus Q)} 在此, P ′ = { p 1 , … , p n } {\displaystyle P'=\{p_{1},\dots ,p_{n}\}} , Q ′ = { q 1 , … , q m } {\displaystyle Q'=\{q_{1},\dots ,q_{m}\}} 。於是,原問題轉成求該圖的最大流問題 ,並且可以藉由各種算法求得其極值。
以下給出一個計畫選擇問題的例子,右圖是該問題對應到的網絡。
計畫收入 r (pi )
設備價格 c (qj )
備註 1 100 200 執行計畫 p 1 須購買設備 q 1 、q 2 。
2 200 100 執行計畫 p 2 須購買設備 q 2 。
3 150 50 執行計畫 p 3 須購買設備 q 3 。
該網絡的最小 s-t 割是選擇計畫 p 2 、p 3 與設備 q 2 、q 3 ,容量為 250。三個計劃的總收益是 450,因此最大淨利為 450 − 250 = 200。
以上解法可以理解為將計畫所給予的收益流過所需設備,如果無法流滿設備至 t 的邊,代表執行計畫不合成本,最小割將選擇穿過 s 到計畫的邊而非穿過設備到 t 的邊。
影像分割問題 编辑 Each black node denotes a pixel. 設原圖有 n 像素,想要把該圖分割為前景和背景,並且將 i 像素歸類為前景有效益 fi ,歸類為背景有效益 bi ,但是若 i、j 像素相鄰且被歸類為不同塊,則會減少 pij 的效益。求將該圖分割為前後景的最有效益方法。
令 P 為前景的集合,Q 為背景的集合,於是問題轉化成求最大值
max P , Q ∑ i ∈ P f i + ∑ i ∈ Q b i − ∑ i ∈ P , j ∈ Q ∨ j ∈ P , i ∈ Q p i j {\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}} 因為 fi 、 bi 的總合是與 P、Q的選取無關,因此等價於求以下最小值
min P , Q ∑ i ∈ Q f i + ∑ i ∈ P b i + ∑ i ∈ P , j ∈ Q ∨ j ∈ P , i ∈ Q p i j {\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 個像素連上一條容量為 fi 的有向邊 ;第 i 個像素至超匯點連上一條容量為 bi 的有向邊 。相鄰的像素 i、j 之間連上來回兩條容量為 pij 的有向邊 。則一個 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 達到最大流,令 (Gf ) 是 f 的殘留網絡,定義
A:在 (Gf ) 中可以從 s 出發到達的點 Ac :A 以外的點,即 V − A 換句話說,v∈A 若且唯若 s 可以流出更多流量到 v。
我們宣稱 | f | = c ( A , A c ) {\displaystyle |f|=c(A,A^{c})} ,其中該 s-t 割的容量 定義為
c ( S , T ) = ∑ ( u , v ) ∈ ( S × T ) ∩ E c u v {\displaystyle c(S,T)=\sum \nolimits _{(u,v)\in (S\times T)\cap E}c_{uv}} .由於 | f | {\displaystyle |f|} 的大小等於所有流出集合 A 的流量總和減所有流入集合 A 的流量總和,故 | f | ≤ c ( A , A c ) {\displaystyle |f|\leq c(A,A^{c})} ,並且等號成立若且唯若
所有從 A 流向 Ac 的邊流量均已達飽和。 所有從 Ac 流向 A 的邊流量均為 0。 我們用反證法分別證明以上兩點:
假設存在從 A 流向 Ac 的邊 ( x , y ) ∈ A × A c {\displaystyle (x,y)\in A\times A^{c}} 並未達到飽和,即 f ( x , y ) < c x y {\displaystyle f(x,y)<c_{xy}} 。因此,可以從 x 流更多 的流量到 y,(x,y) 是 Gf 的一條邊。由 x∈A 知 Gf 圖中有一條中的路徑從 s 到 x,其中只經過 A 中的點, 所以 y∈A,產生矛盾。是故所有從 A 流向 Ac 的邊流量均已達飽和。 假設存在從 Ac 流向 A 的邊 ( y , x ) ∈ A c × A {\displaystyle (y,x)\in A^{c}\times A} 其流量不為 0,即 f ( x , y ) > 0 {\displaystyle 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 ) {\displaystyle c(A,A^{c})} 是容量的最小值,由聲稱知,最大流最小割定理得證。
参见 编辑 参考文献 编辑 ^ 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). ^ Trevisan, Luca. Lecture 15 from CS261: Optimization (PDF) . (原始内容存档 (PDF) 于2019-11-01). ^ 3.0 3.1 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