算法数理工学 第 7 回 定兼 邦彦 1

グラフ グラフ G = (V, E) –V: 頂点 ( 節点 ) 集合 {1,2,…,n} –E: 枝集合, E  V  V = {(u,v) | u, v  V} 無向グラフ – 枝は両方向にたどれる 有向グラフ – 枝 (u,v) は u から v の方向のみたどれる – 注 : 無向グラフは有向グラフで表現できる ( 枝数を倍にする ) 枝には重み ( 長さ ) がついていることもある – なければ全て長さ 1 とみなす

グラフの表現 節点数 n, 枝数 m とする 隣接行列表現 –n 行 n 列の行列 A で表現 – 領域計算量 O(n 2 ) –i 行目は節点 i から出ている枝を表す – 無向グラフなら対称行列 – 対角成分が 1 ⇔ セルフループ

接続行列表現 n 行 m 列の行列 A で表現 行は節点に，列は枝に対応 領域計算量 O(mn) 各枝に対し， – 始点の行に 1 – 終点の行に  1 無向グラフなら両方 1 セルフループは表せない e1e1 e2e2 e3e3 e4e4 e5e5 e6e6 e7e e1e1 e2e2 e3e3 e4e4 e5e5 e6e6 e7e7

疎な有向グラフのデータ構造 グラフが疎  m = o(n 2 ) とする グラフが疎の場合，行列による表現は冗長 各節点 u ごとに，そこから出ている枝 (u,v) をリスト に格納する u は共通なので v だけリストに入れる 枝に重み w がついているときは (v, w) をリストに入 れる 隣接行列を圧縮したようなもの グラフの隣接リスト表現と呼ぶことにする

v 重み E 領域計算量 O(n+m)

7 最小木問題 節点集合 V = {1,2,…,n} と枝集合 {e 1,e 2,…,e m } をもつ連結無向グラフ G = (V,E) に対して， G と 同じ節点集合 V を持ち， E の部分集合 T を枝集 合とするグラフ G’ = (V,T) を考える 各節点 i  V は少なくとも 1 つの枝 e j  T の端点 になっているとする G’ が閉路を含まない連結グラフ，すなわち木 になっているならば， G’ を G の全域木という 各枝 e i  E に長さ a i が与えられているとき， を全域木の長さと定義する 長さ最小の全域木を求める問題

8 貪欲 (greedy) アルゴリズム アルゴリズムの各ステップで，その時点で最善 と 思われる選択を常に行うアルゴリズム 局所的に最善な選択が大局的に最善な解を導く 場合には最適解を与える 貪欲アルゴリズムで解ける問題は比較的簡単な 問題といえる

9 成長法による最適全域木の構成 「繰り返しの各ステップの直前で， A はある最 小全域木の部分集合」というループ不変式を維 持 安全な辺 = それを加えてもループ不変式を満た す A :=  while A は最小全域木ではない A に対して安全な辺 (u,v) を求める A := A  {(u,v)} return A

10 定義 無向グラフ G = (V, E) のカット (S, V  S) とは ， V の分割 辺 (u,v)  E の一方の端点が S にあり，他方 が V  S にあるとき， (u,v) はカット (S, V  S) と交 差するという 辺集合 A に属するどの辺もカットと交差し ないとき，このカットは A を侵害しないと いう カットと交差する辺の中で重み最小の辺を 軽い辺 (light edge) という

11 fg b h a i cd e S VSVS カット 軽い枝 A: 最小全域木の枝の部分集合

12 定理 1: グラフ G = (V, E) のある最小全域木に 含まれる E の任意の部分集合を A ， A を侵害 しない G の任意のカットを (S, V  S) ，そのカッ トと 交差する任意の軽い辺を (u,v) とする．このと き， 辺 (u,v) は A に対して安全である． 証明： A を含む任意の最小全域木 T に対し， ・ T が (u,v) を含む →OK ・ T が (u,v) を含まない →A  {(u,v)} を含む別 の最小全域木 T’ が存在することを示す．

13 T の u から v への経路 p 上の辺に (u,v) を加える と閉路ができる． u と v はカット (S, V  S) の反対 側 にあるから，経路 p 上にこのカットと交差する T の 辺が少なくとも 1 つ存在する． このような辺の 1 つを (x,y) とする． カット (S, V  S) は A を侵害しないから， A は辺 (x,y) を含まない． (x,y) は T における u から v への唯 一 の経路上にあるから， (x,y) を削除すると T は 2 つ の 成分に分かれる．これに (u,v) を加えると新たな 全域木 T’ = T  {(x,y)}  {(u,v)} ができる．

