最大フロー最小カット定理

目次

インタラクティブ

増加道、残余辺、最小カット

増加自動リセット

フローネットワーク（流量 / 容量）

増加道最小カット流量

「増加」を押して最初の増加道を求めます。

最大フロー = 最小カット

フローとカットが同じ限界を示す理由

フローは、容量に制限のある有向辺を通して始点から終点へ送れる量を表します。カットは両者を隔てるボトルネックを表します。最大フロー最小カット定理は、この二つの見方が同じ限界値を与えることを示します。

相異なる始点 $s$ と終点 $t$ を持つ有限有向ネットワーク $G=(V,E)$ を考えます。各辺 $e$ の容量 $c_e$ は有限かつ非負です。実行可能なフローは、各辺に $f_e$ を割り当てて

$$0\leq f_e\leq c_e$$

を満たし、$s,t$ 以外の各頂点で流入量と流出量を等しくするものです。フロー値 $|f|$ は $s$ から出る正味のフローであり、$t$ に入る正味のフローにも等しくなります。

$s$–$t$ カットは、$V=S\mathbin{\dot\cup}T$、$s\in S$、$t\in T$ を満たす分割です。容量には、元の辺のうち $S$ から $T$ へ向かう辺だけを数えます。

$$c(S,T)=\sum_{e=(u,v)\in E:\,u\in S,\ v\in T}c_e.$$

定理は、実行可能なフローの最大値が、すべての $s$–$t$ カット容量の最小値に等しいと述べます。

どのカットもフローの上限

任意の実行可能フローとカットについて、$S$ 内の頂点の正味流出量を合計すると、内部辺のフローが相殺されて

$$\begin{aligned} |f| &= \sum_{e=(u,v):\,u\in S,\,v\in T}f_e\\ &\quad-\sum_{e=(u,v):\,u\in T,\,v\in S}f_e \end{aligned}$$

となります。第2の和は非負で、第1の和の各項は対応する辺の容量以下です。したがって $|f|\leq c(S,T)$ であり、これはすべてのフローとカットに成り立ちます。

残余到達可能性から等号を導く

最大フローは存在します。ゼロフローは実行可能であり、実行可能なフロー全体は有限次元空間の閉かつ有界な集合だからです。元の辺 $u\to v$ ごとに、残余グラフには容量 $c_e-f_e$ の順方向辺と容量 $f_e$ の逆方向辺があります。逆方向辺は、その元の辺にすでに流したフローを取り消せることを表します。

正の残余容量を持つ辺だけをたどって $s$ から到達できる頂点を $S$、残りを $T=V\setminus S$ とします。$t$ が $S$ に含まれるなら、残余路の正のボトルネック分だけフローを増やせるため、最大性に反します。よって $S$ から $T$ へ向かう正容量の残余辺はありません。その結果、$S$ から $T$ へ向かう元の辺はすべて飽和し、$T$ から $S$ へ向かう元の辺にはフローがありません（あれば逆方向残余辺がカットを越えます）。先ほどのカットの式に代入すると $|f|=c(S,T)$ です。どのフロー値もどのカット容量も越えないため、このフローは最大、このカットは最小です。

小さな最適性証明書

容量が $s\to a:3$、$s\to b:2$、$a\to t:2$、$a\to b:1$、$b\to t:3$ のネットワークを考えます。同じ順にフロー $3,2,2,1,3$ を流すと、$a,b$ でフローが保存され、値は 5 です。カット $S=\{s\}$、$T=\{a,b,t\}$ の容量も $3+2=5$ です。フロー値とカット容量が一致するので、これ以上大きなフローも小さなカットもありません。

要点： フローは実現可能な輸送量、カットはボトルネックの容量です。残余ネットワークでの到達可能性から、両者の値が等しいことを証明するカットを得られます。