与えられたグラフの隣接行列と連結行列を求め、連結行列からグラフについてわかることを述べる。グラフは5つの頂点(1, 2, 3, 4, 5)と、辺(1,2), (2,3), (2,4), (4,5)で構成されている。
2025/7/22
1. 問題の内容
与えられたグラフの隣接行列と連結行列を求め、連結行列からグラフについてわかることを述べる。グラフは5つの頂点(1, 2, 3, 4, 5)と、辺(1,2), (2,3), (2,4), (4,5)で構成されている。
2. 解き方の手順
* 隣接行列を作成する。隣接行列は、頂点iと頂点jの間に辺が存在する場合は(i,j)成分が1、そうでない場合は0となる行列である。
* 連結行列を作成する。連結行列は、頂点iと頂点jの間に経路が存在する場合は(i,j)成分が1、そうでない場合は0となる行列である。
* 連結行列からわかることを述べる。連結行列は、グラフの連結性を示す。
3. 最終的な答え
隣接行列Aは以下の通り。
$ A = \begin{pmatrix}
0 & 1 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0
\end{pmatrix}$
連結行列Cは以下の通り。
$ C = \begin{pmatrix}
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1
\end{pmatrix}$
連結行列Cからわかることは、グラフの任意の2つの頂点間に経路が存在すること、つまりグラフが連結であることである。