最小全域木と最大流問題

離散数学
最小全域木と最大流問題
落合秀也
今日の内容
• 最小全域木
• プリムのアルゴリズム
• 最大流問題
• フォード・ファルカーソンのアルゴリズム
2
今日の内容
• 最小全域木
• プリムのアルゴリズム
• 最大流問題
• フォード・ファルカーソンのアルゴリズム
3
最小全域木を考える
Minimum Spanning Tree Problem
• ラベル付(重み付) グラフ G(V, E)が与えられたとき、ラ
ベルの和が最小となる全域木を作りたい
• 全域木 G(V, T)
• Vのすべての頂点で構成される木
∑ e∈T Ce
を最小にする T で作られる G(V,T)
(Ceは辺eのラベル)
8
2
• 最小全域木
2
2
2
9
4
5
3
5
1
6
例：ラベルを地点間の配線コストとする
このとき、全地点がつながるネットワークを
最小コストで配線したい
4
1
4
7
1
3
8 8
4
8
4
5
プリム法による最小全域木の作成
※ 考え方
a
3
• 任意の頂点を選び開始点sとする
c
• Tを辺の集合とする (開始時は空と
7
4
2
する)
b
5
d • Hの領域まで最小全域木の一部を
s
6
作っているとする。
3
6
• Hから出る辺のうち、そのコストが
7
5
最小の辺で接続する頂点をHに取
e
り込む・・・ (*)
8 f 8
H
• その辺をTに追加する
5
h
3
g
• H=Vとなるまで(*)を繰り返す
• G(V,T) が最小全域木となる
5
プリムのアルゴリズム：素直な実装
a
H := {s}
T := {}
2
While H ≠ V
5
min_length := ∞, min_edge := null
s
Foreach (u,v) : u∈H, v∈H-V
6
If min_length > length(u,v) Then,
7
min_length := length(u,v)
e
8
min_edge := (u,v)
EndIf
5
EndFor
T.add ( min_edge )
g
H.add( min_edge.right )
時間計算量 O(nm)
EndWhile
3
c
b
7
4
d
6
3
5
f
※ この疑似コードの場合
8
h
3
6
練習
• プリム法により、以下のグラフに対する最小全域木
を作成せよ
5
8
2
3
2
5
2
2
9
4
4
1
5
4
7
8
1
8
3
4
1
6
8
7
１．開始点を選ぶ
s
2
8
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
8
２．コストが最小の辺を選び
接続する頂点を取り込む (1/12)
s
2
8
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
9
２．コストが最小の辺を選び
接続する頂点を取り込む (2/12)
s
2
8
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
10
２．コストが最小の辺を選び
接続する頂点を取り込む (3/12)
s
2
8
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
11
２．コストが最小の辺を選び
接続する頂点を取り込む (4/12)
s
2
8
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
12
２．コストが最小の辺を選び
接続する頂点を取り込む (5/12)
s
2
8
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
13
２．コストが最小の辺を選び
接続する頂点を取り込む (6/12)
s
2
8
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
14
２．コストが最小の辺を選び
接続する頂点を取り込む (7/12)
s
2
8
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
15
２．コストが最小の辺を選び
接続する頂点を取り込む (8/12)
s
2
8
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
16
２．コストが最小の辺を選び
接続する頂点を取り込む (9/12)
s
2
8
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
17
２．コストが最小の辺を選び
接続する頂点を取り込む (10/12)
s
2
8
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
18
２．コストが最小の辺を選び
接続する頂点を取り込む (11/12)
s
2
8
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
19
２．コストが最小の辺を選び
接続する頂点を取り込む (12/12)
s
2
8
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
20
３．最小全域木の完成
8
2
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
21
プリムのアルゴリズム（改良版）
ダイクストラ法で工夫したように、
ダイクストラ法とよく似た形に実装できる
H := {s}
T := {}
While H ≠ V
min_length := ∞, min_edge := null
Foreach (u,v) : u∈H, v∈H-V
If min_length > length(u,v) Then,
min_length := length(u,v)
min_edge := (u,v)
EndIf
EndFor
T.add ( min_edge )
H.add( min_edge.right )
EndWhile
改良前
Foreach v ∈V (v≠s)
c[v] :=∞, prev[v]:=null
Q.add(v)
EndFor
c[s] :=0
While Q is not empty
u := Q.extractMin()
Foreach v in Adj[u]
If c[v] > length(u,v) Then,
c[v] := length(u,v)
prev[v] := u
( Q.changeKey() )
EndIf
EndFor
EndWhile
改良後
While Q is not empty
u := Q.extractMin()
Foreach v in Adj[u]
If c[v] > length(u, v) Then,
c[v] := length(u, v)
prev[v] := u
EndIf
EndFor
EndWhile
確認
• プリム法（改良版）により、以下
のグラフに対する最小全域木
を作成してみよ
8
2
2
3
2
2
9
4
5
1
4
1
8
8
4
1
6
5
4
7
3
5
8
23
プリム法: 計算量の考察
• While文の内部は n回実行される。
• Foreach文の内部は nm回実行される。
 実装によっては O(nm) となりえる。
