離散数学

最小全域木と最大流問題

落合 秀也

今日の内容• 最小全域木• プリムのアルゴリズム• 最大流問題• フォード・ファルカーソンのアルゴリズム

2

今日の内容• 最小全域木• プリムのアルゴリズム• 最大流問題• フォード・ファルカーソンのアルゴリズム

3

最小全域木を考える
Minimum Spanning Tree Problem• ラベル付(重み付) グラフ G(V, E)が与えられたとき、ラベルの和が最小となる全域木を作りたい• 全域木 G(V, T)• Vのすべての頂点で構成される木∑ e∈T Ceを最小にする T で作られる G(V,T)(Ceは辺eのラベル)

82• 最小全域木
222

9453516

例：ラベルを地点間の配線コストとする
このとき、全地点がつながるネットワークを最小コストで配線したい

4147138 84845

プリム法による最小全域木の作成※ 考え方a3• 任意の頂点を選び開始点sとする
c• Tを辺の集合とする (開始時は空と742する)
b5d • Hの領域まで最小全域木の一部をs6作っているとする。
36• Hから出る辺のうち、そのコストが75最小の辺で接続する頂点をHに取e
り込む ・・・ (*)
8 f 8H• その辺をTに追加する

5h3g• H=Vとなるまで(*)を繰り返す• G(V,T) が最小全域木となる
5

プリムのアルゴリズム： 素直な実装
aH := {s}T := {}
2
While H ≠ V
5min_length := ∞, min_edge := nulls
Foreach (u,v) : u∈H, v∈H-V
6If min_length > length(u,v) Then,
7min_length := length(u,v)
e8min_edge := (u,v)
EndIf
5EndForT.add ( min_edge )gH.add( min_edge.right )時間計算量 O(nm)EndWhile

3cb74d635f※ この疑似コードの場合

8h36練習• プリム法により、以下のグラフに対する最小全域木を作成せよ
58232522944
1547818341687

１．開始点を選ぶ

s2

8232294514
1884

1654

73588２．コストが最小の辺を選び接続する頂点を取り込む (1/12)

s282322945141884

1654

73589２．コストが最小の辺を選び接続する頂点を取り込む (2/12)

s282322945141884

1654735810

２．コストが最小の辺を選び接続する頂点を取り込む (3/12)

s282322945141884

1654735811

２．コストが最小の辺を選び接続する頂点を取り込む (4/12)

s282322945141884

1654735812

２．コストが最小の辺を選び接続する頂点を取り込む (5/12)

s282322945141884

1654735813

２．コストが最小の辺を選び接続する頂点を取り込む (6/12)

s2823229451418841654735814

２．コストが最小の辺を選び接続する頂点を取り込む (7/12)

s2823229451418841654735815

２．コストが最小の辺を選び接続する頂点を取り込む (8/12)

s2823229451418841654735816

２．コストが最小の辺を選び接続する頂点を取り込む (9/12)s
282322945141884

1654735817

２．コストが最小の辺を選び接続する頂点を取り込む (10/12)

s2823229451418841654735818２．コストが最小の辺を選び接続する頂点を取り込む (11/12)

s2823229451418841654735819２．コストが最小の辺を選び接続する頂点を取り込む (12/12)

s2823229451418841654735820

３．最小全域木の完成
8223229451418841654735821

プリムのアルゴリズム（改良版）
ダイクストラ法で工夫したように、ダイクストラ法とよく似た形に実装できる
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)EndForc[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
EndForEndWhile
改良後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] := uEndIfEndFor
EndWhile

確認• プリム法（改良版）により、以下のグラフに対する最小全域木を作成してみよ
8223229451418841654735823

プリム法: 計算量の考察• 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
EndForEndWhile• 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までの総流量を最大化したい• 辺のラベルの意味： 流量の容量(最大量) 855• 運べる荷物の量• 流せる水の量• 送れるパケット数

222210• このとき、

s5249421345715 1 118 834 143863114455t
10sに流れ込む流量 = tから流れ出る流量 (グラフの外から見た場合)
sから流れ出す流量 = tに流れ込む流量 (グラフの中で見た場合)である。
26
この量の最大値(とそのときのフロー)をどう求めればよいか？

