14.Graph2

Size: px

Start display at page:

Download "14.Graph2"

ときらぶり
5 years ago
Views:

1 アルゴリズム論第 (1クラス) 第 14 回 (2018/01/17) 情報学専攻庄野逸 ( 3 号館 313 号室 )

2 本のお題 [ 復習 ] グラフとはグラフの基本概念と語グラフの実現法グラフをいた問題最短経路問題 Dijkstr アルゴリズム,APSP 問題と Floy アルゴリズム有向グラフ (DAG) とトポロジカルソート最全域 (Minimum Spning Tr): Prim と Kruskl のアルゴリズムグラフの 2 重連結性グラフのマッチング ( の紹介 )

3 [ 復習 ] グラフとは? 語説明 (1) 雑把にいえば幾つかの点とそれらを結ぶ線からなる図がグラフ点は, 頂点 (Vrtx)/ 節点 (No) などと呼ぶ頂点集合を V とする.2 頂点 v, w V を結ぶ線 = (v, w) V x V を辺 (g) / 枝 (rnch) と呼ぶ v と w はの端点 (n nos) V: 頂点集合,E: 辺集合とした時, グラフはこれら 2 つの集合できるグラフ G = (V, E) 無向グラフ (Unirct Grph) 辺は頂点を結ぶだけで向き (irction) がない.(v,w) = (w, v) 有向グラフ (Dirct Grph) 辺に向きがある v w (w は v に隣接する ) この場合の辺を弧 (rc) と呼ぶ.

4 [ 復習 ] グラフとは? 語説明 (2) 雑把にいえば幾つかの点とそれらを結ぶ線からなる図がグラフ経路 : 頂点の列 v 1, v 2,... v n. ただし (v i, v i+1 ) E ( 辺が存在する ) 経路のさ : 通過する辺の本数 = 両端も含めた点の個数 -1 つの頂点だけの経路は, さ 0 単純経路 (simpl) 最初と最後以外の全ての頂点が異なる閉路 (cycl, circuit) ある頂点から, その頂点へとる単純な経路有向グラフではさが 1 以上. 無向グラフではさが 3 以上 : つのノードを根とし, どのノードについても, 根からの単純な経路がつだけあるグラフ

5 問題のモデル化とグラフ最短経路問題 A 地点から B 地点へくのにいろいろな経路がある時, 番 ( 安い, 早い, 楽な ) 経路は? トポロジカルソートさな作業程の組合せ ( 順序関係あり ) からなる仕事を仕上げる場合, 全ての程をどのような順番で作業を進めるか? コスト最の極幾つかの町に通信線を引くのに, どの町にも連絡がつき, かつ最もコストかからない法は? グラフの 2 重連結性幾つかの町のネットワークがあったとして, 部が機能しなくなっても全体の連結性が失われないようなネットワークを作るには? グラフマッチングによってこなせる仕事が異なる場合, どの仕事をどのに割り振るか

6 [ 復習 ] グラフの表現実現法 (1) ラベル付き隣接列 (jcncy mtrix) 隣接の集合が V = {v 1,..., v n } の時, 要素が論理型の n x n 列 A において (v i, v j ) E ならば A ij は真, そうでなければ偽とする無向グラフならば列は対称列になるグラフがラベル付きの場合,A の要素を辺のラベルにすると良い c c

7 [ 復習 ] グラフの表現実現法 (2) 隣接リスト (jcncy list) 各頂点において隣接する頂点のリストを保持リストは連結リストやカーソルによって実現 c c

8 [ 復習 ] 最短経路問題とダイクストラアルゴリズム (1) (Dijkstr) : V = {1, 2,...,n} E (i, j) E C(i, j) ( (i, j) C(i, j) = ) : 1 j(= 2,...,n) (j)... (1) S := {1}; or j := 2 to n o (j) :=C(1,j); (2) n 1 (S = V ) (2-) S (u) u (2-) S := S { u }; (2-c) u (u, v) E (v) min( (v), (u) +C(u, v)); (v u )

