最大フロー最小カット定理 （さいだいフローさいしょうカットていり、英 : Max-flow min-cut theorem ）は、フローネットワーク における最大フロー問題 と呼ばれる最適化問題 に関する定理である。メンガーの定理 から導出される。その内容は次の通り。
「最大フローは最小カット の容量に等しい」 平たく言えば、ネットワークの最大流量はボトルネック に左右されることを意味している。任意の2点間で、一方から他方へ流れる物量は、その経路内で最も弱い部分によって制限される。
定義
G
(
V
,
E
)
{\displaystyle G(V,E)}
有向グラフ であり、各エッジ（枝）
(
u
,
v
)
{\displaystyle (u,v)}
c
(
u
,
v
)
{\displaystyle c(u,v)}
実数 ）があるとする。さらに、始点となるノード
s
{\displaystyle s}
t
{\displaystyle t}
カット （cut）とは、ノード群を2つの集合
S
{\displaystyle S}
T
{\displaystyle T}
S
{\displaystyle S}
s
{\displaystyle s}
T
{\displaystyle T}
t
{\displaystyle t}
2
|
V
|
−
2
{\displaystyle 2^{|V|-2}\,}
あるカット
(
S
,
T
)
{\displaystyle (S,T)}
S
{\displaystyle S}
T
{\displaystyle T}
c
(
S
,
T
)
=
∑
u
∈
S
,
v
∈
T
|
(
u
,
v
)
∈
E
c
(
u
,
v
)
{\displaystyle c(S,T)=\sum _{u\in S,v\in T|(u,v)\in E}c(u,v)}
ここで以下の3つの条件は等価である。
f
{\displaystyle f}
G
{\displaystyle G}
残余ネットワーク（residual network）
G
f
{\displaystyle G_{f}}
あるカット
(
S
,
T
)
{\displaystyle (S,T)}
|
f
|
=
c
(
S
,
T
)
{\displaystyle |f|=c(S,T)}
証明の概要: もし増加道があれば、それを使ってより大きなフローを得ることができるため、最大フローとは呼べなくなるし、逆も成り立つ。増加道がない場合、残余ネットワーク内で
s
{\displaystyle s}
S
{\displaystyle S}
T
{\displaystyle T}
c
(
S
,
T
)
{\displaystyle c(S,T)}
c
(
u
,
v
)
>
0
{\displaystyle c(u,v)>0}
(
u
,
v
)
{\displaystyle (u,v)}
v
{\displaystyle v}
s
{\displaystyle s}
T
{\displaystyle T}
特にここから
m
a
x
f
l
o
w
≥
m
i
n
c
u
t
{\displaystyle \mathrm {max\ flow} \geq \mathrm {min\ cut} }
m
a
x
f
l
o
w
{\displaystyle \mathrm {max\ flow} }
次に
m
i
n
c
u
t
≥
m
a
x
f
l
o
w
{\displaystyle \mathrm {min\ cut} \geq \mathrm {max\ flow} }
G
{\displaystyle G}
f
{\displaystyle f}
c
{\displaystyle c}
(
u
,
v
)
{\displaystyle (u,v)}
c
{\displaystyle c}
f
{\displaystyle f}
f
−
c
{\displaystyle f-c}
c
0
{\displaystyle c0}
0
{\displaystyle 0}
f
{\displaystyle f}
f
{\displaystyle f}
f
−
c
0
<=
0
{\displaystyle f-c0<=0}
f
{\displaystyle f}
f
<=
c
0
{\displaystyle f<=c0}
例 最大フローのネットワーク。3つの最小カットがある。 右図はノード
V
=
{
s
,
o
,
p
,
q
,
r
,
t
}
{\displaystyle V=\{s,o,p,q,r,t\}}
s
{\displaystyle s}
t
{\displaystyle t}
このネットワークには3つの最小カットが存在する。
カット
容量
S
=
{
s
,
p
}
,
T
=
{
o
,
q
,
r
,
t
}
{\displaystyle S=\{s,p\},T=\{o,q,r,t\}}
c
(
s
,
o
)
+
c
(
p
,
r
)
=
3
+
2
=
5
{\displaystyle c(s,o)+c(p,r)=3+2=5}
S
=
{
s
,
o
,
p
}
,
T
=
{
q
,
r
,
t
}
{\displaystyle S=\{s,o,p\},T=\{q,r,t\}}
c
(
o
,
q
)
+
c
(
p
,
r
)
=
3
+
2
=
5
{\displaystyle c(o,q)+c(p,r)=3+2=5}
S
=
{
s
,
o
,
p
,
q
,
r
}
,
T
=
{
t
}
{\displaystyle S=\{s,o,p,q,r\},T=\{t\}}
c
(
q
,
t
)
+
c
(
r
,
t
)
=
2
+
3
=
5
{\displaystyle c(q,t)+c(r,t)=2+3=5}
(
o
,
q
)
{\displaystyle (o,q)}
(
r
,
t
)
{\displaystyle (r,t)}
S
=
{
s
,
o
,
p
,
r
}
,
T
=
{
q
,
t
}
{\displaystyle S=\{s,o,p,r\},T=\{q,t\}}
G
f
{\displaystyle G_{f}}
c
f
(
r
,
q
)
=
c
(
r
,
q
)
−
f
(
r
,
q
)
=
0
−
(
−
1
)
=
1
{\displaystyle c_{f}(r,q)=c(r,q)-f(r,q)=0-(-1)=1}
歴史 この定理は1956年 、P. Elias、A. Feinstein、クロード・シャノン によって証明された。また、L.R. Ford, Jr. と D.R. Fulkerson も同じ年に独自に証明した。最大フローを求める問題は線形計画問題 の特殊形式であり、最大フロー最小カット定理は線形計画の双対性定理 の特殊ケースと見ることもできる。
関連項目 外部リンク 参考文献 P. Elias, A. Feinstein, and C. E. Shannon . Note on maximum flow through a network. IRE Transactions on Information Theory IT-2, 117--119, 1956.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest , and Clifford Stein. Introduction to Algorithms , Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Chapter 26: Maximum Flow, pp.643–700. 
