Download presentation
Presentation is loading. Please wait.
1
情報システム ネットワークフロー
2
ネットワークの例 あるコンピュータネットワーク 太線： 4パケット/秒 中線： 2パケット/秒 細線： 1バケット/秒 beta alpha
太線： 4パケット/秒 中線： 2パケット/秒 細線： 1バケット/秒 beta alpha gamma delta the Source the Sink omega theta
3
ネットワークフロー 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 でもない （流量保存）
4
最大フロー G=(V, E)： 有向グラフ， c: E → R (コスト）, s: source, t: sink
ネットワーク N = (G=(V, E), s, t, c) フローfの流量 val(f) : source s から出て行くフローの総量 ネットワーク N の最大フロー: N のフローのうち流量が最大のもの
5
Fold-Fulkersonアルゴリズムの実行例
0/1/1 フロー 含有量 残量
6
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
7
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
8
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
9
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
10
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
11
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
12
残余ネットワーク 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
13
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
14
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
15
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
Similar presentations
