グラフ・ネットワークの基礎用語

ネットワーク理論
Text. Part 3 pp. 57-104
• 最短路問題 pp.58-84
• Ford法,双対問題とポテンシャル,
Bellman方程式とBellman-Ford法
• 負の費用をもつ閉路がある場合,閉
路を含まない場合
• 最大流問題 pp.85-94
• 最小費用流問題 pp.95-104
1
大名の最大流問題
飛脚が運べる量
(容量)
5
始点
s
1
8
2
8
2
t
終点
6
5
3
富士山から江戸までなるべくたくさんの氷を送りたい
どのように運ぶ?
2
最大流問題(グラフ理論的定義)
V
 枝集合 E
 点集合
G=(V,E)
 枝の容量 u: E → R+
 有向グラフ
 目的:
始点sから終点tまでの最大フロー
3
フローとは?
以下の条件を満たす実数値関数x:E → R
フロー整合条件
(江戸以外では氷は消費されない)
x
w:wvE
wv

x
w:vwE
vw
 0, v V \ s, t
容量制約と非負制約
(飛脚の運べる量には限界がある)
0  xe  ue , e  E
4
Ford-Fulkerson法(アイディア)
 最初は適当なフロー(例えば何も流さ
ない)からスタート
 少しずつフローを増やしていく
そのためには...
補助ネットワークを用いる
5
補助ネットワーク
5流せるところを
1流している状態
1/5
s
1
元の問題のネットワーク
残余容量1
1からsへあと1流せる
(sから1へあと1減らせる)
1
s
1
補助ネットワーク
4
残余容量4
sから1へあと4流せる
6
補助ネットワーク
5流せるところを
5流している状態
5/5
s
1
元の問題のネットワーク
1
補助ネットワーク
5
s
5流せる
残余容量0
もう流せない
7
補助ネットワーク
5流せるところを
流していない状態
0/5
s
1
元の問題のネットワーク
s
1
補助ネットワーク
5
もう流せない
残余容量5
あと5流せる
8
練習
(補助ネットワークの作り方)
1/5
0/3
s
1
2
s
1
2
2/4
t
t
9
増加可能パス
増加可能パス=
補助ネットワークにおいて始点sから終点tまでのパス
増加可能パスがある限り,パス内の枝の残余容量の
もっとも小さい値だけフローを増やせる
1
s
0
t
2
1
4
2
3
2
2 (= min {4,3,2})だけ増やせる!
10
Ford-Fulkerson法(アイディア)

最初は適当なフロー(例えば何も流さない)
からスタート

少しずつフローを増やしていく
(補助ネットワーク上で増加可能パスを見つ
けて,パス内の枝の残余容量の最小値だけ,
パス上のフローを増やす)

増加可能パスが見つからなくなったら終わり
やってみよう
11
Ford-Fulkerson法
0/8
0/5
1
0/8
t
0/2
s
2
何も流れていない
0/5
0/6
8
3
1
5
2
s
8
増加可能パス
容量5
t
2
6
5
3
12
Ford-Fulkerson法
流れが増えた
0/8
0/5
1
0/2
s
5/8
t
2
5/5
増加可能パス
容量5
補助ネットワーク
が変化した
5/6
8
3
1
5
s
2
3
5
t
2
1
5
5
3
13
Ford-Fulkerson法
増加可能パス
容量2
5/8
5/5
1
0/2
s
5/8
t
2
5/5
5/6
3
3
1
5
s
2
3
5
2
t
5
1
5
5
3
14
Ford-Fulkerson法
7/8
5/5
1
t
2/2
s
7/8
2
5/5
5/6
1
3
増加可能パス
が見つからないので
終了
1
5
s
2
1
7
2
t
7
1
5
5
3
15
Ford-Fulkerson法(擬似コード)
xe:=0, e  E
while 増加可能パスがある do
適当な増加可能パスPを選択
Δ:=パスP内の枝の残余容量の最小値
パスP上にフローをΔだけ増加
16
練習
0/10
1
0/1
s
0/6
2
1
0/8
t
0/10
t
s
2
枝の本数の少ないパスを使うと 回で終了
枝の本数の多いパスを使うと 回で終了
17
最小カット
最大で12の氷を運べることはわかった
「12よりたくさんの氷は運べない」という
にはどうしたらよいだろうか?
カットの概念を導入する
18
カットとは?
点を2つのグループに分ける
1. 始点を含むグループ
2. 終点を含むグループ
始点を含むグループから終点を含むグループへ
向かっている有向枝の集合をカットとよぶ
カットに含まれる枝の容量の合計を
カットの容量とよぶ
例題のカットをみてみよう
19
例題のカット
5
1
s
カット
容量は13
2
8
2
t
8
6
5
3
始点を含むグループ
20
例題のカット
5
1
s
カット
容量は12
2
8
2
t
8
6
5
3
始点を含むグループ
21
例題のカット
5
1
s
始点を含むグループ
t
8
2
8
2
6
5
3
カット
容量は16
22
例題のカット
5
1
s
2
8
2
t
8
カット
容量は13
6
5
3
始点を含むグループ
23
例題のカット
5
1
t
8
カット
容量は13
s
2
8
2
始点を含むグループ
6
5
3
24
例題のカット
5
1
s
カット
容量は14
2
8
2
始点を含むグループ
t
8
6
5
3
25
カットの性質
観察してわかったと思うが,始点から終点へは
(どんなにがんばっても)
カット容量よりたくさんは流すことはできない.
カット容量は始点から終点へのフローの上界を
与える!
26
最小カット問題
カットの定義
 S   vw | vw E, v  S , w  S
