組合せとグラフの理論(塩田)第12回 (5) $a^{-1}$ を考える理由
$a^{-1}$ を考える理由
次のネットワークにおいて
$N$ :
初めにこのようなフロー $\varphi$ を見つけたとしましょう。
$\varphi$ :
このとき $a^{-1}$ を考えずに $N'$ を作ってしまうと
失敗 $N'$ :
となって $N'$ には $v$-$w$ 道が無いので増加道が作れません。
ところが $a^{-1}$ を考えて $N'$ を作れば
本当の $N'$ :
となり、次のように増加道 $\varepsilon$ が見つかります。
$\varepsilon$ :
新 $\varphi=\varphi+\varepsilon$ は
新 $\varphi$ :
となって最大フローになります。
最初の $\varphi$ では真ん中の回線を使っていましたが、
使わなかった方が通信容量が増えた訳で
「使ってみたけどやめた」
というときのために $a^{-1}$ を登録してあるのです。
無向グラフの場合
無向グラフはどの辺も双方向に通信可能なネットワークと考えられ、
最大フローアルゴリズムを実行することができます(ただし入口・出口が自動的には決まりませんが)。
例えば完全グラフ(全ての辺の容量1)では次のような最大フローが得られます。
→
頂点数を増やすとこんな絵が描けます。
真面目なことをやってるのに奇麗な絵が描ける、という例でした。