最大流問題：解決へのアプローチ• s-t間の適当な道を考え、その流量上限（最小容量）を算出す
る・・・赤色のケース

u101020s

30 2010t• 赤色のフローを流しても余っている別のs-t間の道を考える(逆向きは押し戻すと考える)。この際の、流量上限を算出する・・・
青色のケース20 • 上記を繰り返していけば、徐々vに総流量が増えてやがてそれ以上流せなくなる。これにより、ネットワーク全体の最大流が求27まるのではないか？？

フローの定式化• 辺を流れるフローf(u,v)
uC(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※ 考え方• s-t間の何らかの道を考え、その流量の上限を算出する
10• そのフローfを容量Cから引いた値（残余容10量）を計算し、グラフから差し引く ・・・そのグ30ラフをGfとする
2020 • Gfに対して、同様のことをする（つまり、s-t間の何らかの道を考え、その流量の上限を20算出し、総フローを算出し、容量から差し引いて・・・）
フローに沿って• s-t間の道が無くなれば、終了-20u202030s

1010tv

uu

01010s405010101000

10020t4040s

040 フローに沿って（さらに）v-1020v

200s-t間の道がなくなった(容量>0の弧についてのみ考える)

t40 このとき差し引いている
総フローが求める最大流29練習• フォード・ファルカーソン法を用いて、以下のフローグラフにおける sから t への最大流を求めよ。
1020101020s30

10305040

1020t

102010(*) 辺のラベルは、容量（向きは問わない）を表している。

3050202030s

容量を、まず有向グラフに置き換える

1020

10 10 10 20
3010t
30
1050
1020
10 30
50 1020 1030502050
402020402030 10 10
10 10 2030
202020ss-t間の適当な道を考え、その流量の上限を算出する。

1020

10 10 10 20
3010t
30
1050
10202010 30
50 1020 1030502050
402020402030 10 10
10 10 2030202020s

残余容量 Cf(u,v) = C(u,v) - f(u,v) とし、Gfを作成する

102010 10 10 203010t30
1050102010 3050 1020 103030
20704020204020
10 10 1010 10 05040040

s

Gfにおいて、s-t間の適当な道を考え、その流量の上限を算出する。

102010 10 10 203010t
30
1050
10202010 30
50 1020 10303020704020204020
10 10 1010 10 05040040

s

残余容量 Cf(u,v) = C(u,v) - f(u,v) とし、Gfを作成する

10(*) 本来は f(u,v)はフローの総和
道Pによって作られるフローではない20

10 10 10 2030
10t30
1050
102010 30
50 1020 1030
10409020006040
10 10 1010 10 05040040sGfにおいて、s-t間の適当な道を考え、その流量の上限を算出する。

102010 10 10 203010t301050101020301050 1020 103010409020006040
10 10 1010 10 05040040

s

残余容量 Cf(u,v) = C(u,v) - f(u,v) とし、Gfを作成する

10(*) 本来は f(u,v)はフローの総和
道Pによって作られるフローではない2010 10 10 203010t
301050102010 40
50 1020 1020104090
100070400 20010 10 06040040

s

Gfにおいて、s-t間の適当な道を考え、その流量の上限を算出する。

10（ここでは複数回まとめて表示）

201010 10 10 203010 10t
1030
1010 1050
102010 40
50 1020 1020
10409010007040
0 20010 10 06040040

s

残余容量 Cf(u,v) = C(u,v) - f(u,v) とし、Gfを作成する

0(*) 本来は f(u,v)はフローの総和
道Pによって作られるフローではない

020 20 040
1020500002060
0100 20
20 20
040
00080
40
0 20
0
10 10 060
40
040t
1090

s

Gfにおいて、 s-t間の(Cf>0の辺で作られる)道が存在しないので、終了

0020 20 040
1020500002060
0100 2020 200400008040
0 20
010 10 06040040t
1090s

最大流は以下のフローの総和である。

10101010t

10 102020

各辺が以下のフローを通すとき、sからtに対して最大流が得られる。その流量は1001010s

10101020s301030501020102020t

1040304020

1020t

10 102042

フォード・ファルカーソンのアルゴリズム
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月24日： 平面的グラフ、地図• 7月1日： スキップグラフ• 7月8日： 内容未定
• 7月22日： 試験 13:00 – 14:30 ＠241講義室 (未確定)45