与えられたグラフの隣接行列と連結行列を求め、連結行列からわかることを述べよ。グラフは5つの頂点（1, 2, 3, 4, 5）と、いくつかの有向辺で構成されています。

1. 問題の内容

与えられたグラフの隣接行列と連結行列を求め、連結行列からわかることを述べよ。グラフは5つの頂点（1, 2, 3, 4, 5）と、いくつかの有向辺で構成されています。

2. 解き方の手順

(1) 隣接行列の作成

隣接行列$A$は、$n \times n$の正方行列であり、$A_{ij}$は頂点$i$から頂点$j$への辺が存在する場合は1、存在しない場合は0となります。

与えられたグラフの隣接行列は以下のようになります。

$ A = \begin{pmatrix}

0 & 0 & 0 & 0 & 0 \\

1 & 0 & 1 & 1 & 0 \\

0 & 0 & 0 & 0 & 1 \\

0 & 1 & 0 & 0 & 0 \\

0 & 0 & 0 & 1 & 0

\end{pmatrix} $

(2) 連結行列の作成

連結行列 $M$は、$n \times m$ の行列であり、$n$は頂点の数、$m$は辺の数です。

$M_{ij}$は頂点$i$が辺$j$の始点である場合は1、終点である場合は-1、そうでない場合は0となります。

まずグラフの辺に番号を振ります。

1: 2 -> 1

2: 2 -> 3

3: 2 -> 4

4: 3 -> 5

5: 4 -> 5

連結行列$M$は以下のようになります。

$ M = \begin{pmatrix}

-1 & 0 & 0 & 0 & 0 \\

1 & 1 & 1 & 0 & 0 \\

0 & -1 & 0 & 1 & 0 \\

0 & 0 & -1 & 0 & 1 \\

0 & 0 & 0 & -1 & -1

\end{pmatrix} $

(3) 連結行列からわかること

連結行列の各列は、対応する辺の始点と終点を示しています。

連結行列の各行の和は、対応する頂点が出入りする辺の数の差を示しています。

このグラフは連結グラフであることがわかります。

また、このグラフは強連結ではありません。

3. 最終的な答え

隣接行列:

$ A = \begin{pmatrix}

0 & 0 & 0 & 0 & 0 \\

1 & 0 & 1 & 1 & 0 \\

0 & 0 & 0 & 0 & 1 \\

0 & 1 & 0 & 0 & 0 \\

0 & 0 & 0 & 1 & 0

\end{pmatrix} $

連結行列:

$ M = \begin{pmatrix}

-1 & 0 & 0 & 0 & 0 \\

1 & 1 & 1 & 0 & 0 \\

0 & -1 & 0 & 1 & 0 \\

0 & 0 & -1 & 0 & 1 \\

0 & 0 & 0 & -1 & -1

\end{pmatrix} $

連結行列から、グラフの連結性や辺の向きがわかります。このグラフは連結ですが、強連結ではありません。