図1 グラフ
各枝に正の重みが与えられたグラフがある．このグラフ上の全点を張る木の中で，枝の重みの総和が最小なものを「最小木」とよぶ．この最小木は「クラスカル法」と名づけられている以下のアルゴリズムで求められることが知られている．
|
||||||||||
次の問いに答えよ．
| (1) | 図1で与えられたグラフの最小木を求めなさい．答えは，グラフを図示し，最小木を構成する枝を太線にすることで示しなさい． |
図1 グラフ |
| (2) | 与えられたグラフの点数がn個，枝数がm本である時，最小木を求める問題の入力サイズを求めよ． | |
| (3) | クラスカル法をできる限り効率よく実行したい．どのような点に工夫を加えると効率よく実行できるか．工夫を加えるべき箇所を挙げ，その方法を説明せよ． | |
| (4) | 上記で提案した工夫を加えた上でクラスカル法を実行した際の，クラスカル法の最悪計算量を評価せよ．ただし，評価結果は漸近計算量で表現せよ． | |
| (5) | n=1,000,000(点数が百万),m=3,000,000(枝数が三百万)のサイズのグラフ上で最小木をクラスカル法で求める．1秒に1億回演算可能なコンピュータを用いて導出を試みた場合，おおよそどの程度の時間で最小木を導くか求めなさい．なお，必要ならlog102=0.3010とみなし利用してよい． | |