14.Graph2

アルゴリズム論第⼀

(1

クラス)

第14回

(2018/01/17)

情報学専攻 庄野 逸 (shouno@uec.ac.jp) (_{⻄3号館313号室)}

本⽇のお題

´ [_{復習] グラフとは} ´ グラフの基本概念と⽤語 ´ グラフの実現⽅法 ´ グラフを⽤いた問題 ´ 最短経路問題

Dijkstra _{アルゴリズム，APSP問題と Floyd アルゴリズム}

´ 有向グラフ(DAG) とトポロジカルソート

´ 最⼩全域⽊(Minimum Spaning Tree): Prim と Kruskal のアル ゴリズム

´ グラフの2重連結性

[

_{復習] グラフとは？}

⽤語説明(1)

´ ⼤雑把にいえば「幾つかの点とそれらを結ぶ線からなる図」がグラフ ´ 点は，頂点(Vertex)/節点(Node) などと呼ぶ ´ 頂点集合を V とする．2頂点 v, w ∈ V を結ぶ線 e = (v, w) ∈ V x V を 辺(edge) / 枝(branch) と呼ぶ 「v と w は e の端点(end nodes)」 ´ V: _{頂点集合，E: 辺集合とした時，グラフはこれら2つの集合できる} グラフG = (V, E) ´ 無向グラフ(Undirected Graph) 辺は頂点を結ぶだけで向き(direction)がない．(v,w) = (w, v) ´ 有向グラフ(Directed Graph) 辺に向きがある v → w (w は v に隣接する) この場合の辺を「弧 (arc)」と呼ぶ．

[

_{復習]グラフとは？}

⽤語説明(2)

´ ⼤雑把にいえば「幾つかの点とそれらを結ぶ線からなる図」がグラフ ´ 経路: 頂点の列 v₁, v₂, ... v_{n ．ただし (vi}, v_i+1) ∈ E _{（辺が存在する)} ´ 経路の「⻑さ」: 通過する辺の本数＝両端も含めた点の個数-1 ⼀つの頂点だけの経路は，⻑さ０ ´ 「単純経路」(simple) 最初と最後以外の全ての頂点が異なる ´ 「閉路」(cycle, circuit) ある頂点から，その頂点⾃⾝へと⾄る単純な経路 有向グラフでは⻑さが１以上．無向グラフでは⻑さが３以上 ´ ⽊: 「⼀つのノードを根とし，どのノードについても，根からの単純な経 路が⼀つだけあるグラフ」

問題のモデル化とグラフ

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

[

_{復習]グラフの表現・実現⽅法(1)}

´ ラベル付き隣接⾏列(adjacency matrix) ´ 隣接の集合が V = {v₁, ..., v_n} _{の時，要素が論理型の n x n ⾏列 A において} (v_i, v_j) ∈ E _{ならば Aijは真，そうでなければ偽とする} ´ 無向グラフならば⾏列は対称⾏列になる ´ グラフがラベル付きの場合，Aの要素を辺のラベルにすると良い

アルゴリズム論第一

✬

✫

✩

✪

グラフの表現・実現法

• (

ラベルつき

)

隣接行列

(adjancency matrix)

◦

頂点の集合が

V =

_{v

1

, v

2

, ..., v

n

}

の時，要

素が論理型の

n

_{× n}

行列

A

において，

(v

i

, v

j

)

∈ E

ならば

A[i, j]

は真，さもなくば

偽とする

◦

無向グラフならば，行列は対称

◦

グラフがラベルつきの場合，

A

の要素を辺の

ラベルにすればよい

a

b

c

d

e

f

a

_◦

_◦

b

_◦

_◦

c

d

e

f

•

隣接リスト

(adjancency list):

各頂点について，隣接する頂点

のリストを保持．

リストは，連結リストやカーソ

ルにより実現

f

e

d

c

b

a

_•

✟✟

✟

✯

b

_•

✲

c

✑✑

•

✏✏

✏

✶

d

•

✲

_e

_✑✑

•

•

•

•

❍❍

❍

❥

d

✑✑

