有限幾何学 第 2 回. 有限幾何学 第 2 回 1. 様々なグラフの例 2. 道と最短経路問題 1. 用語の説明 2. 最短経路問題 3. ダイキストラのアルゴリズム.

Presentation on theme: "有限幾何学 第 2 回. 有限幾何学 第 2 回 1. 様々なグラフの例 2. 道と最短経路問題 1. 用語の説明 2. 最短経路問題 3. ダイキストラのアルゴリズム."— Presentation transcript:

1 有限幾何学 第 2 回

2 有限幾何学 第 2 回 1. 様々なグラフの例 2. 道と最短経路問題 1. 用語の説明 2. 最短経路問題 3. ダイキストラのアルゴリズム

3 1. 様々なグラフの例

4 1 様々なグラフの例 多重辺： 異なる 2 頂点を結ぶ 2 本以上の辺 ループ： 同じ 1 つの頂点を結ぶ辺 単純グラフ：多重辺とループを持たないグラフ ⇐ルー プ 多重辺⇒ 多重辺とループを持つグラフ

5 1 様々なグラフの例 グラフ G に対し，部分グラフ，誘導部分グラフ とは ＊違いに注意

6 1 様々なグラフの例 部分グラフ： V(H) ⊆ V(G) ， E(H) ⊆ E(G) を満たすグラフ H を G の部分グラフとい う 特に， V(H)=V(G) となるとき， H を G の全域部分グラフという G G の部分グラフ G の全域 部分グラフ u v w x y z u v x y z u v x y z w

7 1 様々なグラフの例 W ⊆ V(G) によって誘導された G の誘導部分グラフ G ： V( G )=W, E( G )={xy: x,y ∈ W, xy ∈ E(G)} であるグラフ {u,v,y,z} によって誘導 {y,z,v,w} によっ て誘導 G された誘導部分グラフ された誘 導部分グラフ u v w x y z u v y z v w y z

8 1 様々なグラフの例 完全グラフ， 2 部グラフ，完全 2 部グラフ， 道，閉路，車輪，空グラフ， 正則グラフ， r- 正則グラフ とは

9 1 様々なグラフの例 完全グラフ：任意の相異なる 2 頂点が隣接しているグラフ 位数 l の完全グラフは K l で表される K 6

10 1 様々なグラフの例 2 部グラフ： V(G)=V 1 ∪ V 2, V 1 ∩ V 2 = ∅ E(G) ⊆ {xy: x ∈ V 1, y ∈ V 2 } で表されるグラフ V 1 と V 2 を G の部集合という V 1 ={u,v,w}, V 2 ={a,b,c,d} uvw a b cd

11 1 様々なグラフの例 完全 2 部グラフ： V(G)=V 1 ∪ V 2, V 1 ∩ V 2 = ∅ E(G)={xy: x ∈ V 1, y ∈ V 2 } で表されるグラフ |V 1 |=l, |V 2 |=m のとき， K l,m で表される V 1 ={u,v,w}, V 2 ={a,b,c,d} |V 1 |=3, |V 2 |=4 K 3,4 uvw a b cd

12 1 様々なグラフの例 道： P n 閉路： C n 車輪： W n 空グラフ：辺がないグラフ C 6 W 7 P 4

13 正則グラフ：全ての頂点の次数が同じであるグラフ r- 正則グラフ：各頂点の次数が r の正則グラフ 5- 正則グラフ 3- 正則グラフ 1 様々なグラフの例

14 定理 任意のグラフ G に対し， G を誘導部分グラフとして含む正則グラフが存在する． グラフ G を誘導部分グラフとして含む正則グラフ H の構成方法の例 ⇒ ⇒ G H

15 1 様々なグラフの例 その他の名前の付いたグラフ http://en.wikipedia.org/wiki/Gallery_of_named_graphs

16 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 で表す

17 1 様々なグラフの例 同型の例：下の 3 つのグラフは同じ色の頂点どうしを 対応させることにより同型であることが分 かる ≌ ≌

18 2. 道と最短経路問題

