スライド 1

有限幾何学
第2回
有限幾何学第2回
1. 様々なグラフの例
2. 道と最短経路問題
1. 用語の説明
2. 最短経路問題
3. ダイキストラのアルゴリズム
1. 様々なグラフの例
1 様々なグラフの例
多重辺：
異なる2頂点を結ぶ2本以上の辺
ループ：
同じ1つの頂点を結ぶ辺
単純グラフ：多重辺とループを持たないグラフ
⇐ループ
多重辺⇒
多重辺とループを持つグラフ
1 様々なグラフの例
グラフGに対し，部分グラフ，誘導部分グラフとは
＊違いに注意
1 様々なグラフの例
部分グラフ：
V(H)⊆V(G)， E(H)⊆E(G)を満たすグラフHをGの部分グラフという
特に，V(H)=V(G)となるとき，HをGの全域部分グラフという
G
Gの部分グラフ
Gの全域部分グラフ
v
v
v
u
u
u
w
w
x z
z
y
x
x z
y
y
1 様々なグラフの例
W⊆V(G)によって誘導されたGの誘導部分グラフ<W>G：
V(<W>G)=W, E(<W>G)={xy: x,y ∈W, xy ∈E(G)}であるグラフ
{u,v,y,z}によって誘導 {y,z,v,w}によって誘導
G
された誘導部分グラフされた誘導部分グラフ
v
v
v
u
u
w
x
z
y
w
z
z
y
y
1 様々なグラフの例
完全グラフ，2部グラフ，完全2部グラフ，
道，閉路，車輪，空グラフ，
正則グラフ，r-正則グラフとは
1 様々なグラフの例
完全グラフ：任意の相異なる2頂点が隣接しているグラフ
位数lの完全グラフはKlで表される
K6
1 様々なグラフの例
2部グラフ：V(G)=V1 ∪ V2, V1 ∩ V2=∅
E(G)⊆{xy: x ∈ V1, y ∈ V2} で表されるグラフ
V1とV2をGの部集合という
u
v
w
V1={u,v,w}, V2={a,b,c,d}
a
b
c
d
1 様々なグラフの例
完全2部グラフ： V(G)=V1 ∪ V2, V1 ∩ V2=∅
E(G)={xy: x ∈ V1, y ∈ V2} で表されるグラフ
|V1|=l, |V2|=m のとき，Kl,mで表される
u
v
w
V1={u,v,w}, V2={a,b,c,d}
|V1|=3, |V2|=4
a
b
c
K3,4
d
1 様々なグラフの例
道：Pn
閉路：Cn
車輪：Wn
空グラフ：辺がないグラフ
C6
P4
W7
1 様々なグラフの例
正則グラフ：全ての頂点の次数が同じであるグラフ
r-正則グラフ：各頂点の次数がrの正則グラフ
5-正則グラフ
3-正則グラフ
1 様々なグラフの例
その他の名前の付いたグラフ
http://en.wikipedia.org/wiki/Gallery_of_named_graphs
1 様々なグラフの例
同型：2つのグラフGとHに対し，V(G)からV(H)への全単射 f で，
任意のu,v ∈V(G)に対し，
uv∈E(G) ⇔ f(u)f(v) ∈ E(H)
を満たすものが存在するとき，GとHは同型であるといい，
G ≌ H で表す
1 様々なグラフの例
同型の例：下の3つのグラフは同じ色の頂点どうしを
対応させることにより同型であることが分かる
≌
≌
2. 道と最短経路問題
2.1 用語の説明
x0-xl 歩道：ei=xixi+1∊E(G) (0≦i≦l-1) のとき，
P：x0e0x1e1x2e3・・・xl-1el-1xl を，
x0 を始点，xl を終点とする x0-xl 歩道という．
2点間を結ぶ辺が1本しかないときは，
v
p P： x0x1x2・・・xl-1xl と表すことが多い.
u
w
x
z
y
o 注意：x0-xl 歩道は，
同じ頂点や辺を何度通ってもよい
2.1 用語の説明
x0-xl 歩道：ei=xixi+1∊E(G) (0≦i≦l-1) のとき，
P：x0e0x1e1x2e3・・・xl-1el-1xl を，
x0 を始点，xl を終点とする x0-xl 歩道という．
2点間を結ぶ辺が1本しかないときは，
v
p P： x0x1x2・・・xl-1xl と表すことが多い.
u
w
x
z
y
o
左図での u-x 歩道の例
uzuvwpowx
uvwpowx
uzyx
2.1 用語の説明
x0-xl 小道：x0-xl 歩道で同じ辺を含まないもの
x0-xl 道：x0-xl 歩道で同じ頂点を含まないもの
v
p
u
w
x
z
y
o
左図での u-x 小道の例
uzuvwpowx
uvwpowx
uzyx
2.1 用語の説明
x0-xl 小道：x0-xl 歩道で同じ辺を含まないもの
x0-xl 道：x0-xl 歩道で同じ頂点を含まないもの
注意：道⇒小道⇒歩道
v
p
u
w
x
z
y
o
左図での u-x 道の例
uzuvwpowx
uvwpowx
uzyx
2.1 用語の説明
歩道Pに含まれる辺の数をPの長さという．
グラフの2点u,vに対して，
最短の u-v 道の長さをuとvの距離といい，dG(u,v)で表す．
v
p
u
w
x
z
y
o
uzuvwpowx ：長さ8
uvwpowx：長さ6
uzyx ：長さ3
uwx:長さ2
dG(u,x)=2
2.1 用語の説明
重み付きグラフ：グラフの各辺eに重みと呼ばれる実数値w(e)
が割り当てられているグラフ
グラフ及び部分グラフの重み：含まれている辺の重みの総和
w(u,v)：重みが最小の u-v 道の重み
v
p
2
4 2
3
u
1
w 4 o
3
2
x
z
1
5
y
w(u,x)=3
2.1 用語の説明
重み付きグラフ：グラフの各辺eに重みと呼ばれる実数値w(e)
が割り当てられているグラフ
グラフ及び部分グラフの重み：含まれている辺の重みの総和
w(u,v)：重みが最小の u-v 道の重み
注意：全ての辺の重みが1のとき，
グラフの重み=|E(G)|で w(u,v)=dG(u,v) となる
2.2 最短経路問題
最短経路問題：
重み付きグラフの2頂点間の道で
重みが最小となるものを求める問題
6
5
x
4
2
2
y
2
3
6
4
2.2 最短経路問題
最短経路問題：
重み付きグラフの2頂点間の道で
重みが最小となるものを求める問題
6
5
x
4
2
2
y
2
3
6
4
w(x,y)=10
2.2 最短経路問題
最短経路問題：
重み付きグラフの2頂点間の道で
重みが最小となるものを求める問題
ある2点間の距離や移動する時間を重みと
捉えることにより，いろいろと応用が可能
応用例：カーナビ，
鉄道の経路案内（駅すぱあと，駅探，NAVITIME）
全経路を調べなくても効率的に最短経路を求めることができる
アルゴリズムが知られている
2.3 ダイキストラのアルゴリズム
ダイキストラ法
ある頂点xとx以外の任意の頂点yに対して，
重み最小のx-y 道とその重さを求めるアルゴリズム
入力：重み付きグラフGと始点x
出力：x以外の任意の頂点yに対する
重み最小のx-y 道とその重み
2.3 ダイキストラのアルゴリズム
ダイキストラ法
入力
6
5
2
x
4
2
2
3
6
4
2.3 ダイキストラのアルゴリズム
ダイキストラ法
5
出力
6
5
x
2
0
4
10
4
2
2
3
2
6
4
6
2.3 ダイキストラのアルゴリズム
ダイキストラ法
1. L(x)=0, L(y)=∞ (∀y ∈V(G)-{ x }), T=空グラフとする
2. V(T)=V(G)となるまで以下のループを繰り返す
1. L(v)= min {L(u): u∈V(G)-V(T)}となるv∈V(G)-V(T)を探す
2. L(v)=L(v’)+w(v’v)となるv’∈V(T)を探す
3. uv∈E(G)となる任意のu∈V(G)-V(T)に対して，
L(u)>L(v)+w(uv)ならばL(u)=L(v)+w(uv)とする
4. T=T+v’vとする（T=空グラフのときはT=vとする）
2.3 ダイキストラのアルゴリズム
6
5
2
x
4
2
2
3
6
4
2.3 ダイキストラのアルゴリズム
∞
6
5
x
2
0
∞
4
∞
2
2
3
∞
6
4
∞
1. L(x)=0, L(y)=∞ (∀y ∈V(G)-{ x }), T=空グラフとする
2.3 ダイキストラのアルゴリズム
∞
6
5
x
2
0
∞
4
∞
2
2
3
∞
6
4
∞
2.1. L(v)= min {L(u): u∈V(G)-V(T)}となるv∈V(G)-V(T)を探す
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
∞
4
4
2
2
3
2
6
4
∞
2.3. uv∈E(G)となる任意のu∈V(G)-V(T)に対して，
L(u)>L(v)+w(uv)ならばL(u)=L(v)+w(uv)とする
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
∞
4
4
2
2
3
2
6
4
∞
2. 4. T=xとする
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
∞
4
4
2
2
3
2
6
4
∞
2.1. L(v)= min {L(u): u∈V(G)-V(T)}となるv∈V(G)-V(T)を探す
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
∞
4
4
2
2
3
2
6
4
∞
2.2. L(v)=L(v’)+w(v’v)となるv’∈V(T)を探す
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
∞
4
4
2
2
3
2
6
4
8
2.3. uv∈E(G)となる任意のu∈V(G)-V(T)に対して，
L(u)>L(v)+w(uv)ならばL(u)=L(v)+w(uv)とする
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
∞
4
4
2
2
3
2
6
4
8
2. 4. T=T+v’vとする
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
∞
4
4
2
2
3
2
6
4
8
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
∞
4
4
2
2
3
2
6
4
8
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
∞
4
4
2
2
3
2
6
4
6
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
∞
4
4
2
2
3
2
6
4
6
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
∞
4
4
2
2
3
2
6
4
6
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
∞
4
4
2
2
3
2
6
4
6
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
4
11
4
2
2
3
2
6
4
6
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
4
11
4
2
2
3
2
6
4
6
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
4
11
4
2
2
3
2
6
4
6
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
4
11
4
2
2
3
2
6
4
6
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
4
10
4
2
2
3
2
6
4
6
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
4
10
4
2
2
3
2
6
4
6
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
4
10
4
2
2
3
2
6
4
6
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
4
10
4
2
2
3
2
6
4
6
2.3 ダイキストラのアルゴリズム
5
6
5
x
2
0
4
10
4
2
2
3
2
6
4
6
提出課題2
教科書：
P.27 問1.27, 1.28, 1.29
P.20 問 1.23, 1.24のグラフに対して，
a以外の任意の頂点yに対して，
重み最小のa-y 道とその重みを求めよ
（答えのみでよいです）

Download Report