[

練習問題

7-2]:

前のグラフに対す

る行列と図を完成させよ．

第 12 回 Page 5

[

_{復習]グラフの表現・実現⽅法(2)}

´ 隣接リスト(adjacency list) ´ 各頂点において隣接する頂点のリストを保持 ´ リストは連結リストやカーソルによって実現

アルゴリズム論第一

✬

✫

✩

✪

グラフの表現・実現法

• (

ラベルつき

)

隣接行列

(adjancency matrix)

◦

頂点の集合が

V =

_{v

1

, v

2

, ..., v

n

}

の時，要

素が論理型の

n

_{× n}

行列

A

において，

(v

i

, v

j

)

∈ E

ならば

A[i, j]

は真，さもなくば

偽とする

◦

無向グラフならば，行列は対称

◦

グラフがラベルつきの場合，

A

の要素を辺の

ラベルにすればよい

a

b

c

d

e

f

a

_◦

_◦

b

_◦

_◦

c

d

e

f

•

隣接リスト

(adjancency list):

各頂点について，隣接する頂点

のリストを保持．

リストは，連結リストやカーソ

ルにより実現

f

e

d

c

b

a

_•

✟✟

✟

✯

b

_•

✲

c

✑✑

•

✏✏

✏

✶

d

•

✲

_e

_✑✑

•

•

•

•

❍❍

❍

❥

d

✑✑

[

練習問題

7-2]:

前のグラフに対す

る行列と図を完成させよ．

第 12 回 Page 5

[

_{復習]最短経路問題と}

ダイクストラアルゴリズム(1)

アルゴリズム論第一 (村尾)

✬

✫

✩

✪

復習

:

最短経路問題とダイクストラのアルゴリズム

最短経路問題に対するダイクストラ (Dijkstra) のアルゴリズム

✓

✏

入力 : 有向グラフの頂点の集合 V = _{{1, 2, ..., n}} と重みつきの辺の集合 E．辺 (i, j) _{∈ E} の重みを C(i, j) とする (但し，(i, j) に弧が存在しなければ C(i, j) = _∞ とする)． 出力 : 頂点 1 から頂点 j(= 2, ..., n) への最短経路のコスト d(j) . . . . (1) 【初期化】頂点の集合 S := _{1}; for j := 2 to n do d(j) := C(1, j); (2) 以下の操作を n _{− 1} 回 (S = V となるまで) 繰り返す (2-a) S に含まれない頂点から，d(u) が最小であるような頂点 u を選ぶ (2-b) S := S _{∪ { u };}

(2-c) u を始点とするすべての辺 (u, v) _{∈ E} に対し，d(v) _{← min( d(v), d(u) + C(u, v) );} (v への経路は，現在の経路よりも u を通過した方がコストが小さい時にコストを更新)

✒

✑

2

❄

50 3

✛

10

✛

20 1

❄

30 4

✲

100

$

$$

✒

60 5

✏✏

✏✏

✏

✏

✶

10 1 から到達するためのコスト 2 3 4 5 d 10 ∞ 30 100 1. 経由地 2, d(u = 2) = 10 S = _{{1, 2},} 更新：v = 3 10 60 30 100 2. 経由地 4, d(u = 4) = 30 S = {1, 2, 4}, 更新：v = 3, 5 10 50 30 90 3. 経由地 3, d(u = 3) = 50 d(u = 3) = 50, S = {1, 2, 3, 4}, v = 5 10 50 30 60 残った 5 を始点とする弧がないので終わり 第 13 回 Page 5 アルゴリズム論第一 (村尾)

✬

✫

✩

✪

復習

:

最短経路問題とダイクストラのアルゴリズム 最短経路問題に対するダイクストラ (Dijkstra) のアルゴリズム

✓

✏

