H28 グラフ理論 - Donald Home Page

用語の補足

u
無向グラフ・有向グラフ
無向グラフの辺：{u,v} = {v,u}
有向グラフの辺： (u,v) ≠ (v,u)
H28 グラフ理論
u
{u,v}
(u,v)
v
v
単純グラフ・多重グラフ
これ以後特に断りがない限り
グラフは単純グラフを意味する

ループ

―第2回―
最も短い道を求める
多重辺
重み付きグラフの最短経路問題

重みなしグラフ・重み付きグラフ
3
1
重み無し
1
1.2: 道と最短経路問題
重み付き
2
最短経路の単調性
与えられたグラフで，２頂点を結ぶ最も
短い経路を求める問題
AからBの最短経路の個数
（各格子点に付けられた
整数値）
5
JR浜松町駅から東京ドーム（水道橋）へ行く
最短(あるいは最も乗り継ぎが少ない)ルートは？
1
A
営団
地下鉄路線図
1
都営
地下鉄路線図
3
14
42
14
28
2
5
9
14
2
3
4
5
1
1
1
1
B
このような後戻りする経路が
最短になることはないので
この性質を用いて最短経路の
数を求めることができ，一般の
グラフにおいても同様
4
1
グラフの部分構造
グラフの部分構造
グラフ G=(V,E) の頂点と辺を交互に並べた列
P: v1 e1 v2 e2 v3 e3 … vn-1 en-1 vn
を考える．このうち各辺が隣同士と接続しているものを
G の v1-vn歩道と呼ぶ．このとき v1を始点，vnを終点という．
v1
G
v3
e7
v6
v1
e1
e3
e2
e5
•すべての辺が異なる歩道を小道という．
•すべての頂点が異なる小道を道という．
•v1=vnである小道を回路という．
•v1=vnである道を閉路という．
v4
v2
v3
e4 e
6
e7
v5
e8
v6
e1
e3
v2
e2
e5
v4
e4 e
6
v5
e8
回路(小道)
閉路(道)
歩道の例 P: v1 e1 v2 e2 v3 e5 v4 e4 v2 e6 v5 e8 v6
単純グラフの場合：辺を省略して P: v1 v2 v3 v4 v2 v5 v6 と書いてよい．
5
グラフの部分構造
閉路(道)は回路(小道)でもあるが，逆は成り立たないことに注意する
6
道と最短経路問題(重み無し)
•頂点 u-v 間に道が存在するとき，u と v は連結しているという．
•任意の２頂点が連結しているグラフを連結なグラフという．
•一般のグラフは連結なグラフ(連結成分)の集まりである．
•連結成分からある辺 e を取り除くと非連結となるとき，
その辺 e を橋という．
２つの点
を結ぶ最短の道は？
連結成分
e
連結グラフ
非連結グラフ
(もっとも一般的なグラフ)
橋e
7
8
2
道と最短経路問題(重み無し)
重み無し最短経路問題：
任意のグラフ G と2点 x,y ∈ V(G)が与えられたとき，
道 Pn={x, v1,…, vn, y}のうち，最短の Pn を求める問題．
見かけは最短経路
異なる経路の数は，|V(G)=n| とすると 2n に比例する．
最短経路問題では，それらの経路から最短のものを
できるだけ短時間に発見したい．
V(G)
x
どうすれば，効率的に
最短経路を発見できるか？
y
x-y道かどうかを確かめる
(候補は指数的に大きい)
頂点を取り出す
9
グラフの重み

10
ダイクストラ(Dijkstra)のアルゴリズム
アイディア
点 x から n ステップで到達できる点の
集合Vnを求める．n = 0から出発して，
ある n に対して y ∈ Vn になったら終了．
最短経路問題のバリエーション
 重み無しグラフ：すべての辺が単一距離を表す
(あるいは重みがない)問題
未知の経路
x
 重み付きグラフ：各辺には重みがあり，目的地ま
での重みの総和が最も小さい道を求めたい
v への最短路
v
y
x

