最大流最小割定理 是最优化理论 的定理。根据该定理，在一个网络流 中，从源点 到汇点 的最大的流量，等于它的最小割中每一条边的容量之和。“割”指的是一种边 的集合，如果移除这个集合的全部边，就会断开源点和汇点的连接。
最大流最小割定理 是线性规划 中的对偶问题 的一种特殊情况，并且可以用来推导门格尔定理 和König–Egerváry定理 。[ 1]
最大流和最小割定理是图论的一部分，因此为了准确定义，我们需要先定义图、流、割，然后再定义这个定理。
定义： 流量 代表一种映射
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]
More information
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}}}
Close
最大流的线性规划公式是容易理解的，对于最小割的线性规划公式的理解如下：
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}\}}
最大流问题 ，并且可以借由各种算法求得其极值。
以下给出一个计划选择问题的例子，右图是该问题对应到的网络。
More information 计划收入 r(pi), 设备价格 c(qj) ...
计划收入 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
Close
该网络的最小 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})}
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
, ...