入力 : 有向グラフの頂点の集合 V = _{{1, 2, ..., n}} と重みつきの辺の集合 E．辺 (i, j) _{∈ E} の重みを C(i, j) とする (但し，(i, j) に弧が存在しなければ C(i, j) = _∞ とする)． 出力 : 頂点 1 から頂点 j(= 2, ..., n) への最短経路のコスト d(j) . . . . (1) 【初期化】頂点の集合 S := _{1}; for j := 2 to n do d(j) := C(1, j); (2) 以下の操作を n_{− 1} 回 (S = V となるまで) 繰り返す (2-a) S に含まれない頂点から，d(u) が最小であるような頂点 u を選ぶ (2-b) S := S _{∪ { u };}

(2-c) u を始点とするすべての辺 (u, v) _{∈ E} に対し，d(v) _{← min( d(v), d(u) + C(u, v) );} (v への経路は，現在の経路よりも u を通過した方がコストが小さい時にコストを更新)

✒

✑

2

❄

50 3

✛

10

✛

20 1

❄

30 4

✲

100

$

$$

✒

60 5

✏✏

✏✏

✏

✏

✶

10 1 から到達するためのコスト 2 3 4 5 d 10 _∞ 30 100 1. 経由地 2, d(u = 2) = 10 S = _{{1, 2},} 更新：v = 3 10 60 30 100 2. 経由地 4, d(u = 4) = 30 S = _{{1, 2, 4},} 更新：v = 3, 5 10 50 30 90 3. 経由地 3, d(u = 3) = 50 d(u = 3) = 50, S = _{{1, 2, 3, 4}, v = 5} 10 50 30 60 残った 5 を始点とする弧がないので終わり 第 13 回 Page 5

[

_{復習]最短経路問題と}

ダイクストラアルゴリズム(2)

´ 1_{から到達するためのコスト} 1. _{経由地 2, d(u=2) = 10} S = {1, 2}, _{更新 v= 3} 2. _{経由地 4, d(u=4) = 30} S = {1, 2, 4}, _{更新 v = 3, 5} 3. _{経由地 3, d(u=3) = 50} s = {1, 2, 3, 4}, v = 5 4. _{残った５を始点とする弧がないので終了}

最短経路問題の解法と計算量

