查看“︁最大流最小割定理”︁的源代码

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

'''最大流最小割定理'''是[[线性规划]]中的[[对偶线性规划|对偶问题]]的一种特殊情况，并且可以用来推导[[门格尔定理]]和[[König–Egerváry定理]]。<ref>{{cite journal|last1=Dantzig|first1=G.B.|last2=Fulkerson|first2=D.R.|title=On the max-flow min-cut theorem of networks|journal=RAND corporation|date=9 September 1964|page=13|url=http://www.dtic.mil/dtic/tr/fulltext/u2/605014.pdf|accessdate=10 January 2018|archive-date=2018-05-05|archive-url=https://web.archive.org/web/20180505093256/http://www.dtic.mil/dtic/tr/fulltext/u2/605014.pdf|dead-url=no}}</ref>

== 定义 ==
最大流和最小割定理是图论的一部分，因此为了准确定义，我们需要先定义图、流、割，然后再定义这个定理。
=== 图 ===
设 <math>G=(V,E)</math> 为一个有向图，其中有一個[[起源点]] <math>s</math> 和一個[[超匯点]] <math>t</math>，代表 <math>s</math> 是所有流的源頭，<math>t</math> 是所有流的終點。这个图的每一条边都有一个'''容量''' {{Math|''c'' : ''E'' → '''R'''<sup>+</sup>}}，记做 <math>c_{uv}</math> 或者 <math>c(u,v)</math>，代表着能通过边 <math>(u,v)</math> 的最大流量。

=== 最大流 ===
'''定义：''' '''流量'''代表一种映射 <math>f:E \rightarrow \mathbb{R}^+</math>，记做<math>f_{uv}</math> 或者 <math>f(u,v)</math>，代表通过边 <math>(u,v)</math> 的流量。每一条边所通过的流有以下两个限定条件：
# '''流量限制'''：<math>f_{uv} \le c_{uv} \quad \forall\, (u,v)\in E.</math> 也就是说，一条边上的流量不可以超过它的容量。
# '''流量守恒'''：<math>\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\}.</math> 也就是说，除了源点和汇点以外，进入一个节点的流量等于流出这个节点的流量，节点内不能保存流。
规定在一个图中，流的值是
:<math>|f| = \sum\nolimits_{v:(s,v) \in E} f_{sv} = \sum\nolimits_{v:(v,t) \in E} f_{vt}.</math> 
也就是说，一个图的流是自其源点流出的流量之和，也是向其汇点流入的流量之和。或者说，由源点向汇点移动多少内容，这个图的流就是多少。

'''[[最大流问题]]：'''计算<math>|f|</math>的最大值，即从<math>s</math>到<math>t</math>的最大流量。

=== 最小割 ===
'''定义：''' '''s-t割''' <math>C=(S,T)</math> 将图 <math>G</math> 完全[[集合划分|劃分]]为两部分，使得 <math>s \in S, t \in T,</math> 也就是一侧有源，一侧有汇。<math>C</math> 的'''割集''' <math>X_C</math> 是 <math> \{ (u, v) \in E \ : \ u \in S, v \in T \}.</math> 也就是说，一条边当且仅当骑在这个划分方法上，一个节点位于划分出来的源侧，另一个位于汇侧，那么它包含在 <math>X_C</math> 里。因此如果 <math>C</math> 的割集是空集，或者我们把一个割集里的边全都从图中拿走，則 <math>|f| = 0</math>。通俗地说，割集就是一个图的断面，而割则是划分断面的方法。

规定在一个图中，s-t割的'''容量'''是
:<math>c (S,T) = \sum\nolimits_{(u,v) \in X_C} c_{uv} = \sum\nolimits_{(i,j) \in E } c_{ij}d_{ij},</math> 其中当 <math>i \in S,j \in T</math> 时，<math>d_{ij}</math> 为 <math>1</math>, 否则为 <math>0</math>。
通俗地说，割的容量就是断面中所有边的总容量。

'''最小 s-t 割问题：''' 计算 <math>c(S,T)</math> 的最小值。即找到一种割法，使割的容量最小。也就是说，找到通过能力最弱的断面。

=== 主定理 ===
可以证明一切流都不能超过任何s-t割，所以经过图的最大流就是图的最小割。我们直观上就可以知道，通过能力最弱的断面就是整个网络的最大流量。这个理论把[[最大流问题]]和最小割问题联系了起来。

== 线性规划公式 ==
最大流最小割问题可以被看做为一对线性规划對偶问题。<ref>{{Cite web|url=http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf|title=Lecture 15 from CS261: Optimization|last=Trevisan|first=Luca|date=|website=|archive-url=https://web.archive.org/web/20191101045143/http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf|archive-date=2019-11-01|dead-url=no|access-date=}}</ref>

{| class="wikitable" rules="" cellspacing="0" cellpadding="0" border="0"
!
! style="border: 1px solid darkgrey;"|
Max-flow (Primal)
! style="border-top: 1px solid darkgrey; border-bottom: 1px solid darkgrey; border-right: 1px solid darkgrey;"|
Min-cut (Dual)
|-
|'''variables'''
| style="border-right: 1px solid darkgrey; border-left: 1px solid darkgrey; padding: 1em;" valign="top" align="left" |
<math>f_{uv}</math> <math>\forall (u,v)\in E</math> ''[a variable per edge]''
| style="border-right: 1px solid darkgrey; padding: 1em;" valign="top" align="left" |
<math>d_{uv}</math> <math>\forall (u,v)\in E</math> ''[a variable per edge]''

<math>z_{v}</math> <math>\forall v\in V\setminus \{s,t\}</math> ''[a variable per non-terminal node]''
|-
|'''objective'''
| style="border-right: 1px solid darkgrey; border-left: 1px solid darkgrey; padding: 1em;" valign="top" align="left" |
maximize <math>\sum\nolimits_{v: (s,v)\in E} f_{sv}</math>

''[max total flow from source]''
| style="border-right: 1px solid darkgrey; padding: 1em;" valign="top" align="left" |
minimize <math>\sum\nolimits_{(u,v) \in E } c_{uv}d_{uv}</math>

''[min total capacity of edges in cut]''
|-
|'''constraints'''
| style="border-left: 1px solid darkgrey; border-bottom: 1px solid darkgrey; border-right: 1px solid darkgrey; padding: 1em;" valign="top" |
subject to 

:<math>\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}</math>

''[a constraint per edge and a constraint per non-terminal node]''
| style="border-bottom: 1px solid darkgrey; border-right: 1px solid darkgrey; padding: 1em" valign="top" |
subject to

:<math>\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{if } (s, t) \in E
\end{align}</math>

''[a constraint per edge]''
|-
|'''sign constraints'''
|<math>\begin{align} 
f_{uv} & \geq 0 && \forall (u, v) \in E\\
\end{align}</math>
|<math>\begin{align}
d_{uv} & \geq 0 && \forall (u, v) \in E \\
z_v & \in \R && \forall v \in V\setminus \{s,t\} 
\end{align}</math>
|}

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

:<math>d_{uv} = \begin{cases} 1, & u \in S , v \in T 
\\ 0, & \text{Otherwise} \end{cases}</math> 

:<math>z_{u} = \begin{cases} 1, &  u \in S \\ 0, & \text{Otherwise} \end{cases}</math>

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

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

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

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

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

== 举例 ==
[[File:Max-flow_min-cut_example.svg|右|有框|一个流量等于s-t 割的容量的流网络]]
上圖是一個網絡，上有流量為 7 的流。令 S 集合和 T 集合分別包含所有白色和灰色的點， 從而形成了一個割集包含圖中虛線的 s-t 割，並且其容量為 7，與流量相同。故由大流最小割定理知，前述的流與 s-t 割皆達到流量及容量的極值。

== 应用 ==

=== 廣義最大流最小割定理 ===
額外規定映射 <math>c \colon V \rightarrow R^+</math>為點的容量，記做 c(v)，使得一個流 f 不只要滿足邊的流量限制與流量守恆，還要滿足點的流量限制，即
: <math>\forall v \in V \setminus \{s,t\} : \qquad \sum\nolimits_{\{u\in V\mid (u,v)\in E\}} f_{uv} \le c(v).</math>
換句話說，流過 v 點的總流量不能超過 v 的容量 c(v)。一個 ''s-t 割'' 的定義為一個包含一些點和邊的集合，滿足與任一條由 s 到 t 的路徑皆不互斥。並且 s-t 割的''容量'' 定義成所有點和邊的容量總和。

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

=== 門格爾定理 ===
{{See also|門格爾定理}}不共邊路徑問題為給定無向圖 <math>G=(V,E)</math> 及兩頂點 s、t，求從 s 到 t 彼此沒有共同邊的路徑數量的最大值。

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

=== 計畫選擇問題 ===
{{See also|最大流問題}}
[[File:Max-flow min-cut project-selection.svg|thumb|right|計畫選擇問題的網絡型態]]
計畫選擇問題敘述如下：當下有 n 個計畫 <math>p_1, \dots ,p_n</math>可以被實施、m 種設備 <math>q_1, \dots ,q_m</math> 可以被購買，要執行計畫必須擁有該計畫要求的設備，執行計畫 <math>p_i</math>可獲得  <math>r(p_i)</math> 的收益，但購買設備  <math>q_j</math> 要支付 <math>c(q_j)</math> 的費用。如何選擇執行計畫並購買所需設備以獲得淨利的最大值？

設 P 為'''不'''被執行的計畫的集合，Q 為所購買的設備，則問題變成求最大值
: <math>\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)</math>
注意到 <math display="inline">\sum_{i} r(p_i)</math>與 P、Q 的選擇無關，故只需求後兩項和的最小值，即
: <math>\min_{P,Q} \sum_{p_i \in P} r(p_i) + \sum_{q_j \in Q} c(q_j)</math>
現在考慮一個網絡，起源点 s 連接到 n 個點 <math>p_1, \dots ,p_n</math>，邊的容量分別為 <math>r(p_i)</math>，超匯点 t 連接到 m 個點 <math>q_1, \dots ,q_m</math>，邊的容量分別為 <math>c(q_j)</math>，若執行任務 <math>p_i</math>需購買設備  <math>q_j</math> ，則在 <math>p_i</math>、<math>q_j</math> 之間連上一條容量為無限大的邊，若不需購買設備，則不連上邊。則 <math display="inline">\sum_{p_i \in P} r(p_i) + \sum_{q_j \in Q} c(q_j)</math> 對應到一個 s-t 割的容量，其中的兩個集合是要執行的計畫與要購買的設備和它的餘集，也就是
: <math>\{s\}\cup (P'\setminus P) \cup Q \text{、 } \{t\}\cup P \cup (Q'\setminus Q) </math>
在此，<math>P'=\{p_1, \dots ,p_n\}</math>，<math>Q'=\{q_1, \dots ,q_m\}</math>。於是，原問題轉成求該圖的[[最大流問題]]，並且可以藉由各種算法求得其極值。

以下給出一個計畫選擇問題的例子，右圖是該問題對應到的網絡。
{| class="wikitable" style="text-align:center; width:560px;" border="1"
|-
! width="20px" |
! width="120px" |
計畫收入  {{math|''r''(''p<sub>i</sub>'')}}
! width="120px" |
設備價格  {{math|''c''(''q<sub>j</sub>'')}}
!備註
|-
! 1
| 100 || 200
| align="left" style="padding-left: 1em;" |
執行計畫 {{Math|''p''<sub>1</sub>}} 須購買設備 {{Math|''q''<sub>1</sub>}}、{{Math|''q''<sub>2</sub>}}。
|-
! 2
| 200 || 100
| align="left" style="padding-left: 1em;" |
執行計畫 {{Math|''p''<sub>2</sub>}} 須購買設備 {{Math|''q''<sub>2</sub>}}。
|-
! 3
| 150 || 50
| align="left" style="padding-left: 1em;" |
執行計畫 {{Math|''p''<sub>3</sub>}} 須購買設備 {{Math|''q''<sub>3</sub>}}。
|}
該網絡的最小 s-t 割是選擇計畫 {{Math|''p''<sub>2</sub>}}、{{Math|''p''<sub>3</sub>}} 與設備 {{Math|''q''<sub>2</sub>}}、{{Math|''q''<sub>3</sub>}}，容量為 250。三個計劃的總收益是 450，因此最大淨利為 450 − 250 = 200。

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

=== 影像分割問題 ===
[[File:Image_segmentation.jpg|缩略图|Each black node denotes a pixel.]]
設原圖有 n 像素，想要把該圖分割為前景和背景，並且將 i 像素歸類為前景有效益 {{Mvar|&thinsp;f<sub>i</sub>}}，歸類為背景有效益 {{Mvar|&thinsp;b<sub>i</sub>}}，但是若 i、j 像素相鄰且被歸類為不同塊，則會減少 {{Mvar|p<sub>ij</sub>}} 的效益。求將該圖分割為前後景的最有效益方法。

令 P 為前景的集合，Q 為背景的集合，於是問題轉化成求最大值
: <math>\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}</math>
因為 {{Mvar|&thinsp;f<sub>i</sub>}}、{{Mvar|&thinsp;b<sub>i</sub>}} 的總合是與 P、Q的選取無關，因此等價於求以下最小值
: <math>\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}</math>
以上的最小值問題可以被描述為一個網絡的最小割問題，其中該網絡如右圖，以橘點為起源點；紫點為超匯點。各個像素被描述為網絡的頂點，起源點至第 i 個像素連上一條容量為 {{Mvar|&thinsp;f<sub>i</sub>}} 的[[有向邊]]；第 i 個像素至超匯點連上一條容量為 {{Mvar|b<sub>i</sub>}} 的[[有向邊]]。相鄰的像素 i、j 之間連上來回兩條容量為 {{Mvar|p<sub>ij</sub>}} 的[[有向邊]]。則一個 s-t 割代表一種將部分像素歸類為前景 P、其餘歸類為背景 Q 的安排。

