東北大学 工学研究科 電気・情報系 2023年2・3月実施実施 基礎科目 問題4 情報基礎2

标签：

• Tohoku-University
• Minimum-Spanning-Tree

Author

祭音Myyura

Description

以下の問に答えよ。

(1)

節点の集合 $V$ と重みが付いた枝の集合 $E$ からなる連結無向グラフ $G = (V, E)$ について考える. Fig. 4 のグラフ $G_1$ はそのような連結無向グラフの例であり、各枝の中央付近に記載の整数は、その枝の重みである。

(a) Fig. 4 のグラフ $G_1$ の隣接行列と隣接リストを示せ、ただし、枝の重みの情報は含まなくても良い。

(b) $n$ 個の節点と $m$ 個の枝からなるグラフ $G$ の隣接行列と隣接リストを格納するのに必要な記憶領域のサイズを $O$ 記法でそれぞれ示せ。

(c) グラフ $G$ の連結部分グラフの中で、$G$ の全ての節点を含む木を $G$ の全域木と呼ぶ、また、$G$ の全域木の中で、枝の重みの合計が最小であるものを $G$ の最小全域木と呼ぶ. Fig. 4のグラフ $G_1$ の最小全域木を示せ.

(2)

各行の要素の値は左から右に昇順ソートされ、かつ、各列の要素の値は上から下に昇順ソートされている $n$ 行 $m$ 列の整数行列 $M$ を考える、任意の整数 $x$ に対して、$M$ に値が $x$ である要素が含まれる場合は「Yes」 を出力し、そうでない場合は「No」を出力する探索アルゴリズムを考える、時間計算量が $O(n + m)$ となるような探索アルゴリズムの概要を説明せよ。

Kai

(1)

(a)

隣接行列

$$\begin{pmatrix} 0 & 6 & 7 & 0 & 0 \\ 6 & 0 & 5 & 3 & 2 \\ 7 & 5 & 0 & 1 & 0 \\ 0 & 3 & 1 & 0 & 4 \\ 0 & 2 & 0 & 4 & 0 \end{pmatrix}$$

隣接リスト

$$\begin{aligned} a & : (b, 6), (c, 7) \\ b & : (a, 6), (c, 5), (d, 3), (e, 2) \\ c & : (a, 7), (b, 5), (d, 1) \\ d & : (b, 3), (c, 1), (e, 4) \\ e & : (b, 2), (d, 4) \end{aligned}$$

(b)

• 隣接行列は $n \times n$ の行列で、各要素に辺の重み（整数）を格納するため、メモリ使用量は $O(n^2)$ となります。
• 隣接リストは各ノードに接続されているノードとその重みをリストで保持します。全辺数 $m$ を考えると、メモリ使用量は $O(n + m)$ です。

(c)

クラスカル法では以下の辺が選ばれることになります。

• $(c, d)$ 重み 1
• $(b, e)$ 重み 2
• $(b, d)$ 重み 3
• $(a, b)$ 重み 6

これで、最小全域木の重みの合計は $1 + 2 + 3 + 6 = 12$ です。

(2)

アルゴリズム概要

1. 右上から開始する。ここでは右上 $(i,j)=(0,m-1)$ とする。
2. ループ：
   • もし $M[i][j]=x$ なら「Yes」を返す（終了）。
   • もし $M[i][j] > x$ なら、この列の下方向はすべて $M[i][j]$ 以上なので、列を1つ左へ移動（$j \leftarrow j-1$）。
   • もし $M[i][j] < x$ なら、この行の左方向はすべて $M[i][j]$ 以下なので、行を1つ下へ移動（$i \leftarrow i+1$）。
3. インデックスが範囲外になったら要素は存在しないので「No」。

計算量

行インデックス $i$ は最大 $n$ 回増え，列インデックス $j$ は最大 $m$ 回減る。したがって比較回数は高々 $n+m$，時間計算量は $O(n+m)$。