最小カット問題
全てのカットに対して,容量が最小のカットを
求める問題.
実は最小カット問題は最大流問題の双対問題である.
確かめてみよう.
27
最大流問題の双対問題
最大流問題(主問題)
最大化
x
w:swE
条件
x
w:wvE
wv
sw

x
w:vwE
vw
 0, v  V \ s, t
xe  ue , e  E
xe  0, e  E
最大化問題なので,(最適)目的関数値が
より大きくなるように条件を緩和する
28
最大流問題の双対問題
最大流問題の緩和問題


最大化  xsw   ue  xe ze     xwv   xvw  yv
w:swE
eE
vV \s ,t   w:wvE
w:vwE

条件  xwv   xvw  0, v  V \ s, t
w:wvE
w:vwE
xe  ue , e  E
xe  0, e  E
ze  0, e  E
ここは0以上
ここは0
条件を緩和する
29
最大流問題の双対問題
最大流問題のLagrange緩和問題


最大化  xsw   ue  xe ze     xwv   xvw  yv
w:swE
eE
vV \s ,t   w:wvE
w:vwE

条件 xe  0, e  E
ze  0, e  E
目的関数をxについてまとめる
30
最大流問題の双対問題
最大流問題のLagrange緩和問題


最大化  xsw   ue  xe ze     xwv   xvw  yv
w:swE
eE
vV \s ,t   w:wvE
w:vwE

条件 xe  0, e  E
ze  0, e  E
目的関数を変数 x についてまとめる
31
最大流問題の双対問題
最大流問題のLagrange緩和問題
最大化 ue ze 
eE
 y
vwE
v
 yw  zvw xvw
条件xe  0, e  E
ze  0, e  E
y s  1, yt  0
この問題の最適値は元の問題の最適値以上
目的関数の中で x に関係ない項を最小化し
目的関数の中で x の係数になっている項が0以下
の問題を作る
32
最大流問題の双対問題
最大流問題の双対問題
最小化  ue ze
eE
条件 yv  yw  zvw  0, vw  E
ze  0, e  E
ys  1, yt  0
この問題を観察してみる
zは枝に対応する変数である
yは点に対応する変数である
33
最大流問題の双対問題
最大流問題の双対問題
最小化  ue ze
eE
条件 yv  yw  zvw  0, vw  E
ze  0, e  E
ys  1, yt  0
枝 vw がカットに含まれるとき zvw=1,
そうでないとき
zvw=0
点 v が始点と同じグループに含まれるとき yv=1,
そうでないとき yv=0
この問題は,最小カット問題!
34
最大フロー最小カット定理
以上より,どうやっても富士山から江戸へは
12しか氷を運べないことがいえた.
最大フローが存在するとき,最大フロー量と最小カット
容量は一致する.
1
1
5
s
2
1
7
2
t
7
1
5
3
5
始点から補助ネットワーク上で到達可能な点集合->カット35
演習問題1
1
3
3
s
2
4
3
t
2
3
1
•最大流をFord-Fulkerson法で見つけてください.
•最小カットを示してください.
36
演習問題2
12
20
16
s
4
10
9
13
t
7
4
14
•最大流をFord-Fulkerson法で見つけてください.
•最小カットを示してください.
37
演習問題3(オプション)
工場
18
4
2
7
5
12
3
22
9
24
8
7
市場
7
13
16
24
2
工場
市場
6
4
12
ここには
好きな数字を入
れること
市場
工場から市場へなるべくたくさんの物を流したい
どう流したらよいだろうか?(ヒント:ダミーを使う)
38