どちらも効率的に解ける
v への最短路
x
11
y
E.W. Dijkstra (1930-2002)
1972 A. M. Turing Award
v
y
y への最短路
12
3
初期状態
ダイクストラのアルゴリズム（重みなしの場合）
y
入力：グラフ G=(V,E) と２頂点 x,y
出力：最短の x-y 道
Step1: x と接続している頂点の集合 X を求める
y ∈ X ならば辺 (x,y) を出力して終了
Step2: まだ訪れていない頂点で，v ∈ X と接続している
頂点の集合を求め，新たに X とする
y ∈ X ならば求めた x-y道を出力して終了
x
Step3: y ∈ X となるまで Step2 を繰り返す
13
14
1ステップで到達可能な点
2ステップで到達可能な点
y
y
x
x
X = {すべての }
15
X = {すべての }
16
4
3ステップで到達可能な点
4ステップで到達可能な点
y
y
x
x
X = {すべての }
X = {すべての }
17
18
5ステップで到達可能な点
6ステップで到達可能な点
y
y
x
x
X = {すべての }
19
X = {すべての }
20
5
7ステップで到達可能な点
8ステップで到達可能な点
y
y
x
x
X = {すべての }
X = {すべての }
21
9ステップで到達可能な点
y
22
x-y道の求め方
x から k ステップで到達可能な2つの頂点 u,vがあり，
u,v から1ステップで同じ頂点 w に到達可能ならば，
どちらか一方の経路を記録していればよい
u
kステップ
1ステップ
w
x
x
v
X = {すべての }
23
kステップ
1ステップ
これ以降のパスはどちらから来ても
同じ距離が保証される
※ このようにすると，逆順の辿り方が
一通りに決まる
24
6
x-y間の最短経路（辺数9）
ダイクストラの方法は，すべての路を調べるやり方
に比べて，はるかに効率的である．グラフの頂点数
が n のとき，この方法では，高々 n2 個の路を調べること
で最短経路を求めることができる（効率的な計算が可能）
y
n2 ≪ 2n
素朴な手法に比べて非常に短時間で
答えが求まる！
x
（例えば n=60 の場合でハノイの塔を例に考えてみよ）
25
26
重み付きグラフの条件
より一般的な場合(重み付きグラフ)
問：これまでは頂点間はすべて同じ距離と仮定した．
一般には距離は異なると考えられるが，この場合は，
どのように最短距離を求めればよいか？

重み付きグラフは距離の公理を満たす．


：三角不等式

v
n
d(u,v)
m
距離の違いを数値の
ラベルで表す
u
27
d(u,w)
d(v,w)
w
28
7
重み付きの場合の難しさ
重みなし
重み付き
2
x
一般の場合の解法
y
x
4
y
8
5
y
最適な辺として
これらを選ぶのは
間違い
a
L1
この辺は調べなくてよい
※ 重みの和の大小関係が
途中で入れ替わらない
2
x
2
3
1
b
図のように y に隣接する頂点が3個の
場合, 重み付きの x から y の最短路は
Min{a+L1,b+L2,c+L3}
で計算できる．
c
a, b, cはyに1ステップで到達可能な
頂点とyの間の辺の重み，Liはそれぞれの
頂点への最短経路の重み
L2
L3
x
この問題は，前の場合と同様
にして効率的に計算可能．
y
※ 途中の逆転がある
29
ダイクストラのアルゴリズム（重み付きの場合）
30
実際の例：重み付きの場合
入力：グラフ G=(V,E) と２頂点 x,y
出力：最短の x-y 道
Step1: L(x)=0 (x から x 自身へは重み0で移動可能) とし，
5
2
それ以外の v ∈ V は L(v)=∞ とする
Step3: v=y ならば終了, それ以外ならすべての (v,u) に対して，
7
5
4
4
x
Step2: 全体で最小のラベル L(v) を見つけ, v=y ならば終了
1
9
7
3
y
2
3
u ∈ V かつ L(u) > L(v) + w(e) ならば
L(u) := L(v) + w(e) とする
Step4: V:=V－{v} としてStep2へ戻る
31
※ X:= X+Y のような式は，X+Y を計算して X に代入することを表す．
32
8
実際の例：重み付きの場合
5
∞
2
x
1
4
0
∞
∞
9
∞
7
3
7
5
4
3
∞
y
2
∞
最短の経路：重み11
33
9

Download Report