情報システム
ネットワークフロー
ネットワークの例
あるコンピュータネットワーク
太線： 4パケット/秒
beta
alpha
中線： 2パケット/秒
細線： 1バケット/秒
gamma
delta
the
the
Source
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 でもない
 f(u, v)  0
uV
（流量保存）
最大フロー
G=(V, E)： 有向グラフ， c: E → R (コスト）, s: source, t: sink
ネットワーク N = (G=(V, E), s, t, c)
フローfの流量 val(f) :
source s から出て行くフローの総量
val( f )   f(s, v)
uV
ネットワーク N の最大フロー:
N のフローのうち流量が最大のもの
Fold-Fulkersonアルゴリズムの実行例
0/1/1
フロー
含有量
残量
beta
0/1/1
alpha
Fold-Fulkersonアルゴリズムの実行例
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
0/2/2
0/4/4
0/4/4
Sink
0/1/1
omega
0/2/2
0/1/1
theta
フロー
含有量
残量
beta
0/1/1
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
0/2/2
0/4/4
0/4/4
Sink
0/1/1
omega
0/2/2
0/1/1
theta
フロー
含有量
残量
beta
0/1/1
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
0/2/2
0/4/4
0/4/4
Sink
0/1/1
omega
0/2/2
0/1/1
theta
フロー
含有量
残量
beta
0/1/1
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
0/2/2
0/4/4
0/4/4
Sink
0/1/1
omega
Finding an augmenting path
0/2/2
0/1/1
theta
フロー
含有量
残量
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
0/2/2
0/4/4
0/4/4
Sink
0/1/1
omega
Augmenting the flow
0/2/2
0/1/1
theta
フロー
含有量
残量
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
0/2/2
0/4/4
0/4/4
Sink
0/1/1
omega
Augmenting the flow
0/2/2
0/1/1
theta
フロー
含有量
残量
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
0/2/2
0/4/4
0/4/4
Sink
0/1/1
omega
Augmenting the flow
0/2/2
0/1/1
theta
残余ネットワーク
フロー
含有量
残量
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
0/2/2
0/4/4
0/4/4
Sink
0/1/1
omega
Augmenting the flow
0/2/2
0/1/1
theta
フロー
含有量
残量
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
2/2/0
2/4/2
0/4/4
Sink
0/1/1
omega
Augmenting the flow
0/2/2
0/1/1
theta
フロー
含有量
残量
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
2/2/0
2/4/2
0/4/4
Sink
0/1/1
omega
Augmenting the flow
0/2/2
0/1/1
theta
フロー
含有量
残量

グラフとネットワーク 2016 年 5 月 16 日 第 6 回：用語一覧 岡本 吉央