´ 隣接⾏列による表現 ´ n _{個の要素の集合 S をビットベクトルで表し，d(j) および C(i, j)を，その} まま各々１次元および２次元の配列で表すのが⼀番簡単 ´ ステップ(2-a) およびベクトル要素の操作の計算量は，それぞれ O(n) 全体で O(n2₎ ´ 計算量を良くするための実現法 ´ 隣接リスト表現．各点からの辺を連結リストで保持 ´ d(u) _{を優先度とするヒープを考える．} 但しヒープノードには，優先度とグラフの頂点番号 u の組を保持 ヒープの要素数は n ´ ステップ(2-a) における要素の選択(DeleteMin) の⼿間， ステップ(2-c) で d(v) の値が変更された場合のヒープ内の位置変更 (insert) _{も⼿間は O(log n)．} ´ ステップ(2-a) は n 回, (2-c) は |E| (辺の数)

最短経路問題: 全ての頂点つの

最短経路(1)

´ APSP_問題

出発点を⼀つに限定せずに，グラフ上の任意の２頂点について

最短経路を求める問題を APSP(All Pairs Shortest Paths) 問題と呼ぶ

´ ダイクストラアルゴリズムを全頂点を始点にして実⾏する ´ 隣接⾏列を使うのならば「フロイド(Floyd)アルゴリズム」も ´ n x n _{隣接⾏列 A を考える．対⾓要素 Aii} = 0_{，それ以外は Aij} = C(i,j) ´ k = 1 _{〜 n i = 1〜n j = 1〜n で３重ループを回す} A_ij = min( A_ij, A_ik + A_kj ) ´ k _{回操作後の Aijは「頂点 i から j への経路のうちk より⼤きい番号の頂点} を通過しないものの最短距離」 ´ 上の代⼊⽂で値が変更されるのは，頂点 i から j への経路⻑が k を通過す ることにより短くなる場合． 経路も求めたければ i-j 間の途中経路を記録する n x n ⾏列 P も⽤意し， 上の代⼊⽂で値が変化する場合 P[i, j] = k とすれば良い

最短経路問題: 全ての頂点つの

最短経路(2)

´ APSP_問題

出発点を⼀つに限定せずに，グラフ上の任意の２頂点について

最短経路を求める問題を APSP(All Pairs Shortest Paths) 問題と呼ぶ

最短経路問題: 全ての頂点つの

最短経路(3)

´ 「i から j までの経路があるか？」だけを知るには，要素が真偽値の みの隣接⾏列の「推移的閉包」を計算する(Warshall アルゴリズム) ´ 有向グラフの「中⼼」: 離⼼率が最⼩の頂点（最も遠い頂点までの距 離が最も⼩さい頂点） ´ ある頂点の「離⼼率」 = max { w から v への最短距離 } フロイドアルゴリズムの実⾏終了後に得られた A を⽤いると良い v _{の離⼼率 = max { Auv} } _{（第v列中の最⼤値）} ´ 練習問題 有向グラフの頂点が V = {a, b,c, d, e} で７本だけある弧のコストが C(a,b) = C(d, b) = 1, C(b, c) = C(c, d) = 2, C(d, c) = 3, C(c, e) =4, C(e, d) =5 _{としたとき，APSP 問題をとき，各頂点の離⼼率とグラフ} の中⼼を求めなさい

幅優先探索(Breadth First Search)と

深さ優先探索(Depth First Search)

´ BFS_{アルゴリズム(G, s)概略} ´ グラフ G の s 以外の全ノードの未達とする ´ Enq(Q, s) ´ while Q != _空集合 ´ v = Deq(Q) ´ for u ∈ v _{の隣接ノード} ´ u_{の到達距離}= v _{の到達距離+1} ´ Enq(Q, u) ´ v_{に到達済みのマークを⼊れる} s f c g d h a e Dijkstra _{アルゴリズムと似ている}

幅優先探索(Breadth First Search)と

深さ優先探索(Depth First Search)

´ DFS_{アルゴリズム(G, s)概略(再帰版)} ´ s _{に処理開始マークを⼊れる} ´ for u ∈ s _{の隣接ノードかつ未処理開始} ´ DFS_{アルゴリズム(G, u)} ´ s _{に処理終了マークを⼊れる} b f s g d h a e b f s g d h a e (1/10) (2/9) (3/6) (11/16) (7/8) (4/5) (12/13) (14/15) • 複数の⽊構造→森 • ⽊を構成する弧→⽊辺 • 先祖に戻る弧→後退弧 • ⽊を跨ぐ弧→交差弧 • 孫以降への弧→前進弧

閉路の無い有向グラフ

(Directed Acyclic Graph)DAG

´ 算術式の共通部分式

((a+b) * c) * (((a+b)*c) + ((a+b)+e)*(e+f))

´ 式の値を計算する場合，共通部分式の 計算を⼀度やって覚えておけば，同じ計算を 繰り返さずに済む ´ 閉路があるかどうか＝深さ優先探索で後退弧に出会うか？ ´ グラフをなぞる 頂点間に順序を設け，頂点毎に訪問済みか否かのマークをいれる ´ 深さ優先の極⼤森(Spanning Tree): 深さ優先探索の⽊の弧全体 ´ 深さ優先探索の極⼤森の中で先祖の頂点に向かう弧を後退弧と呼ぶ ´ 交差弧は先祖でも⼦孫でも無い頂点に向かう弧

トポロジカルソート

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

無向グラフの応⽤:

Minimum-cost Spanning Tree

´ 最⼩全域⽊(Minimal cost Spanning Tree)

幾つかの節点と2節点を結ぶ為のコストが与えられた時，最⼩コストで全 ての節点を結ぶ連結グラフ ´ グラフ G の全域⽊: G の全ての頂点を連結する⾃由⽊ ´ 経路 v₁ ... v_{n は「v1 と vn を「連結」する」} ´ 連結グラフ(connected graph): 全ての頂点の対が連結されている ´ ⾃由⽊: 閉路の無い連結グラフ ´ 全域⽊のコスト=辺のコストの和

MST

を求めるアルゴリズム

´ Prim のアルゴリズム 現在の⽊と，その⽊に含まれない頂点を結ぶ辺で，重みが最⼩のものを ⽊に加えて育てていく O(|V|2₎ ´ Kruskal _{のアルゴリズム} ⽊の集合で，2つの⽊を結ぶ辺の内で，重み最⼩のものを加えることで⼀ つの⽊に繋いでいく

MST

を求めるアルゴリズム

Prim

のアルゴリズム(1)

´ Prim のアルゴリズム アルゴリズム論第一 (村尾)

✬

✫

✩

✪

コスト最小の極大木を求めるプリムのアルゴリズム

プリム (Prim) のアルゴリズム

✓

✏

入力 : 無向グラフの頂点の集合 V = _{vi, 1 ≤ i ≤ n} と，辺 (vi, vj) それぞれのコスト C(vi, vj) (但し， (vi, vj) に弧が存在しなければ C(vi, vj) = ∞)． 出力 : コスト最小の極大木の辺の集合 T . . . . (1) 【初期化】 T := _{∅; (}空集合) • 構成していく木の頂点の集合 U := {v1}; • V − U の各頂点 w (∈ V − U) について，U の頂点に接続する辺の内でコスト最小の辺 (u, w) のコ スト Cmin(w) と隣接する頂点 emin(w) = u ∈ U を初期化:

Cmin(w) := C(v1, w), emin(w) := v1 for w = v2, ..., vn ∈ V − U.

(2) 【木を育てる】 U = V となるまで (即ち n− 1 回だけ) 次の処理を繰り返す．. . . .全体で O(n2) (a) 【U と V − U 間の最小コストの辺を見つける】U と V − U の頂点を結ぶすべての辺から，コスト

最小の辺 (u, v), u ∈ U, v ∈ V − U (即ち，コストの最小値 Cmin(v)) を選ぶ. . . O(n)

(b) 【木に追加】 U := U ∪ {v}; T := T ∪ { 辺 (u, v)}; Cmin(v) := ∞;

(c) 【最小コストに関する情報の更新】V − U の各頂点 w (∈ V − U) について，

C(v, w) < Cmin(w) ならば Cmin(w) := C(v, w) 及び emin(w) := v; . . . O(n)

✒

✑

MST

を求めるアルゴリズム

Prim

のアルゴリズム(2)

´ ✬Primアルゴリズム論第一 (村尾)のアルゴリズム ✫ ✩ ✪ プリムのアルゴリズムを適用すると? : U の頂点 a 1 ✑6✑✑ b ◗ ◗_◗5 d c ❳ ❳ ❳(5) ✘✘(5)✘ ❇ ❇_❇ (3) e ✁✁✁ (6) ✂✂✂(2) f ❆ ❆❆ ₍₄₎ (6) =⇒ a 1 ✑✑✑ b ◗ ◗_◗5 d c ❳ ❳ ❳ 5 ✘✘✘ ❇ ❇_❇ (3) e ✁✁✁ 6 ✂✂✂(2) f ❆ ❆❆ ₄ (6) =⇒ a 1 ✑✑✑ b ◗ ◗_◗ d c ❳ ❳ ❳ 5 ✘✘✘ ❇ ❇_❇ (3) e ✁✁✁ 6 ✂✂✂2 f ❆ ❆❆ ₄ =_⇒ a 1 ✑✑✑ b ◗ ◗_◗ d c ❳ ❳ ❳ 5 ✘✘✘ ❇ ❇_❇ (3) e ✁✁✁ 6 ✂✂✂2 f ❆ ❆❆ ₄ =_⇒ a 1 ✑✑✑ b ◗ ◗_◗ d c ❳ ❳ ❳ 5 ✘✘✘ ❇ ❇_❇ 3 e ✁✁✁ ✂✂✂2 f ❆ ❆❆ ₄ =_⇒ a 1 ✑6✑✑ b ◗ ◗_◗5 d c ❳ ❳ ❳ 5 ✘✘5✘ ❇ ❇❇ 3 e ✁ ✁✁ 6 ✂✂✂2 f ❆ ❆❆ ₄ 6

実現: Cmin() および emin() に対応する 1 次元配列を使えば，計算量は O(n2)

MST

を求めるアルゴリズム

Kruskal

のアルゴリズム(1)

´ Kruskal のアルゴリズム アルゴリズム論第一 (村尾)

✬

✫

✩

✪

コスト最小の極大木を求めるクラスカルのアルゴリズム

クラスカル (Kruskal) のアルゴリズム

✓

✏

入力 : 無向グラフの頂点の集合 V と重みつきの辺の集合 E 出力 : コスト最小の極大木の辺の集合 T . . . . (1) 【初期化】 T := _{∅; (}空集合) S := E の全ての要素 (辺) からなる集合; 連結している点の集合を要素とする集合 C の辺のない状態での初期値は，V のすべての要素 (グラフの頂点) について頂点ひとつだけからなる集合の全体: C := _{{ { v } | v ∈ V })} (2) 【C の中の 2 つのグラフを連結していく】C に要素が 2 つ以上ある間、次の操作を繰り返す (a) 辺の集合 S から，重みが最小の要素，辺 (v1, v2) を取り除く (b) 集合 C の要素で v1 と v2 を含む頂点の集合を，各々 c(v1) と c(v2) とする (c) c(v1) ̸= c(v2) ならば、両要素を C から取り除き、和集合 c(v1) ∪ c(v2) を C の 要素として追加 (C := C _{− { c(v}1), c(v2)} ∪ { c(v1) ∪ c(v2)};) し、また、T に 辺 (v1, v2) を追加 (T := T ∪ { 辺 (u, v)};)．

✒

✑

第 13 回 Page 15

MST

を求めるアルゴリズム

Kruskal

のアルゴリズム(2)

´ Kruskalアルゴリズム論第一のアルゴリズム(村尾) ✬ ✫ ✩ ✪

クラスカルのアルゴリズムを適用すると

?

a 1 ✑6✑✑ b ◗ ◗_◗5 d c ❳ ❳ ❳ 5 ✘✘5✘ ❇ ❇_❇ 3 e ✁✁✁ 6 ✂✂✂2 f ❆ ❆❆ ₄ 6 =_⇒ a 1 ✑6✑✑ b ◗ ◗_◗5 d c ❳ ❳ ❳ 5 ✘✘5✘ ❇ ❇_❇ 3 e ✁✁✁ 6 ✂✂✂2 f ❆ ❆❆ ₄ 6 =_⇒ a 1 ✑6✑✑ b ◗ ◗_◗5 d c ❳ ❳ ❳ 5 ✘✘5✘ ❇ ❇❇ 3 e ✁✁✁ 6 ✂✂✂2 f ❆ ❆❆ ₄ 6 =_⇒ a 1 ✑6✑✑ b ◗ ◗_◗5 d c ❳ ❳ ❳ 5 ✘✘5✘ ❇ ❇❇ 3 e ✁✁✁ 6 ✂✂✂2 f ❆ ❆❆ ₄ 6 =_⇒ a 1 ✑6✑✑ b ◗ ◗_◗5 d c ❳ ❳ ❳ 5 ✘✘5✘ ❇ ❇❇ 3 e ✁✁✁ 6 ✂✂✂2 f ❆ ❆❆ ₄ 6 第 13 回 Page 16

MST

を求めるアルゴリズム

Kruskal

のアルゴリズム(3)

´ Kruskal のアルゴリズムにおけるデータ表現法 ´ 辺の集合 S は重みの⼩さい順から要素を取り出していく ´ 初期化時に重みの⼩さい順にソートして配列やリストとしても良いし， 全ての要素を使うわけでもないので，辺の重みで優先順位を付けたヒープを⽤ いてもよい O(|E|log |E|) ´ 頂点の集合を要素とする集合 C: V中の頂点を幾つかに分けて出来た部分集合 の集合 ´ (2)-(b) _{はある頂点 v がどの部分集合に属するかの find 操作} ´ (2)-(c) _{は2つの部分集合の併合(merge)操作} ´ データ構造: 部分集合は⽊構造 ´ ⼦が親を指す⽊構造があると良い（配列で実現可能，親の添字を持つ) ´ 部分集合は要素数を保持し，根で区別．⽊の⾼さは⾼々 O(log n) アルゴリズム論第一 (村尾)

