辺素路

最初に発見された最大フローの応用の一つは、有向グラフ \(G\) の特定の頂点 \(s\) と \(t\) を結ぶ辺素な路集合の大きさの最大値の計算です。ここで \(G\) の路の集合が辺素 (edge-disjoint) であるとは、その集合に含まれる路の中に \(G\) の任意の辺が最大でも一回しか現れないことを言います。同じ頂点は複数回通っていても構いません。

任意のグラフを考えたとき、辺の重みが全て \(1\) ならば、\(s\) から \(t\) への最大フローは各辺に \(0\) または \(1\) 単位のフローを流します。フロー分解定理から、飽和した辺を集めた部分グラフ \(S\) は互いに素な路または閉路の和として表すことができ、さらに分解に含まれる路の数は最大フローの値と等しいことが分かります。また \(S\) から実際の路を取り出すことも簡単です ――\(S\) において \(s\) から \(t\) への適当な路を見つけ、取り除き、再帰すればそれで終わりです。

逆に、互いに素な \(k\) 個の \(s\) から \(t\) への路があれば、それらの路に含まれる辺全てに \(1\) 単位のフローを流すことで、値が \(k\) のフローを得ることができます。つまり任意の最大フローアルゴリズムは最大フローと同時に最大の辺素路集合も計算していると言えます。

Orlin のアルゴリズムを使って最大フローを計算すれば最大辺素路集合を \(O(VE)\) 時間で計算できますが、この単純な応用に Orlin のアルゴリズムを使うというはやりすぎです。実際、カット \((\lbrace s \rbrace, V \backslash \lbrace s \rbrace)\) の容量は最大でも \(V - 1\) なので、最大フローの値は最大でも \(V - 1\) であり、最初に説明したFord と Fulkerson の増加路アルゴリズムを使ったとしても計算時間は \(O(|f^{\ast}| E) = \) \(\pmb{O(VE)}\) です。

同じアルゴリズムを使って無向グラフ \(G\) の最大辺素路集合を計算することもできます。まず、\(G\) に含まれる無向辺 \(uv\) を \(1\) 単位の容量を持つ二つの有向辺 \(u \rightarrow v\) と \(v \rightarrow u\) に変更し、この有向グラフを \(G^{\prime}\) とします。続いて Ford-Fulkerson のアルゴリズムを使って \(G^{\prime}\) の最大フロー \(f^{\ast}\) を計算します。もし \(f^{\ast}\) が \(u \rightarrow v\) と \(v \rightarrow u\) の両方を飽和させるなら、両方の辺を削除してもフローの値は変化しません (一般的に言えば、\(f^{\ast}\) に含まれる閉路を全て削除して非巡回の最大フローとしてしまっても構いません。ここでは長さが 2 の閉路だけを削除しています)。よって一般性を失うことなく、\(f^{\ast}\) が飽和させる辺には一方向にしかフローが流れないと言えます。したがって \(f^{\ast}\) が飽和させる有向辺からなる部分グラフを調べれば辺素路集合を取り出せます。