• Q にリストや配列を使う場合
While Q is not empty
u := Q.extractMin()
Foreach v in Adj[u]
If c[v] > length(u, v) Then,
c[v] := length(u, v)
prev[v] := u
( Q.changeKey() )
EndIf
EndFor
EndWhile
• Q.extractMin()に O(n) の時間を要する
• Q.extractMin()は n回呼び出される
 O(n2)
• Q に 2分ヒープを使う場合
•
•
•
•
Q.extractMin()に O(log n)の時間を要する
Q.extractMin()の呼び出しはn回ある  O(n log n)
c[v]の更新に伴うヒープの組換え処理に、O(log n)の時間を要する
c[v]の更新は、m回発生する  O(m log n)
 O( (n+m) log n )
24
今日の内容
• 最小全域木
• プリムのアルゴリズム
• 最大流問題
• フォード・ファルカーソンのアルゴリズム
25
最大流問題
Maximum Flow Problem
• ラベル付(重み付) グラフ G(V, E)が与えられたとき、流入点
sから流出点tまでの総流量を最大化したい
• 辺のラベルの意味：流量の容量(最大量) 8
55
• 運べる荷物の量
• 流せる水の量
• 送れるパケット数
22
22
10
• このとき、
s
5
2
4
9
4
2
1
3
4
5
7
1
5 1 1
1
8 8
3
4 1
4
3
8
6
3
1
1
4
4
5
5
t
10
sに流れ込む流量 = tから流れ出る流量 (グラフの外から見た場合)
sから流れ出す流量 = tに流れ込む流量 (グラフの中で見た場合)
である。
26
この量の最大値(とそのときのフロー)をどう求めればよいか？
最大流問題：解決へのアプローチ
• s-t間の適当な道を考え、その流
量上限（最小容量）を算出す
る・・・赤色のケース
u
10
10
20
s
30 20
10
t
20
v
• 赤色のフローを流しても余って
いる別のs-t間の道を考える(逆
向きは押し戻すと考える)。この
際の、流量上限を算出する・・・
青色のケース
• 上記を繰り返していけば、徐々
に総流量が増えてやがてそれ
以上流せなくなる。これにより、
ネットワーク全体の最大流が求
27
まるのではないか？？
フローの定式化
• 辺を流れるフロー
f(u,v)
u
C(u,v)
C(v,u)
v
f(u, v) ≦ C(u, v)
f(v, u) = - f (u, v)
∴ -C(v, u) ≦ f(u, v) ≦ C(u, v)
ただし C(u, v) = C(v, u)とは限らない
• 頂点への流入量と流出量
v
流入量: fin(v) = ∑ u∈V, f(u,v)>0 f(u,v)
流出量: fout (v) = ∑ w∈V, f(v,w)>0 f(v,w)
v≠s,t であれば fin(v) = fout(v)
総流量: total(f)= fout(s) = fin(t) 28
フォード・ファルカーソン法
Ford-Fulkerson Algorithm
※ 考え方
u
20
10
10
20
30
s
10
10
30
20
t
20
v
フローに沿って
-20
u
0
10
10
s
40
50
10
10
20
10
• s-t間の何らかの道を考え、その流量の上限
を算出する
• そのフローfを容量Cから引いた値（残余容
量）を計算し、グラフから差し引く・・・そのグ
ラフをGfとする
• Gfに対して、同様のことをする（つまり、s-t
間の何らかの道を考え、その流量の上限を
算出し、総フローを算出し、容量から差し引
いて・・・）
• s-t間の道が無くなれば、終了
u
0
10
20
t
0
0
s
40
40
0
40
v
フローに沿って（さらに） 20
-10
v
20
0
s-t間の道がなくなった
(容量>0の弧についてのみ考える)
t
40 このとき差し引いている
総フローが求める最大流
29
練習
• フォード・ファルカーソン法を用いて、以下のフロー
グラフにおける sから t への最大流を求めよ。
10
20
10
10
20
s
30
10
30
50
40
10
20
t
10
20
10
(*) 辺のラベルは、
容量（向きは問わない）を
表している。
30
50
20
20
30
s
容量を、まず有向グラフに置き換える
10
20
10 10 10 20
30
10
t
30
10
50
10
20
10 30
50 10
20 10
30
50
20
50
40
20
20
40
20
30 10 10
10 10 20
30
20
20
20
s
s-t間の適当な道を考え、その流量の上限を算出する。
10
20
10 10 10 20
30
10
t
30
10
50
10
20
20
10 30
50 10
20 10
30
50
20
50
40
20
20
40
20
30 10 10
10 10 20
30
20
20
20
s
残余容量 Cf(u,v) = C(u,v) - f(u,v) とし、Gfを作成する
10
20
10 10 10 20
30
10
t
30
10
50
10
20
10 30
50 10
20 10
30
30
20
70
40
20
20
40
20
10 10 10
10 10 0
50
40
0
40
s
Gfにおいて、s-t間の適当な道を考え、その流量の上限を算出する。
10
20
10 10 10 20
30
10
t
30
10
50
10
20
20
10 30
50 10
20 10
30
30
20
70
40
20
20
40
20
10 10 10
10 10 0
50
40
0
40
s
残余容量 Cf(u,v) = C(u,v) - f(u,v) とし、Gfを作成する
10
(*) 本来は f(u,v)はフローの総和
道Pによって作られるフローではない
20
10 10 10 20
30
10
t
30
10
50
10
20
10 30
50 10
20 10
30
10
40
90
20
0
0
60
40
10 10 10
10 10 0
50
40
0
40
s
Gfにおいて、s-t間の適当な道を考え、その流量の上限を算出する。
10
20
10 10 10 20
30
10
t
30
10
50
10
10
20
30
10
50 10
20 10
30
10
40
90
20
0
0
60
40
10 10 10
10 10 0
50
40
0
40
s
残余容量 Cf(u,v) = C(u,v) - f(u,v) とし、Gfを作成する
10
(*) 本来は f(u,v)はフローの総和
道Pによって作られるフローではない
20
10 10 10 20
30
10
t
30
10
50
10
20
10 40
50 10
20 10
20
10
40
90
10
0
0
70
40
0 20
0
10 10 0
60
40
0
40
s
Gfにおいて、s-t間の適当な道を考え、その流量の上限を算出する。
10
（ここでは複数回まとめて表示）
20
10
10 10 10 20
30
10 10
t
10
30
10
10 10
50
10
20
10 40
50 10
20 10
20
10
40
90
10
0
0
70
40
0 20
0
10 10 0
60
40
0
40
s
残余容量 Cf(u,v) = C(u,v) - f(u,v) とし、Gfを作成する
0
(*) 本来は f(u,v)はフローの総和
道Pによって作られるフローではない
0
20 20 0
40
10
20
50
0
0
0
20
60
0
100 20
20 20
0
40
0
0
0
80
40
0 20
0
10 10 0
60
40
0
40
t
10
90
s
Gfにおいて、 s-t間の(Cf>0の辺で作られる)道が存在しないので、終了
0
0
20 20 0
40
10
20
50
0
0
0
20
60
0
100 20
20 20
0
40
0
0
0
80
40
0 20
0
10 10 0
60
40
0
40
t
10
90
s
最大流は以下のフローの総和である。
10
10
10
10
t
10 10
20
20
各辺が以下のフローを通すとき、sからtに対して最大流
が得られる。その流量は100
10
10
s
10
10
10
20
s
30
10
30
50
10
20
10
20
20
t
10
40
30
40
20
10
20
t
10 10
20
42
フォード・ファルカーソンの
アルゴリズム
Max-Flow(G(V,E), s, t)
∀e∈E, f(e)=0
While any paths from s to t exist in residual graph Gf
道の発見には
P := simple-path(s,t) in Gf
「幅優先探索」「深さ優先探索」
などが用いられる
f’ := augment(f, P)
フロー f に道Pを流れるフローの上限分を
Update f to be f’
追加し、それを f’ に代入する処理
Update Gf to be Gf’
EndWhile
※ このアルゴリズムの停止性について
Return f
考察してみよ
43
今日の内容
• 最小全域木
• プリムのアルゴリズム
• 最大流問題
• フォード・ファルカーソンのアルゴリズム
44
今後の予定
• 6月26日：分散ハッシュテーブル
• Chord アルゴリズム
• 7月3日：平面的グラフ、地図
• 7月10日：スキップグラフ
• 7月17日：試験 13:00 – 14:30 ＠241講義室
45

Download Report