✬

✫

✩

✪

クラスカルのアルゴリズムにおけるデータの表現法

✄ 辺の集合 S は，重みの小さい方から要素を順に取り出していくだけ → 初期化の時に重みの小さい順に ソートして配列やリスト としてもよいし， 全ての要素を利用するわけではないので完全にソートする必要はなく ヒープ(辺の重みを優先度とす

る優先度付き待ち行列) で充分 . . . 高々 O(_{|E| log |E|)} ✄ 頂点の集合を要素とする集合 C: V 中の頂点全体をいくつかずつに分けてできた部分集合の集合 • (2)-(b) は，ある頂点がどの部分集合に属する かを検索する find 操作， (2)-(c) は，2 つの部分集合の併合 (merge) データ構造: 部分集合ごとに木構造 • (これまでの方法とは逆に) 子が親を指す木構 造 (頂点の番号を添字とする配列に，親の添字 をしまう．根の親は自分自身) • 部分集合は要素数を保持し，木の根で特定 a

✛

c

❅

❅

■

_d

✛

_f b

✛

e 木の高さは，高々 O(log n) 添字 0 1 2 3 4 5 a b c d e f 親の添字 0 1 0 0 1 3 要素数 4 2 _{× × × ×} • merge では，要素数の少ない方の集合の根の 親を，多い方の集合の根とする． • find は，根がみつかるまで親の方へとたぐっ ていく．たぐる途中で，根までの経路の全て のノードについて，ノードの親を根とするよ うに書き換えてしまってもよい (「路の圧縮」 (path compression)) 第 13 回 Page 17 アルゴリズム論第一 (村尾)