14 y v u x e p (u,v) はカットと交差する軽い辺 (u,v) は T における u から v への唯一の経路 p の辺 T から辺 (x,y) を削除し，辺 (u,v) を加えることにより (u,v) を含む最小全域木 T’ が形成できる．

15 T’ が最小全域木であることを示す． (u,v) はカットと交差する軽い辺であり， (x,y) も この カットと交差するから， w(u,v)  w(x,y) である． w(T’) = w(T)  w(x,y)+w(u,v)  w(T) となるが， T は最小全域木なので w(T)  w(T’). 従って， T’ も最小全域木である． (u,v) が A に対する安全な辺であることを示す． A  T かつ (x,y)  A より， A  T’ である． 従って， A  {(u,v)}  T’ である． T’ は最小全域木なので， (u,v) は安全である．

16 クラスカル法 枝を長さの短い順に 1 つずつ選ぶ それを前に選んだ枝の集合に付け加えたとき に 閉路を生じないならば，その枝を付け加える (0) グラフ G の枝を短い順に並べ，枝の番号を付 け替える． A = {e 1 }, k = 2 とおく． (1) 枝集合 A  {e k } が閉路を含まないならば， A := A  {e k } とする (2)A が G の全域木になっていれば計算終了． さもなければ k := k + 1 としてステップ (1) へ戻 る

18 クラスカル法の計算途中では，枝集合 T は一般 に複数の木の集まりになっている．このような 集合を森と呼ぶ． どの枝を付け加えても閉路ができてしまうよう な森を，全域森と呼ぶ． クラスカル法の正当性を背理法で証明する． 得られた全域木を とし，枝 は の順に付け加えられたとする． が成り立つ T より長さの短い全域木 が別に存在したとする． とする

19 T* の長さは T よりも短いので， となる i が存在する． そのような i の中で最小のものを r とすると 枝集合 からなる部分 グラフ を考える． ただし， には枝が重複して含まれている可能 性もある．また，一般に は連結とは限らな い．

20 命題：枝集合 は部分グラフ の 全域森である． 証明：枝集合 に枝を付け加える段階で， ではなくそれより長い が選ばれていると いうことは， のどれを追加しても閉路が できることを意味する． ( 証明終 ) 枝集合 が の全域森であるため， の任意の森は r 本以上の枝を含まない 一方， は G に対する全域木 T* の枝の一部 であり， でも森になっている．しかしその 枝数は r であるため，矛盾． 以上より，クラスカル法で得られた T は最小木．

21 アルゴリズムの効率的な実現 以下の操作を効率的に実現する必要がある 枝集合 A  {e k } が閉路を含まないならば， A := A  {e k } とする e k = (u,v) の両端点 u, v が A の異なる連結成分 に属している ⇔ A  {e k } は閉路を含まない 「互いに素な集合のためのデータ構造」を用い る

22 互いに素な集合のためのデータ構造 互いに素な動的集合の集合 S={S 1, S 2,…, S k } を扱う make_set(x): 唯一の要素 x をもつ新しい集合を作る –x がすでに別の集合に含まれていてはいけない union(x, y): x と y を含む集合 S x と S y を合併し， それらの和集合を作る．元の集合は S から取り除く． find_set(x): x を含む集合の代表元へのポインタを返す make_set の回数 n と全操作の総実行回数 m で 評価する． –union の回数は n  1 以下

23 連結リストによる表現 各集合を連結リストで表現する リストの先頭のオブジェクトがその集合 の 代表元の役割をする 各オブジェクトは集合の要素，次のオブ ジェクトへのポインタ，代表元に戻るポ インタを持つ 各リストは代表元へのポインタ head とリ ストの最後の要素へのポインタ tail を持つ 9164 head(L) tail(L)

24 make_set(x) と find_set(x) は簡単で O(1) 時間 union(x,y) は ? x のリストを y のリストの最後に追加する場合 –x のリストにあった各オブジェクトの代表元への ポインタを書き換える必要がある –x のリストの長さに比例する時間がかかる  (m 2 ) 時間かかる長さ m の操作列が存在 – 初めに n 回の make_set を実行 – 次に n  1 回の union を実行 (m = 2n  1)

