広島大学 先進理工系科学研究科 情報科学プログラム 2022年1月実施 専門科目II 問題2
Author
祭音Myyura
Description
以下の問いに答えよ。
(1) Table 1 は鳥取 (Tr)、島根 (S)、岡山 (O)、広島 (H)、山口 (Y)、徳島 (Tk)、愛媛 (E) の7つの各都市間の距離を表す。
都市を頂点とし、距離を都市間の辺の重みとしたグラフ
(2) 各辺の重みがすべて異なる任意のサイズの重み付き連結グラフ
(3) (2) で述べたアルゴリズムで求められる部分グラフが最小全域木であることを証明せよ。
(4) (2) で述べたアルゴリズムの計算時間複雑性を理由とともに示せ。
(5) 重み付き連結グラフ
Answer the following questions
(1) Table 1 shows the distances between the seven cities of Tottori (Tr), Shimane (S), Okayama (O), Hiroshima (H), Yamaguchi (Y), Tokushima (Tk), and Ehime (E): Find the minimum spanning tree of graph
(2) Describe an algorithm to find the minimum spanning tree in a weighted connected graph
(3) Prove that the subgraph obtained by the algorithm described in (2) is the minimum spanning tree.
(4) Show the time complexity of the algorithm described in (2) with reasons.
(5) In a weighted connected graph
Table 1
Tr | S | O | H | Y | Tk | E | |
---|---|---|---|---|---|---|---|
Tr | - | 108 | 97 | 204 | 292 | 162 | 229 |
S | 108 | - | 121 | 131 | 203 | 298 | 183 |
O | 97 | 121 | - | 139 | 233 | 88 | 141 |
H | 204 | 131 | 139 | - | 94 | 197 | 78 |
Y | 292 | 203 | 233 | 94 | - | 258 | 126 |
Tk | 162 | 298 | 88 | 197 | 258 | - | 168 |
E | 229 | 183 | 141 | 78 | 126 | 168 | - |
Kai
(1)

(2)
Step 1: Determine an arbitrary vertex as the starting vertex of the MST.
Step 2: Follow steps 3 to 5 till there are vertices that are not included in the MST (known as fringe vertex).
Step 3: Find edges connecting any tree vertex with the fringe vertices.
Step 4: Find the minimum among these edges.
Step 5: Add the chosen edge to the MST if it does not form any cycle.
Step 6: Return the MST and exit
(3)
Let
It is trivial that the subgraph obtained by Prim's algorithm is a tree. Let
Let
Let
(4)
If we use an adjacent list graph representation and a binary heap to find an edge of minimum weight, then the worst-case time complexity is
(5)
Assume the contrary, that there are two different MSTs
Since
As