✬

✫

✩

✪

クラスカルのアルゴリズムにおけるデータの表現法

✄ 辺の集合 S は，重みの小さい方から要素を順に取り出していくだけ → 初期化の時に重みの小さい順に ソートして配列やリスト としてもよいし， 全ての要素を利用するわけではないので完全にソートする必要はなく ヒープ(辺の重みを優先度とす

る優先度付き待ち行列) で充分 . . . 高々 O(_{|E| log |E|)} ✄ 頂点の集合を要素とする集合 C: V 中の頂点全体をいくつかずつに分けてできた部分集合の集合 • (2)-(b) は，ある頂点がどの部分集合に属する かを検索する find 操作， (2)-(c) は，2 つの部分集合の併合 (merge) データ構造: 部分集合ごとに木構造 • (これまでの方法とは逆に) 子が親を指す木構 造 (頂点の番号を添字とする配列に，親の添字 をしまう．根の親は自分自身) • 部分集合は要素数を保持し，木の根で特定 a

✛

c

❅

❅

■

_d

✛

_f b

✛

e 木の高さは，高々 O(log n) 添字 0 1 2 3 4 5 a b c d e f 親の添字 0 1 0 0 1 3 要素数 4 2 _{× × × ×} • merge では，要素数の少ない方の集合の根の 親を，多い方の集合の根とする． • find は，根がみつかるまで親の方へとたぐっ ていく．たぐる途中で，根までの経路の全て のノードについて，ノードの親を根とするよ うに書き換えてしまってもよい (「路の圧縮」 (path compression)) 第 13 回 Page 17

