組合せとグラフの理論（塩田）第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}$ を登録してあるのです。
無向グラフの場合
無向グラフはどの辺も双方向に通信可能なネットワークと考えられ、
最大フローアルゴリズムを実行することができます（ただし入口・出口が自動的には決まりませんが）。
例えば完全グラフ（全ての辺の容量１）では次のような最大フローが得られます。
→ 
頂点数を増やすとこんな絵が描けます。
真面目なことをやってるのに奇麗な絵が描ける、という例でした。