19 2.1 用語の説明 x 0 -x l 歩道： e i =x i x i+1 ∊ E(G) (0 ≦ i ≦ l-1) のとき， P ： x 0 e 0 x 1 e 1 x 2 e 3 ・・・ x l-1 e l-1 x l を， x 0 を始点， x l を終点とする x 0 -x l 歩道という． 2 点間を結ぶ辺が 1 本しかないときは， P ： x 0 x 1 x 2 ・・・ x l-1 x l と表すこと が多い. 注意： x 0 -x l 歩道は， 同じ頂点や辺を何度通っても よい u v w x y z o p

20 2.1 用語の説明 x 0 -x l 歩道： e i =x i x i+1 ∊ E(G) (0 ≦ i ≦ l-1) のとき， P ： x 0 e 0 x 1 e 1 x 2 e 3 ・・・ x l-1 e l-1 x l を， x 0 を始点， x l を終点とする x 0 -x l 歩道という． 2 点間を結ぶ辺が 1 本しかないときは， P ： x 0 x 1 x 2 ・・・ x l-1 x l と表すこと が多い. 左図での u-x 歩道の例 uzuvwpowx uvwpowx uzyx u v w x y z o p

21 2.1 用語の説明 x 0 -x l 小道： x 0 -x l 歩道で同じ辺を含まないもの x 0 -x l 道： x 0 -x l 歩道で同じ頂点を含まないもの 左図での u-x 小道の例 uzuvwpowx uvwpowx uzyx u v w x y z o p

22 2.1 用語の説明 x 0 -x l 小道： x 0 -x l 歩道で同じ辺を含まないもの x 0 -x l 道： x 0 -x l 歩道で同じ頂点を含まないもの 注意：道⇒小道⇒歩道 左図での u-x 道の例 uzuvwpowx uvwpowx uzyx u v w x y z o p

23 2.1 用語の説明 歩道 P に含まれる辺の数を P の長さという． グラフの 2 点 u,v に対して， 最短の u-v 道の長さを u と v の距離といい， d G (u,v) で表す． uzuvwpowx ：長さ 8 uvwpowx ：長さ 6 uzyx ：長さ 3 uwx: 長さ 2 d G (u,x)=2 u v w x y z o p

24 2.1 用語の説明 重み付きグラフ：グラフの各辺 e に重みと呼ばれる実数値 w(e) が割り当てられているグラフ グラフ及び部分グラフの重み：含まれている辺の重みの総和 w(u,v) ：重みが最小の u-v 道の重み w(u,x)=3 u v w x y z o p 2 3 15 4 1 2 2 3 4

25 2.1 用語の説明 重み付きグラフ：グラフの各辺 e に重みと呼ばれる実数値 w(e) が割り当てられているグラフ グラフ及び部分グラフの重み：含まれている辺の重みの総和 w(u,v) ：重みが最小の u-v 道の重み 注意：全ての辺の重みが 1 のとき， グラフの重み =|E(G)| で w(u,v)=d G (u,v) となる

26 5 4 3 2 6 2 2 6 4 xy 2.2 最短経路問題 最短経路問題： 重み付きグラフの 2 頂点間の道で 重みが最小となるものを求める問題

27 5 4 3 2 6 2 2 6 4 xy 2.2 最短経路問題 最短経路問題： 重み付きグラフの 2 頂点間の道で 重みが最小となるものを求める問題 w(x,y)=10

28 2.2 最短経路問題 最短経路問題： 重み付きグラフの 2 頂点間の道で 重みが最小となるものを求める問題 ある 2 点間の距離や移動する時間を重みと 捉えることにより，いろいろと応用が可能 応用例：カーナビ， 鉄道の経路案内（駅すぱあと，駅探， NAVITIME ） 全経路を調べなくても効率的に最短経路を求めることができ る アルゴリズムが知られている

29 2.3 ダイキストラのアルゴリズム ダイキストラ 法 ある頂点 x と x 以外の任意の頂点 y に対して， 重み最小の x-y 道とその重さを求めるアルゴリズム 入力：重み付きグラフ G と始点 x 出力： x 以外の任意の頂点 y に対する 重み最小の x-y 道とその重み

30 2.3 ダイキストラのアルゴリズム ダイキストラ 法 5 4 3 2 6 2 2 6 4 x 入力

31 2.3 ダイキストラのアルゴリズム ダイキストラ 法 5 4 3 2 6 2 2 6 4 x 0 5 4 2 10 6 出力