9 [ 復習 ] 最短経路問題とダイクストラアルゴリズム (2) 1 から到達するためのコスト 1. 経由地 2, (u=2) = 10 S = {1, 2}, 更新 v= 3 2. 経由地 4, (u=4) = 30 S = {1, 2, 4}, 更新 v = 3, 5 3. 経由地 3, (u=3) = 50 s = {1, 2, 3, 4}, v = 5 4. 残った 5 を始点とする弧がないので終了

10 最短経路問題の解法と計算量隣接列による表現 n 個の要素の集合 S をビットベクトルで表し,(j) および C(i, j) を, そのまま各々 1 次元および 2 次元の配列で表すのが番簡単ステップ (2-) およびベクトル要素の操作の計算量は, それぞれ O(n) 全体で O(n 2 ) 計算量を良くするための実現法隣接リスト表現. 各点からの辺を連結リストで保持 (u) を優先度とするヒープを考える. 但しヒープノードには, 優先度とグラフの頂点番号 u の組を保持ヒープの要素数は n ステップ (2-) における要素の選択 (DltMin) の間, ステップ (2-c) で (v) の値が変更された場合のヒープ内の位置変更 (insrt) も間は O(log n). ステップ (2-) は n 回, (2-c) は E ( 辺の数 ) 般には E > n なので, 全体の計算量は O( E log n)

11 最短経路問題 : 全ての頂点つの最短経路 (1) APSP 問題出発点をつに限定せずに, グラフ上の任意の 2 頂点について最短経路を求める問題を APSP(All Pirs Shortst Pths) 問題と呼ぶダイクストラアルゴリズムを全頂点を始点にして実する隣接列を使うのならばフロイド (Floy) アルゴリズムも n x n 隣接列 A を考える. 対要素 A ii = 0, それ以外は A ij = C(i,j) k = 1 n i = 1 n j = 1 n で 3 重ループを回す A ij = min( A ij, A ik + A kj ) k 回操作後の A ij は頂点 i から j への経路のうち k よりきい番号の頂点を通過しないものの最短距離上の代で値が変更されるのは, 頂点 i から j への経路が k を通過することにより短くなる場合. 経路も求めたければ i-j 間の途中経路を記録する n x n 列 P も意し, 上の代で値が変化する場合 P[i, j] = k とすれば良い

12 最短経路問題 : 全ての頂点つの最短経路 (2) APSP 問題出発点をつに限定せずに, グラフ上の任意の 2 頂点について最短経路を求める問題を APSP(All Pirs Shortst Pths) 問題と呼ぶフロイドのアルゴリズム

13 最短経路問題 : 全ての頂点つの最短経路 (3) i から j までの経路があるか? だけを知るには, 要素が真偽値のみの隣接列の推移的閉包を計算する (Wrshll アルゴリズム ) 有向グラフの中 : 離率が最の頂点 ( 最も遠い頂点までの距離が最もさい頂点 ) ある頂点の離率 = mx { w から v への最短距離 } フロイドアルゴリズムの実終了後に得られた A をいると良い v の離率 = mx { A uv } ( 第 v 列中の最値 ) 練習問題有向グラフの頂点が V = {,,c,, } で 7 本だけある弧のコストが C(,) = C(, ) = 1, C(, c) = C(c, ) = 2, C(, c) = 3, C(c, ) =4, C(, ) =5 としたとき,APSP 問題をとき, 各頂点の離率とグラフの中を求めなさい

14 幅優先探索 (Brth First Srch) と深さ優先探索 (Dpth First Srch) BFS アルゴリズム (G, s) 概略グラフ G の s 以外の全ノードの未達とする Enq(Q, s) s c whil Q!= 空集合 v = Dq(Q) g h or u v の隣接ノード u の到達距離 = v の到達距離 +1 Enq(Q, u) v に到達済みのマークをれる Dijkstr アルゴリズムと似ている

