最大流和最小割定理是图论的一部分，因此为了准确定义，我们需要先定义图、流、割，然后再定义这个定理。
设
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