32 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 とする） ダイキストラ 法

33 5 4 3 2 6 2 2 6 4 x 2.3 ダイキストラのアルゴリズム

34 5 4 3 2 6 2 2 6 4 x 0 ∞ ∞ ∞ ∞ ∞ 1. L(x)=0, L(y)=∞ ( ∀ y ∈ V(G)-{ x }), T= 空グラフ とする

35 5 4 3 2 6 2 2 6 4 x 0 ∞ ∞ ∞ ∞ ∞ 2.3 ダイキストラのアルゴリズム 2.1. L(v)= min {L(u): u ∈ V(G)-V(T)} となる v ∈ V(G)-V(T) を探す

36 5 4 3 2 6 2 2 6 4 x 0 5 4 2 ∞ ∞ 2.3 ダイキストラのアルゴリズム 2.3. uv ∈ E(G) となる任意の u ∈ V(G)-V(T) に対して， L(u)>L(v)+w(uv) ならば L(u)=L(v)+w(uv) とする

37 5 4 3 2 6 2 2 6 4 x 0 5 4 2 ∞ ∞ 2.3 ダイキストラのアルゴリズム 2. 4. T=x とする

38 5 4 3 2 6 2 2 6 4 x 0 5 4 2 ∞ ∞ 2.3 ダイキストラのアルゴリズム 2.1. L(v)= min {L(u): u ∈ V(G)-V(T)} となる v ∈ V(G)-V(T) を探す

39 5 4 3 2 6 2 2 6 4 x 0 5 4 2 ∞ ∞ 2.3 ダイキストラのアルゴリズム 2.2. L(v)=L(v’)+w(v’v) となる v’ ∈ V(T) を探す

40 5 4 3 2 6 2 2 6 4 x 0 5 4 2 ∞ 8 2.3 ダイキストラのアルゴリズム 2.3. uv ∈ E(G) となる任意の u ∈ V(G)-V(T) に対して， L(u)>L(v)+w(uv) ならば L(u)=L(v)+w(uv) とする

41 5 4 3 2 6 2 2 6 4 x 0 5 4 2 ∞ 8 2.3 ダイキストラのアルゴリズム 2. 4. T=T+v’v とする

42 5 4 3 2 6 2 2 6 4 x 0 5 4 2 ∞ 8 2.3 ダイキストラのアルゴリズム

43 5 4 3 2 6 2 2 6 4 x 0 5 4 2 ∞ 8

44 5 4 3 2 6 2 2 6 4 x 0 5 4 2 ∞ 6

45 5 4 3 2 6 2 2 6 4 x 0 5 4 2 ∞ 6

46 5 4 3 2 6 2 2 6 4 x 0 5 4 2 ∞ 6

47 5 4 3 2 6 2 2 6 4 x 0 5 4 2 ∞ 6

48 5 4 3 2 6 2 2 6 4 x 0 5 4 2 11 6 2.3 ダイキストラのアルゴリズム

49 5 4 3 2 6 2 2 6 4 x 0 5 4 2 11 6 2.3 ダイキストラのアルゴリズム

50 5 4 3 2 6 2 2 6 4 x 0 5 4 2 11 6 2.3 ダイキストラのアルゴリズム

51 5 4 3 2 6 2 2 6 4 x 0 5 4 2 11 6 2.3 ダイキストラのアルゴリズム

52 5 4 3 2 6 2 2 6 4 x 0 5 4 2 10 6 2.3 ダイキストラのアルゴリズム

53 5 4 3 2 6 2 2 6 4 x 0 5 4 2 10 6 2.3 ダイキストラのアルゴリズム

54 5 4 3 2 6 2 2 6 4 x 0 5 4 2 10 6 2.3 ダイキストラのアルゴリズム

55 5 4 3 2 6 2 2 6 4 x 0 5 4 2 10 6 2.3 ダイキストラのアルゴリズム

56 5 4 3 2 6 2 2 6 4 x 0 5 4 2 10 6 2.3 ダイキストラのアルゴリズム

57 提出課題 2 教科書： P.27 問 1.27, 1.28, 1.29 P.20 問 1.23, 1.24 のグラフに対して， a 以外の任意の頂点 y に対して， 重み最小の a-y 道とその重みを求めよ （答えのみでよいです）