15 幅優先探索 (Brth First Srch) と深さ優先探索 (Dpth First Srch) DFS アルゴリズム (G, s) 概略 ( 再帰版 ) s に処理開始マークをれる or u s の隣接ノードかつ未処理開始 s DFS アルゴリズム (G, u) s に処理終了マークをれる g h (3/) (2/9) (1/10) (11/1) s g h 複数の構造森を構成する弧辺先祖に戻る弧後退弧を跨ぐ弧交差弧孫以降への弧前進弧 (7/8) (4/5) (12/13) (14/15)

16 閉路の無い有向グラフ (Dirct Acyclic Grph)DAG 算術式の共通部分式 ((+) * c) * (((+)*c) + ((+)+)*(+)) 式の値を計算する場合, 共通部分式の計算を度やって覚えておけば, 同じ計算を繰り返さずに済む閉路があるかどうか = 深さ優先探索で後退弧に出会うか? グラフをなぞる頂点間に順序を設け, 頂点毎に訪問済みか否かのマークをいれる深さ優先の極森 (Spnning Tr): 深さ優先探索のの弧全体深さ優先探索の極森の中で先祖の頂点に向かう弧を後退弧と呼ぶ交差弧は先祖でも孫でも無い頂点に向かう弧

17 DFS と極森

18 トポロジカルソートトポロジカルソート : グラフの列化.DAG の頂点に線形順序を与え, 頂点 i から頂点 j への弧があれば, その線形順序の中で i < j とする作業 DFS で終了時刻の降順に並べると,DAG の場合, 印が左から右へ並ぶのでトポロジカルソートと呼ぶ左図の DAG のトポロジカルソートを考えてなさい

19 無向グラフの応 : Minimumcost Spnning Tr 最全域 (Miniml cost Spnning Tr) 幾つかの節点と 2 節点を結ぶ為のコストが与えられた時, 最コストで全ての節点を結ぶ連結グラフグラフ G の全域 : G の全ての頂点を連結する由経路 v 1... v n は v 1 と v n を連結する連結グラフ (connct grph): 全ての頂点の対が連結されている由 : 閉路の無い連結グラフ全域のコスト = 辺のコストの和

20 MST を求めるアルゴリズム Prim のアルゴリズム現在のと, そのに含まれない頂点を結ぶ辺で, 重みが最のものをに加えて育てていく O( V 2 ) Kruskl のアルゴリズムの集合で,2 つのを結ぶ辺の内で, 重み最のものを加えることでつのに繋いでいく

21 MST を求めるアルゴリズム Prim のアルゴリズム (1) Prim のアルゴリズム (Prim) : V = {v i, 1 i n} (v i,v j ) C(v i,v j )( (v i,v j ) C(v i,v j )= ) : T... (1) T := ; ( ) U := {v 1 }; V U w ( V U) U (u, w) C min (w) min (w) = u U : C min (w) :=C(v 1,w), min (w) :=v 1 or w = v 2,...,v n V U. (2) U = V ( n 1 )... O(n 2 ) () U V U U V U (u, v), u U, v V U ( C min (v))...o(n) () U := U {v}; T := T { (u, v)}; C min (v) := ; (c) V U w ( V U) C(v, w) <C min (w) C min (w) :=C(v, w) min (w) :=v;... O(n)

22 Prim のアルゴリズム MST を求めるアルゴリズム Prim のアルゴリズム (2)? : U 1 5 (5) (5) c () (3) () (4) (2) = c (3) () 4 (2) = 1 5 c (3) 4 2 = 1 5 c (3) 4 2 = 1 5 c = c 3 : C min () min () 1 O(n 2 ) 4 2