グラフの2重連結性

´ 問い: 「2つの頂点間に複数の経路が存在するか？」 ´ 関節点(articulation point): 消去するとグラフが⾮連結になる節点． ⾮連結になる辺は橋(bridge) と呼ぶ ´ 関節点を持たないグラフを2重連結グラフと呼ぶ ´ 関節点を探すには？ ´ グラフ G の深さ優先探索⽊を構築し， ⾏掛け順になぞる ´ 各頂点について，⽊の弧を⼦孫へと向かうか後退辺により連結する頂点の番号 で最⼩の頂点を再帰的に求める ´ 深さ優先⽊の根は，弧が2⼦以上あれば関節点． 根でない頂点は到達可能名頂点の番号が頂点の番号以上でれば関節点 アルゴリズム論第一 (村尾)

✬

✫

✩

✪

グラフの

2

重連結性

• 2 つの頂点の間に 複数の経路があるか? • 「関節点」(articulation point): それを 取り除くとグラフの連結成分が増加する 頂点 d e b

❅

❅

!

!✂

✂

✂

✂

a

❅

❅

(a は関節点) c

❅

❅

f g • 『関節点をもたないグラフは「2 重連 結」(biconnected) である』 • 関節点を探すには? (1) 深さ優先探索で，行きがけ順にな ぞって頂点に番号をふる a_{⇒ b ⇒ d ! a ⇒ e ! a ! b} 1 2 3 4 " d " b ! e " a ⇒ c ⇒ f ⇒ g ! c " f " c ! g 5 6 7 " a ! d ! e 無向グラフの辺は「木の弧」か「後退辺」 (2) 各頂点について，木の弧を子孫へと 向かうか後退辺により連結する頂点 の番号で最小の値を再帰的に求める e : 1 _{⇐ d : 1 ⇐ b : 1} g : 5 _{⇐ f : 5 ⇐ c : 5} ! a : 1 (3) 根は，子が 2 個以上あれば関節点． 根でない頂点は，到達可能な頂点の 番号が頂点の番号以上ならば関節点 (根 a と頂点 c) 第 13 回 Page 18