== 历史 ==
'''最大流最小割问题'''最早在1956年被P. Elias, A. Feinstein，和 [[克劳德·香农|C.E. Shannon]] 证明<Ref name=Elais>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</ref>， 并且L.R. Ford, Jr. 和 D.R. Fulkerson 也在同年证明了该定理<Ref name=Elais/>。

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

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

設 f 達到最大流，令 {{math|(''G<sub>f</sub>''&thinsp;)}} 是 f 的殘留網絡，定義

# A：在 {{math|(''G<sub>f</sub>''&thinsp;)}} 中可以從 s 出發到達的點
# A<sup>c</sup>：A 以外的點，即 V − A

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

我們'''宣稱''' <math>|f|=c(A,A^c)</math>，其中該 s-t 割的'''容量'''定義為 
: <math>c (S,T) = \sum\nolimits_{(u,v) \in (S \times T) \cap E} c_{uv}</math>.
由於 <math>|f|</math> 的大小等於所有流出集合 ''A'' 的流量總和減所有流入集合 ''A'' 的流量總和，故 <math>|f| \leq c(A,A^c)</math>，並且等號成立[[若且唯若]]
* 所有從 ''A'' 流向 ''A<sup>c</sup>'' 的邊流量均已達飽和。
* 所有從 ''A<sup>c</sup>'' 流向 ''A'' 的邊流量均為 0。
我們用反證法分別證明以上兩點：
* 假設存在從 ''A'' 流向 ''A<sup>c</sup>''  的邊 <math>(x,y) \in A \times A^c</math> 並未達到飽和，即 <math>f(x,y)<c_{xy}</math>。因此，可以從 x 流更'''多'''的流量到 y，(x,y) 是 G<sub>f</sub> 的一條邊。由 x∈A 知 G<sub>f</sub> 圖中有一條中的路徑從 s 到 x，其中只經過 A 中的點， 所以 y∈A，產生矛盾。是故所有從 ''A'' 流向 ''A<sup>c</sup>'' 的邊流量均已達飽和。 
* 假設存在從 ''A<sup>c</sup>''  流向 ''A'' 的邊 <math>(y,x) \in A^c \times A</math> 其流量不為 0，即 <math>f(x,y)>0</math>。因此，可以從 y 流更'''少'''的流量到 x，(x,y) 是 G<sub>f</sub> 的一條邊。由 x∈A 知 G<sub>f</sub> 圖中有一條中的路徑從 s 到 x，其中只經過 A 中的點， 所以 y∈A，產生矛盾。是故所有從 ''A<sup>c</sup>'' 流向 ''A'' 的邊流量均為 0。

