組合せとグラフの理論(塩田)第12回 (3) 最大フローアルゴリズム

アイデア

 最大フローを求めるアルゴリズムのアイデアは割とシンプルです。

アイデア 問 1 のネットワーク
$\varphi$ :  
では、例えば次のフロー $\varphi$ は簡単に思いつきます。
$\varphi$ :  
まだ回線容量には余裕があって、あとどの位容量に余裕があるかを書き出すと
となります。この「残りのネットワーク」の中ではさらに次の道の形のフロー $\varepsilon$ が見つかります。
$\varepsilon$ :  
各弧で容量を足して
新 $\varphi=\varphi + \varepsilon$
とおくと、これは最大フローになっています。
新 $\varphi$ :  
 このように
  • 各回線の容量の残りはいくつか
  • その「残り」の中でどれだけフロー値を増やせるか
を考えます。

記号での表現

Def.9(「残り」の表し方) ネットワーク $N=(D,\Psi)$ のフロー $\varphi$ があたえられたとき、 その残りを表すネットワーク $N'=(D,\Psi')$ を次で定める。
$\left\{ \begin{array}{l} \Psi'(a)=\Psi(a)-\varphi(a) \\ \Psi'(a^{-1})=\Psi(a^{-1})+\varphi(a) \\ \end{array} \right.$  $\forall a \in A$
ただし $a^{-1}$ は $a$ と逆向きの弧を表す。
 $a^{-1}$ を考える理由は後述します。
Def.10( $\varepsilon$ の見つけ方) 上記の $N'$ の中で、 正の容量を持つ弧からなる $v$-$w$ 道 $P$ が存在するとき、 $P$ 上の弧の「残りの容量」の最小値を
$\dps{m=\min_{a \in P} \Psi'(a)}$
とおいて、$P$ 上の弧に重み $m$ を与えたフローを $\varepsilon$ とする:
$\varepsilon(a)= \left\{ \begin{array}{ll} m & a \mbox{ が } P \mbox{ 上の弧のとき } \\ 0 & \mbox{ otherwise} \\ \end{array} \right.$
$\varepsilon$ を「増加道(フロー増加道)」と呼ぶ。
 上の アイデア の例では
$P$ :  
が $N'$ の中の $v$-$w$ 道であり、真ん中が一番細いので それに太さを揃えたのが $\varepsilon$ です。

 $\varepsilon$ が「増加道」であれば
新 $\varphi=\varphi + \varepsilon$
は $\varphi$ よりフロー値が大きいフローとなります。 ( $+\varepsilon$ しても「流入量 = 流出量」が成り立つように「太さを揃え」ました。 )

 そして次の定理が肝 ( きも ) です。
Th.11 ネットワーク $N=(D,\Psi)$ のフロー $\varphi$ が最大フローであることと、 $N'$ が増加道を持たないことが同値である。
証明は次回やります。この定理により

最大フローアルゴリズム

Algorithm 12(最大フローアルゴリズム) 
  • 入力:ネットワーク $N$
  • 出力:$N$ の最大フロー $\varphi$
$\varphi=$ 適当なフロー
while True:
  $N'=$ ( Def.9 のネットワーク )
  if $N'$ に $v$-$w$ 道 $P$ が存在:
    $\varepsilon=$ ( Def.10 の増加道 )
    新 $\varphi=\varphi + \varepsilon$
  else:
    $\varphi$ を出力して終了
  • $v$-$w$ 道 $P$ を見つけるには、例えば $N'$ で $v$ を根とする(弧の向きに沿った)幅優先探索を実行します。
  • プログラムを組むときは、$\varphi$ の初期値は
    $\varphi=$ ゼロフロー $=$ 何も流れていない状態
    としますが、人間は賢いのである程度のフローを見つけてから始めます。