グラフのマッチング

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

最⼤マッチングを求める

（Hopcrot-Karp の概要）

´ マッチング M に対し「Mに関する増加路」： M_{中のどの辺の端点にもなっていない2つの頂点を連結する経路のうち} 辺が⼀本おきにMに含まれるもの ´ 「MとMに関する増加路の辺の集合Pとの排他的論理和M⊕Pをもとめ， それを新たなMとする」 という操作を増加路が⾒つからなくなるまで繰り返す アルゴリズム論第一 (村尾)

✬

✫

✩

✪

最大マッチングを求める ✄ マッチング M に対し「M に関する増加路」(augmented path): M 中のどの辺の端点 もなっていない 2 つの頂点を連結する経路のうち，辺が 1 本おきに M に含まれるもの ✄ 「M と M に関する増加路の辺の集合 P との排他的論理和 M _{⊕ P (M} と P の和集合 から，M と P の共通部分を取り除いた集合) を求め，それを新たな M とする」という 操作を増加路が見つからなくなるまで繰り返す．(M の初期値は空集合 _∅) 1. 下図のような 2 部グラフで， 単純な対応付けによりマッ チング M を得る (矢印の辺 (1, a), (2, d), (3, b), (4, c)) a

❄

❆

❆❆

❅

❅

_❅

b

✁

✁

✁

◗

◗

◗◗

&

❍❍

❍❍❍

c

(

(

(

✁

✁

✁☛

d

✁

✁

✁☛

❆

❆❆

e

✏

✏

✏

✏

✏

✏

✏

1 2 3 4 5 2. 5 と e を連結する増加路? 5 a-1 b-3 _× 5 a-1 c-4 d-2 e _⃝ or 5 a-1 c-4 e _⃝ (下段の増加路を太線で記入 すると) a

❄

❆

❆❆

❅

❅

_❅

b

✁

✁

✁

◗

◗

◗◗

&

❍❍

❍❍❍

c

(

(

(

✁

✁

✁☛

d

✁

✁

✁☛

❆

❆❆

e

✏

✏

✏

✏

✏

✏

✏

1 2 3 4 5 3. 排他的論理和をとると (太 線の矢印を除去し，単なる 太線や矢印をマッチングと する) a

❆

❆❆

❅

❅

_❅

_❘

b

✁

✁

✁

◗

◗

◗◗

&

❍❍

❍❍❍

c

(

(

(

✁

✁

✁☛

d

✁

✁

✁

❆

❆❆❯

e

✏

✏

✏

✏

✏

✏

✏

✮

1 2 3 4 5 第 13 回 Page 20