於是，聲稱得證。

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

== 参见 ==
* [[线性规划]]
* [[最大流]]
* [[最小割]]
* [[网络流]]
* [[Edmonds–Karp算法|Edmonds–Karp 算法]]
* [[Ford–Fulkerson算法|Ford–Fulkerson 算法]]
* 近似最大流最小割定理

== 参考文献 ==
{{Reflist}}

* {{Cite book|title=Combinatorial Optimization: Networks and Matroids|last=Eugene Lawler|authorlink=Eugene Lawler|publisher=Dover|year=2001|isbn=0-486-41453-1|pages=117–120|chapter=4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem}}
* {{Cite book|title=Combinatorial Optimization: Algorithms and Complexity|url=https://archive.org/details/combinatorialopt00papa|last=[[Christos H. Papadimitriou]], [[Kenneth Steiglitz]]|publisher=Dover|year=1998|isbn=0-486-40258-4|pages=[https://archive.org/details/combinatorialopt00papa/page/n134 120]–128|chapter=6.1 The Max-Flow, Min-Cut Theorem}}
* {{Cite book|title=Approximation Algorithms|last=[[Vijay Vazirani|Vijay V. Vazirani]]|publisher=Springer|year=2004|isbn=3-540-65367-8|pages=93–100|chapter=12. Introduction to LP-Duality}}
[[Category:组合优化]]
[[Category:網絡流]]