最大フロー最小カット定理 (さいだいフローさいしょうカットていり、英 : Max-flow min-cut theorem )は、フローネットワーク における最大フロー問題 についての定理である。これは、ネットワークに流れる「もの」の最大流量が、ボトルネック によって決まることを意味している。線形計画法 についての定理メンガーの定理 から導出することもできる。
定義
左から:1. 与えられたネットワーク。各エッジの容量はすべて等しいとする。2. ひとつのフロー。3. 2の残余ネットワークと、その増加道。 4. 最大フローの残余ネットワーク。s から到達可能な緑の丸印のノードの集合をS, 不可能な青の四角のノードの集合をTとすると、(S, T) が最小カットになっている。
二端子フローネットワーク
N
=
(
G
(
V
,
E
)
,
c
,
s
,
t
)
{\displaystyle {\boldsymbol {\mathrm {N} }}=(G(V,E),c,s,t)}
が与えられたとする。つまり、有限の有向グラフ
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}
が指定されたとする。
フロー f の流量 | f | とは、入口 s から出て行くフローの合計である。
|
f
|
=
∑ ∑ -->
v
∈ ∈ -->
N
− − -->
(
s
)
f
(
s
,
v
)
{\displaystyle |f|=\sum _{v\in N^{-}(s)}f(s,v)}
このネットワーク Ν のカット (S , T ) とは、ノード(頂点)V を2つの集合
S
{\displaystyle S}
と
T
{\displaystyle T}
に分割し、
S
{\displaystyle S}
には
s
{\displaystyle s}
が含まれ、
T
{\displaystyle T}
には
t
{\displaystyle t}
が含まれるようにすることをいう。
s と t 以外は自由にどちらかの集合に属することができるので、可能なカットの種類は
2
|
V
|
− − -->
2
{\displaystyle 2^{|V|-2}\,}
個ある。
カット
(
S
,
T
)
{\displaystyle (S,T)}
の容量 c (S , T ) とは、S と T の境界となっているエッジのうち、
S
{\displaystyle S}
から
T
{\displaystyle T}
に向かっているものの容量の合計である。
c
(
S
,
T
)
=
∑ ∑ -->
u
∈ ∈ -->
S
,
v
∈ ∈ -->
T
a
n
d
(
u
,
v
)
∈ ∈ -->
E
c
(
u
,
v
)
{\displaystyle c(S,T)=\sum _{u\in S,v\in T\mathrm {and} (u,v)\in E}c(u,v)}
フローでは流量が保存することから、あるフローが与えられている時、S と T の境界となっているエッジで、S から T へ流れる量から、T から S へ流れる量を引くと、フローの流量と等しくなる。
定理の主張
Ν の最大フローとは、Ν のフローのうち流量が最大のものをいい、最小カットとは、Ν のカットのうち容量が最小のものをいう。このとき、最大フロー f max と 最小カット (S, T)min について、
|
f
m
a
x
|
=
c
(
(
S
,
T
)
m
i
n
)
{\displaystyle |f_{\mathrm {max} }|=c((S,T)_{\mathrm {min} })}
が成り立つ。
証明の概要
証明は、以下のようにしてできる[1] 。
最大フローはフォード・ファルカーソンのアルゴリズム により、以下のようにして見つけることができる。[note 1]
二端子フローネットワーク Ν (G (V , E ), c , s , t ) が与えられたとする。
最大フローを見つけるために、s から t への道 を見つける。この道を構成するすべてのエッジの容量の最小値を、エッジの流量として割り当てると、これはこのネットワークのフローになる。
流量の余裕を容量とする順方向のエッジと、現在の流量を容量とする逆方向のエッジからなるネットワークで、容量が 0 となるエッジを取り除いたものを残余ネットワーク (residual network) もしくは補助ネットワークと呼ぶ。この残余ネットワークの中で、同じように道を見つける。道の構成要素のうち、順方向のエッジでは流量を増加させ、逆方向のエッジでは流量を減少させることで、より流量の大きな新しいフローを得ることができる。(このような、フロー f の残余ネットワークにおける s から t への道を、f の増加道 と呼ぶ。)
増加道がなくなれば、このフローが Ν の最大フローである。
最大フローの残余ネットワークは、
s
{\displaystyle s}
から到達可能なノード群
S
{\displaystyle S}
と到達不可能なノード群
T
{\displaystyle T}
に分けることができる。増加道がないので、t は T に含まれる。定義より、残余ネットワーク上では S から T へのエッジは存在しない。もとのネットワークに戻って考えると、S から出るエッジ (u , v ) はすべて、残余ネットワークに存在しないことから、流量の余裕がない、すなわち
f
(
u
,
v
)
=
c
(
u
,
v
)
{\displaystyle f(u,v)=c(u,v)}
となっていることが分かる。また、S に入るエッジは逆方向のエッジが残余ネットワークにないことから、流量が 0 であることが分かる。これらのことより、
c
(
S
,
T
)
=
|
f
m
a
x
|
{\displaystyle c(S,T)=|f_{\mathrm {max} }|}
となる。
したがって、
|
f
m
a
x
|
=
c
(
S
,
T
)
≥ ≥ -->
c
(
(
S
,
T
)
m
i
n
)
{\displaystyle |f_{\mathrm {max} }|=c(S,T)\geq c((S,T)_{\mathrm {min} })}
といえる。
次に
c
(
(
S
,
T
)
m
i
n
)
≥ ≥ -->
|
f
m
a
x
|
{\displaystyle c((S,T)_{\mathrm {min} })\geq |f_{\mathrm {max} }|}
も成り立つことをみる。任意のフロー f に対して、T へ流れこむエッジ (u , v ) の流量は最大で c (u , v ) であり、これの和は (S , T ) のカットの容量の定義そのものである。一方、T から S へ逆流するエッジの流量は、当然ながら最小値は 0 以上である。フローの流量は流量保存により、T に流入する流量から逆流する流量を引いたものであることを確認したが、このことよりf の流量は最大で カット (S , T ) の容量となる。このことより、
c
(
S
,
T
)
≥ ≥ -->
|
f
|
{\displaystyle c(S,T)\geq |f|}
、特に
c
(
(
S
,
T
)
m
i
n
)
≥ ≥ -->
|
f
m
a
x
|
{\displaystyle c((S,T)_{\mathrm {min} })\geq |f_{\mathrm {max} }|}
である。
例
最大フローのネットワーク。3つの最小カットがある。
右図はノード
V
=
{
s
,
o
,
p
,
q
,
r
,
t
}
{\displaystyle V=\{s,o,p,q,r,t\}}
からなるネットワークであり、始点
s
{\displaystyle s}
から 終点
t
{\displaystyle t}
への総流量は 5 で、これがこのネットワークの最大である。
このネットワークには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\}}
は最小カットではないことに注意されたい。これは残余ネットワーク(residual network)
G
f
{\displaystyle G_{f}}
において、エッジ (r,q) の容量が
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.
藤重, 悟『グラフ・ネットワーク・組み合せ論』共立出版、2002年。ISBN 978-4320016170 。
関連項目
外部リンク