東北大学 工学研究科 電気・情報系 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)$ となるような探索アルゴリズムの概要を説明せよ。

题目描述

1. 考虑由顶点集 $V$ 与带权边集 $E$ 构成的连通无向图 $G=(V,E)$，图 4 的 $G_1$ 是一个具体例子。
   1. 写出 $G_1$ 的邻接矩阵与邻接表；可忽略边权；
   2. 对含 $n$ 个顶点、$m$ 条边的图，分别用大 $O$ 记号给出存储邻接矩阵和邻接表所需空间；
   3. 生成树是包含 $G$ 全部顶点的连通无环子图，最小生成树是总边权最小的生成树。求图 4 中 $G_1$ 的最小生成树。
2. 整数矩阵 $M$ 有 $n$ 行 $m$ 列，每行从左到右非降序、每列从上到下非降序。设计并概述一个时间复杂度为 $O(n+m)$ 的算法：给定整数 $x$，若 $M$ 含有 $x$ 输出 Yes，否则输出 No。

考点

• 图的表示：在邻接矩阵和邻接表之间转换并比较空间复杂度。
• 最小生成树：用 Prim 或 Kruskal 算法选择不成环的最轻边。
• 渐近空间分析：邻接矩阵为 $O(n^2)$，邻接表为 $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)$。