フロー分解

以下のグラフのフロー分解を考えます。

f:id:inarizuuuushi:20170420200053p:plain

まず、フローとは何かという話ですが、
始点(図s)から終点に(図t)に水を流すことを考えます。
そのときの"水の流れ"のことをフローと呼びますが、それにはいくつか条件があります。

図のノード(丸)とノードを結ぶ矢印の方向に管があり、それを伝って矢印の方向に水が流れるのですが、それぞれの管に流せる水の最大量が決まって、管に流せる量よりも多くの水は流せません。
またそのときにs, t以外のノード(図1~4)では 水の流入量と流出量が等しくなってなければなりません。(例えばノード1では流入量は3 + 2 = 5で流出量は1 + 4 = 5)

以上の性質を満たすものがフローと呼ばれるものです。
そこで、そのフローをsからtへのパス、もしくはグラフ中の閉路に一定量の水を流すフローに分解しようというのがフローの分解になります。
結果からいうと、上図のグラフは以下のように分解されます。
(見にくかったら、ごめんなさい)

f:id:inarizuuuushi:20170421064408j:plain

左上のフローを右の5つのフローに分解しています。

分解の方法はいたってシンプルです。
[ アルゴリズム ]
① sからtへのパスまたは閉路を見つける
② ①で見つけたパスまたは閉路の全ての辺について、最小の流水量を計算しdとおく
③ ①で見つけたパスまたは閉路の全ての辺にdだけ水を流すフローを保存(これが分解の要素の一つ)
④ 元のグラフから③のフローを引く
⑤ sからtへのパスまたは閉路がなくなれば、終了。そうでなければ①に戻る


元グラフから実際にアルゴリズムを辿っていくと、

f:id:inarizuuuushi:20170423151727j:plain


①sからtへのパスまたは閉路を見つける
f:id:inarizuuuushi:20170423151656j:plain


② ①で見つけたパスまたは閉路の全ての辺について、最小の流水量を計算しdとおく
③ ①で見つけたパスまたは閉路の全ての辺にdだけ水を流すフローを保存(これが分解の要素の一つ)
d = 1
f:id:inarizuuuushi:20170423151929j:plain


④ 元のグラフから③のフローを引く
f:id:inarizuuuushi:20170423152003j:plain


④ 終了後のグラフ 流水量0のエッジを削除した
f:id:inarizuuuushi:20170423152030j:plain



⑤ ①に戻る
①sからtへのパスまたは閉路を見つける
f:id:inarizuuuushi:20170423152348j:plain


② ①で見つけたパスまたは閉路の全ての辺について、最小の流水量を計算しdとおく
③ ①で見つけたパスまたは閉路の全ての辺にdだけ水を流すフローを保存(これが分解の要素の一つ)
d = 2
f:id:inarizuuuushi:20170423152418j:plain


④ 元のグラフから③のフローを引く
f:id:inarizuuuushi:20170423152437j:plain



⑤ ①に戻る
①sからtへのパスまたは閉路を見つける
f:id:inarizuuuushi:20170423152451j:plain


② ①で見つけたパスまたは閉路の全ての辺について、最小の流水量を計算しdとおく
③ ①で見つけたパスまたは閉路の全ての辺にdだけ水を流すフローを保存(これが分解の要素の一つ)
d = 2
f:id:inarizuuuushi:20170423152505j:plain


④ 元のグラフから③のフローを引く
f:id:inarizuuuushi:20170423152521j:plain



⑤ ①に戻る
①sからtへのパスまたは閉路を見つける
f:id:inarizuuuushi:20170423152539j:plain

② ①で見つけたパスまたは閉路の全ての辺について、最小の流水量を計算しdとおく
③ ①で見つけたパスまたは閉路の全ての辺にdだけ水を流すフローを保存(これが分解の要素の一つ)
d = 1
f:id:inarizuuuushi:20170423152650j:plain


④ 元のグラフから③のフローを引く
f:id:inarizuuuushi:20170423152708j:plain



⑤ ①に戻る
①sからtへのパスまたは閉路を見つける
f:id:inarizuuuushi:20170423153027j:plain

② ①で見つけたパスまたは閉路の全ての辺について、最小の流水量を計算しdとおく
③ ①で見つけたパスまたは閉路の全ての辺にdだけ水を流すフローを保存(これが分解の要素の一つ)
d = 1
f:id:inarizuuuushi:20170423153027j:plain



④ 元のグラフから③のフローを引く
アルゴリズム終了

長かったですね。
なぜこのアルゴリズムが上手くいくのかというと、
「フローからフローを引いてもフローです」(五七五)ということですね。