名古屋大学情報学研究科複雑系科学専攻 2024年8月実施情3

标签：

Author

祭音Myyura

Description

[1]

Union/Find とは、互いに素な集合の集まりを管理するデータ構造で以下の 2 つの操作をもつ。その集合で最小の要素を代表の要素とする。

Find(x)：x が所属する集合の代表の要素を返す操作。要素 x のみの集合は、代表の要素は x となる。
Union(x, y)：x が所属する集合と y が所属する集合を 1 つにまとめる操作。

例えば初期状態が {0}, {1}, {2}, {3}, {4} の場合、 Find(3) を実行すると 3 が返され、 Union(1, 3) を実行すると、{0}, {1, 3}, {2}, {4} となる。

1)

初期集合が

{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}

であるとする。この集合に対して以下のような順で Union 操作を行う過程を示しなさい。

Union(0, 2)
Union(1, 5)
Union(3, 4)
Union(6, 9)
Union(0, 8)
Union(3, 7)
Union(1, 6)

2)

で得られた最終的な集合に対して、Find(2), Find(4), Find(6) の操作を行った結果を示しなさい。

[2]

Union/Find 操作を用いて頂点が $\{0, 1, 2, ..., 5\}$ である無向グラフ $G$ に閉路が存在するかどうか調べる。 Union/Find 操作による閉路検出では、各ノードを単一要素の集合に初期化し、辺の両端ノードの Find 操作で所属集合を調べる。もし同じ集合なら閉路であることが検出され、異なる集合なら Union 操作を行う。この処理を各辺について繰り返す。 $G$ は以下の隣接リストで表す。このリストは、頂点 $0$ から $5$ のそれぞれについて、隣接するすべての頂点を列挙したものである。閉路検出に用いた Union/Find 操作の内容を操作順に示せ。

$G$ の隣接リスト

頂点	隣接頂点
0	4
1	2, 5
2	1, 5
3	5
4	2
5	1, 2, 3

[3]

クラスカル法は、重み付き無向グラフの最小全域木（Minimum Spanning Tree, MST）を探索するアルゴリズムである。最小全域木とは重み付き無向グラフの部分木であり、しかも、そのグラフのすべての頂点を含み、構成するすべての辺の重みの合計が最小のものである。クラスカル法の手順を以下に示す。

初期状態を空のグラフ $G$ とする。
与えられたグラフ $M$ の全ての辺を重みの小さい順に並べ替え、辺リスト $L$ とする。
辺リスト $L$ $L$ から順に辺 $e$ $e$ を取り出し、 $L$ $L$ が空になるまで以下を行う。
1. 辺 $e$ をグラフ $G$ に追加した場合に閉路ができるかを Union/Find 操作で判定する。閉路ができない場合、辺 $e$ をグラフ $G$ に追加し、Union 操作を行う。

以下の $N$ は 7 つの頂点 $(1, 2, 3, ..., 7)$ で構成される重み付き無向グラフである。 $N$ の辺と重みは次のように表記される。

辺の両端点	重み
(1, 2)	2
(1, 3)	3
(1, 7)	4
(2, 3)	5
(2, 5)	7
(3, 4)	9
(3, 6)	8
(4, 6)	10
(5, 6)	6
(5, 7)	1

クラスカル法を使って、実行された Union/Find 操作の処理内容も含めて、グラフ $N$ の最小全域木（MST）を求める過程を示しなさい。

Kai

[1]

1)

操作	操作後の集合
`Union(0, 2)`	`{0,2}, {1}, {3}, {4}, {5}, {6}, {7}, {8}, {9}`
`Union(1, 5)`	`{0,2}, {1,5}, {3}, {4}, {6}, {7}, {8}, {9}`
`Union(3, 4)`	`{0,2}, {1,5}, {3,4}, {6}, {7}, {8}, {9}`
`Union(6, 9)`	`{0,2}, {1,5}, {3,4}, {6,9}, {7}, {8}`
`Union(0, 8)`	`{0,2,8}, {1,5}, {3,4}, {6,9}, {7}`
`Union(3, 7)`	`{0,2,8}, {1,5}, {3,4,7}, {6,9}`
`Union(1, 6)`	`{0,2,8}, {1,5,6,9}, {3,4,7}`

2)

\operatorname{Find}(2)=0, \operatorname{Find}(4)=3, \operatorname{Find}(6)=1

[2]

無向辺は重複を除き、隣接リストに現れる順に

(0,4),(1,2),(1,5),(2,5),(3,5),(2,4)

として処理する。

辺	Find の結果	処理
`(0,4)`	`Find(0)=0`, `Find(4)=4`	異なるので `Union(0,4)`
`(1,2)`	`Find(1)=1`, `Find(2)=2`	異なるので `Union(1,2)`
`(1,5)`	`Find(1)=1`, `Find(5)=5`	異なるので `Union(1,5)`
`(2,5)`	`Find(2)=1`, `Find(5)=1`	同じ集合なので閉路を検出
`(3,5)`	`Find(3)=3`, `Find(5)=1`	異なるので `Union(3,5)`
`(2,4)`	`Find(2)=1`, `Find(4)=0`	異なるので `Union(2,4)`

辺 (2,5) を調べた時点で、頂点 2 と 5 はすでに同じ集合に属している。
したがって、この辺を加えると

1-2-5-1

という閉路ができる。

[3]

辺を重みの小さい順に並べると、

\begin{aligned} &(5,7):1,\ (1,2):2,\ (1,3):3,\ (1,7):4,\ (2,3):5,\\ &(5,6):6,\ (2,5):7,\ (3,6):8,\ (3,4):9,\ (4,6):10 \end{aligned}

となる。

辺・重み	Find の結果	判定
`(5,7), 1`	`5 \neq 7`	採用し、`Union(5,7)`
`(1,2), 2`	`1 \neq 2`	採用し、`Union(1,2)`
`(1,3), 3`	`1 \neq 3`	採用し、`Union(1,3)`
`(1,7), 4`	`1 \neq 5`	採用し、`Union(1,7)`
`(2,3), 5`	`1 = 1`	閉路ができるため不採用
`(5,6), 6`	`1 \neq 6`	採用し、`Union(5,6)`
`(2,5), 7`	`1 = 1`	閉路ができるため不採用
`(3,6), 8`	`1 = 1`	閉路ができるため不採用
`(3,4), 9`	`1 \neq 4`	採用し、`Union(3,4)`

7 頂点の全域木に必要な辺数は $7-1=6$ 本であるため、ここで終了する。

採用された辺は

\boxed{ (5,7),(1,2),(1,3),(1,7),(5,6),(3,4) }

である。

重みの合計は

1+2+3+4+6+9=25

Author​

Description​

[1]​

1)​

2)​

[2]​

[3]​

Kai​

[1]​

1)​

2)​

[2]​

[3]​

Author

Description

[1]

1)

2)

[2]

[3]

Kai

[1]

1)

2)

[2]

[3]