定義
最大流和最小割定理是圖論的一部分，因此為了準確定義，我們需要先定義圖、流、割，然後再定義這個定理。
圖
設
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}
z
s
{\displaystyle z_{s}}
z
t
{\displaystyle z_{t}}
線性規劃 中的強對偶定理 推得最大流最小割問題 中的等式，也就是說如果原問題有一個最優解 x *，則對應問題也有一個最優解 y * ，並且兩個解相等。
舉例
一個流量等於s-t 割的容量的流網絡 上圖是一個網絡，上有流量為 7 的流。令 S 集合和 T 集合分別包含所有白色和灰色的點， 從而形成了一個割集包含圖中虛線的 s-t 割，並且其容量為 7，與流量相同。故由大流最小割定理知，前述的流與 s-t 割皆達到流量及容量的極值。
應用
廣義最大流最小割定理
額外規定映射
c
:
V
→
R
+
{\displaystyle c\colon V\rightarrow R^{+}}
∀
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 彼此沒有共同邊的路徑數量的最大值等於在所有 G 的 s-t 割(以原本的定義)中，頂點分別在不同集合的邊數的最小值。
計劃選擇問題
計劃選擇問題的網絡型態 計劃選擇問題敘述如下：當下有 n 個計劃
p
1
,
…
,
p
n
{\displaystyle p_{1},\dots ,p_{n}}
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})}
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})}
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
}
∪
(
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
以上解法可以理解為將計劃所給予的收益流過所需設備，如果無法流滿設備至 t 的邊，代表執行計劃不合成本，最小割將選擇穿過 s 到計劃的邊而非穿過設備到 t 的邊。
影像分割問題
Each black node denotes a pixel. 設原圖有 n 像素，想要把該圖分割為前景和背景，並且將 i 像素歸類為前景有效益 fi bi 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
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] [3]
證明
同之前的設定，G = (V , E )
將所有流考慮成一個歐式空間 的有界 閉 子集，滿足流量限制與流量守恆，而流量是一個連續函數，因此有極大值 |f| 。
設 f 達到最大流，令 (Gf )
A：在 (Gf )
Ac ：A 以外的點，即 V − A 換句話說，v∈A 若且唯若 s 可以流出更多流量到 v。
我們宣稱
|
f
|
=
c
(
A
,
A
c
)
{\displaystyle |f|=c(A,A^{c})}
容量 定義為
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}}
多 的流量到 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}
f
(
x
,
y
)
>
0
{\displaystyle f(x,y)>0}
少 的流量到 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
