情報システム ネットワークフロー

ネットワークの例 あるコンピュータネットワーク 太線： 4パケット/秒 中線： 2パケット/秒 細線： 1バケット/秒 beta alpha 　　　　　太線：　4パケット/秒 　　　　　中線：　2パケット/秒 　　　　　細線：　1バケット/秒 beta alpha gamma delta the Source the Sink omega theta

ネットワークフロー G=(V, E)： 有向グラフ， c: E → R (コスト）, s: source, t: sink ネットワーク N = (G=(V, E), s, t, c) N 中の s から t へのフロー f : 1. 　0 ≦ f(u,v) ≦ c(u,v) 　　　　　　　　　　　　（容量制約） 2. f(u,v) = －f(v,u) 3.　Gの任意の点 v で、source s でも sink t でもない 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（流量保存）

最大フロー G=(V, E)： 有向グラフ， c: E → R (コスト）, s: source, t: sink ネットワーク N = (G=(V, E), s, t, c) フローfの流量 val(f) : source s から出て行くフローの総量 ネットワーク N の最大フロー: 　　　　　　N のフローのうち流量が最大のもの

Fold-Fulkersonアルゴリズムの実行例 0/1/1 フロー　含有量 残量

Fold-Fulkersonアルゴリズムの実行例 beta 0/1/1 Fold-Fulkersonアルゴリズムの実行例 alpha 0/1/1 0/2/2 0/2/2 gamma 0/1/1 delta 0/1/1 0/2/2 0/4/4 the Source the Sink 0/4/4 0/2/2 0/4/4 0/1/1 0/1/1 フロー　含有量 残量 omega 0/2/2 theta

0/1/1 フロー 含有量 残量 beta 0/1/1 alpha 0/1/1 0/2/2 0/2/2 gamma 0/1/1 delta 0/4/4 the Source the Sink 0/4/4 0/2/2 0/4/4 0/1/1 0/1/1 フロー　含有量 残量 omega 0/2/2 theta

0/1/1 フロー 含有量 残量 beta 0/1/1 alpha 0/1/1 0/2/2 0/2/2 gamma 0/1/1 delta 0/4/4 the Source the Sink 0/4/4 0/2/2 0/4/4 0/1/1 0/1/1 フロー　含有量 残量 omega 0/2/2 theta

0/1/1 フロー 含有量 残量 beta 0/1/1 alpha 0/1/1 0/2/2 0/2/2 gamma 0/1/1 delta 0/4/4 the Source the Sink 0/4/4 0/2/2 0/4/4 0/1/1 0/1/1 フロー　含有量 残量 omega 0/2/2 theta Finding an augmenting path

0/1/1 フロー 含有量 残量 beta 0/1/1 alpha 0/1/1 0/2/2 0/2/2 gamma 0/1/1 delta 1/1/0 1/2/1 1/4/4 the Source the Sink 0/4/4 0/2/2 0/4/4 0/1/1 0/1/1 フロー　含有量 残量 omega 0/2/2 theta Augmenting the flow

0/1/1 フロー 含有量 残量 beta 0/1/1 alpha 0/1/1 0/2/2 0/2/2 gamma 0/1/1 delta 1/1/0 1/2/1 1/4/4 the Source the Sink 0/4/4 0/2/2 0/4/4 0/1/1 0/1/1 フロー　含有量 残量 omega 0/2/2 theta Augmenting the flow

残余ネットワーク 0/1/1 フロー 含有量 残量 beta 0/1/1 alpha 0/1/1 0/2/2 0/2/2 gamma delta 1/1/0 1/2/1 1/4/4 the Source the Sink 0/4/4 0/2/2 0/4/4 0/1/1 0/1/1 フロー　含有量 残量 omega 0/2/2 theta 残余ネットワーク Augmenting the flow

0/1/1 フロー 含有量 残量 beta 0/1/1 alpha 0/1/1 0/2/2 0/2/2 gamma 0/1/1 delta 1/1/0 1/2/1 1/4/4 the Source the Sink 0/4/4 0/2/2 0/4/4 0/1/1 0/1/1 フロー　含有量 残量 omega 0/2/2 theta Augmenting the flow

0/1/1 フロー 含有量 残量 beta 0/1/1 alpha 0/1/1 0/2/2 2/2/0 gamma 0/1/1 delta 1/1/0 1/2/1 1/4/4 the Source the Sink 0/4/4 2/2/0 2/4/2 0/1/1 0/1/1 フロー　含有量 残量 omega 0/2/2 theta Augmenting the flow

0/1/1 フロー 含有量 残量 beta 0/1/1 alpha 0/1/1 0/2/2 2/2/0 gamma 0/1/1 delta 1/1/0 1/2/1 1/4/4 the Source the Sink 0/4/4 2/2/0 2/4/2 0/1/1 0/1/1 フロー　含有量 残量 omega 0/2/2 theta Augmenting the flow