23 MST を求めるアルゴリズム Kruskl のアルゴリズム (1) Kruskl のアルゴリズム (Kruskl) : V E : T... (1) T := ; ( ) S := E ( ) ; C V ( ) : C := {{v } v V }) (2) C 2 C 2 () S (v 1,v 2 ) () C v 1 v 2 c(v 1 ) c(v 2 ) (c) c(v 1 ) c(v 2 ) C c(v 1 ) c(v 2 ) C (C := C { c(v 1 ),c(v 2 ) } { c(v 1 ) c(v 2 ) };) T (v 1,v 2 ) (T := T { (u, v)};)

24 MST を求めるアルゴリズム Kruskl のアルゴリズム (2) Kruskl のアルゴリズム? c = c = c 4 2 = c 4 2 = c 4 2

25 MST を求めるアルゴリズム Kruskl のアルゴリズム (3) Kruskl のアルゴリズムにおけるデータ表現法辺の集合 S は重みのさい順から要素を取り出していく初期化時に重みのさい順にソートして配列やリストとしても良いし, 全ての要素を使うわけでもないので, 辺の重みで優先順位を付けたヒープをいてもよい O( E log E ) 頂点の集合を要素とする集合 C: V 中の頂点を幾つかに分けて出来た部分集合の集合 (2)-() はある頂点 v がどの部分集合に属するかの in 操作 (2)-(c) は 2 つの部分集合の併合 (mrg) 操作データ構造 : 部分集合は構造が親を指す構造があると良い ( 配列で実現可能, 親の添字を持つ ) 部分集合は要素数を保持し, 根で区別. のさは々 O(log n) c c

26 グラフの 2 重連結性問い : 2 つの頂点間に複数の経路が存在するか? 関節点 (rticultion point): 消去するとグラフが連結になる節点. 連結になる辺は橋 (rig) と呼ぶ関節点を持たないグラフを 2 重連結グラフと呼ぶ関節点を探すには? グラフ G の深さ優先探索を構築し, 掛け順になぞる各頂点について, の弧を孫へと向かうか後退辺により連結する頂点の番号で最の頂点を再帰的に求める深さ優先の根は, 弧が 2 以上あれば関節点. 根でない頂点は到達可能名頂点の番号が頂点の番号以上でれば関節点 ( ) c g

27 グラフのマッチング 2 部グラフ (iprtit grph): 頂点が互いに素な ( 共通部分のない )2 つの集合に分割され, 辺は 2 つの部分集合間を結ぶものに限られるグラフグラフ G(V, E) が与えられた時, 辺の集合 E の部分集合で, どの 2 本の辺も V の同じ頂点に接続していないものをマッチングと呼ぶ ( 頂点の対応づけで頂点に重複の無いもの ) 最マッチングマッチングにおいて, 最も多くの辺をもの完全マッチング全ての頂点がいずれかの辺の端点になっている完全マッチングは最マッチングを表す頂点の集合と, 同時に処理しないといけない仕事を表す頂点集合があって, 担当可能な対応関係を辺とするとそれは 2 部グラフとなる. 最効率で仕事をしようとすると最マッチングを解く必要が出て来る

28 最マッチングを求める (Hopcrot-Krp の概要 ) マッチング M に対し M に関する増加路 : M 中のどの辺の端点にもなっていない 2 つの頂点を連結する経路のうち辺が本おきに M に含まれるもの M と M に関する増加路の辺の集合 P との排他的論理和 M P をもとめ, それを新たな M とするという操作を増加路がつからなくなるまで繰り返す 1. 2 M ( (1,), (2,), (3,), (4,c)) c 2. 5? c-4-2 or 5-1 c-4 ( ) c 3. ( ) c

14.Graph2

14.Graph2 (1 ) 14 (2018/01/17) 1. ) ( 3 u TF TGo] rf TG i T D gk sgk M gkf M pj T FS [ K PAS tl ) : 2 F ( G M TG mn TG Gy [ ] (1) swve x G N h G U n v, : = r U p v c, v, h, =, o 2 / p, v c ( o c c ), ( g /: ) o