25 このアルゴリズムはどこが悪いのか –union(x,y) で常に x を y の末尾に追加しているので ， x が長いと時間がかかる x と y の短いほうを長いほうの末尾に追加すれ ば 計算量を抑えられる ? – 長さ n/2 同士のリストの併合は  (n) 時間かかるの で 最悪計算量は同じ ならし計算量 (amortized time complexity) で評価 –m 回の操作全体での計算量で評価する 定理 : 長さ m の make_set, union, find_set 操作の 列の実行の計算量は，その中の n 回が make_set のとき， O(m + n log n) である．

26 証明： n 個の各要素に対し，代表元へのポインタ が 更新される回数の上界を求める． ある要素 x において，その代表元ポインタが更新 されるとき， x は常に小さい方の集合に属してい る． 従って，最初に x の代表元ポインタが更新された 時，得られる集合のサイズは 2 以上． 代表元ポインタが k 回更新された後に得られる 集合は，少なくとも 2 k 個の要素を持っている． 要素は n 個しかないので， k  log n.

27 ( 続き ) n 個のオブジェクトを更新するのにかかる総時 間は O(n log n). make_set と find_set 操作は 1 回あたり O(1), m 回の操作全体で O(m). 従って，列全体に対する総時間計算量は O(m + n log n)

28 クラスカルのアルゴリズム mst_kruskal(G, w) 1.A :=  2.for v  V(G) 3. make_set(v) 4. 重み w の順に E の辺をソートする 5.for (u,v)  E ( 重みの小さい順 ) 6. if find_set(u)  find_set(v) then 7. A := A  {(u,v)} 8. union(u,v) 9.return A

29 クラスカル法の計算量 辺のソート : O(m log m) make_set: n 回 find_set: 2m 回 union: n  1 回 素な集合の操作全体で O(m + n log n) m = O(n 2 ) より クラスカル法の計算量は O(m log n)

30 プリム (Prim) のアルゴリズム 最小全域木の部分集合 A を常に連結にしながら 更新していくアルゴリズム A に含まれない点の集合を Q とする 初期状態は Q = V  {r} (r はある任意の点 ) カットは (Q, V  Q) になっている ダイクストラ法に似ている

31 mst_prim(G, w, r) 1.for each u  V(G) d[u] :=  2.d[r] := 0;  [r] := NIL 3.Q := V(G); 4.while Q   5. u := extract_min(Q) 6. for each v  Adj[u] 7. if v  Q かつ w(u,v) < d[v] then 8.  [v] := u 9. d[v] := w(u,v)

d(1)=0 d(2)=  d(3)=  d(4)=  d(5)=  Q = {1,2,3,4,5} d(1)=0 d(2)=50 d(3)=80 d(4)=  d(5)=  Q = {2,3,4,5}

d(1)=0 d(2)=50 d(3)=20 d(4)=15 d(5)=  Q = {3,4,5} d(1)=0 d(2)=50 d(3)=10 d(4)=15 d(5)=30 Q = {3,5}

d(1)=0 d(2)=50 d(3)=10 d(4)=15 d(5)=15 Q = {5} d(1)=0 d(2)=50 d(3)=10 d(4)=10 d(5)=15 Q = {}

35 While ループの各繰り返しの直前では –A = {(v,  [v] | v  V  {r}  Q} – 最小全域木の中にすでに置かれた点は V  Q の点 –v  Q に対し，  [v]  NIL ならば， d[v] <  d[v] は v と最小全域木にすでに置かれた点を結ぶ 軽い辺 (v,  [v]) の長さ 注：集合 A は明示的には持たない アルゴリズムでは d[u] が最小である u  Q を Q から削除する ⇒ (u,  [u]) を A に加える

データ構造の詳細 グラフは隣接リストで表現 Q はヒープで表現．キーは d[  ] d[v] := w(u,v) を行うとき，ヒープも更新す る –v をヒープからいったん削除し， d[v] を更新し てから挿入し直す – 削除を O(log n) 時間で行うために， v がヒープ のどこに格納されているかをサイズ n の配列で 管理 if v  Q の判定は，上記のヒープの拡張を用 いれば定数時間で可能 36

37 プリム法の計算量 extract_min: O(n) 回 各点の隣接点を列挙する処理は，各点について 1 回のみ ⇒ 処理回数は 2m 以下 d の更新 (heap の挿入削除 ): O(m) 回 総計算量 : O(n log n + m log n) = O(m log n) – クラスカル法と同じ d の更新を挿入と削除ではなく，フィボナッチ ヒープ の decrease_key で行うと，総計算量は O(m + n log n)