与えられた無向グラフ $G(V, E)$ について、以下の問いに答えます。 (1) グラフ $G(V, E)$ を示します。 (2) グラフ $G(V, E)$ の隣接行列 $A$ を求めます。 (3) グラフ $G(V, E)$ において、長さ2の $P_3$-$P_2$ 歩道の数を求めます。

1. 問題の内容

与えられた無向グラフ $G(V, E)$ について、以下の問いに答えます。

(1) グラフ $G(V, E)$ を示します。

(2) グラフ $G(V, E)$ の隣接行列 $A$ を求めます。

(3) グラフ $G(V, E)$ において、長さ2の $P_3$-$P_2$ 歩道の数を求めます。

2. 解き方の手順

(1) グラフ $G(V, E)$ の図示

頂点集合 $V = \{P_1, P_2, P_3, P_4, P_5\}$ と辺集合 $E = \{(P_1, P_3), (P_2, P_4), (P_2, P_3), (P_3, P_4), (P_4, P_5)\}$ をもとにグラフを図示します。それぞれの頂点を点として描き、辺集合にある頂点間を線で結びます。

(2) 隣接行列 $A$ の算出

隣接行列 $A$ は、グラフの頂点間の隣接関係を示す正方行列です。$n$ 個の頂点を持つグラフの場合、$n \times n$ の行列になります。行列の $(i, j)$ 成分 $A_{ij}$ は、頂点 $P_i$ と頂点 $P_j$ が隣接している場合に 1、隣接していない場合に 0 となります。無向グラフの場合、隣接行列は対称行列になります。

この問題の場合、$V = \{P_1, P_2, P_3, P_4, P_5\}$ なので、隣接行列 $A$ は $5 \times 5$ の行列となります。

辺集合 $E = \{(P_1, P_3), (P_2, P_4), (P_2, P_3), (P_3, P_4), (P_4, P_5)\}$ を基に、隣接行列 $A$ の各成分を決定します。

$A_{13} = A_{31} = 1$, $A_{24} = A_{42} = 1$, $A_{23} = A_{32} = 1$, $A_{34} = A_{43} = 1$, $A_{45} = A_{54} = 1$

他の成分は全て 0 となります。

(3) 長さ2の $P_3$-$P_2$ 歩道の数の算出

長さ2の $P_3$-$P_2$ 歩道は、頂点 $P_3$ から始まり、2つの辺を通って頂点 $P_2$ に到達する経路です。

$P_3$ から到達できる頂点とその経路は以下の通りです。

- $P_1$ : $(P_3, P_1)$

- $P_2$ : $(P_3, P_2)$

- $P_4$ : $(P_3, P_4)$

次に、$P_1$, $P_2$, $P_4$から$P_2$に到達できるか確認します。

- $P_1$ から $P_2$ へ直接到達することはできません。

- $P_2$ から $P_2$ へは到達できません。

- $P_4$ から $P_2$ へは $(P_4, P_2)$ を通って到達できます。

したがって、長さ2の $P_3$-$P_2$ 歩道は $P_3 \rightarrow P_4 \rightarrow P_2$ のみです。

歩道の数は1つです。

3. 最終的な答え

(1) グラフ $G(V, E)$ は、頂点 $P_1, P_2, P_3, P_4, P_5$ と辺 $(P_1, P_3), (P_2, P_4), (P_2, P_3), (P_3, P_4), (P_4, P_5)$ を持つグラフです。 (図示は省略します)

(2) 隣接行列 $A$ は以下の通りです。

$A = \begin{pmatrix}

0 & 0 & 1 & 0 & 0 \\

0 & 0 & 1 & 1 & 0 \\

1 & 1 & 0 & 1 & 0 \\

0 & 1 & 1 & 0 & 1 \\

0 & 0 & 0 & 1 & 0

\end{pmatrix}$

(3) 長さ2の $P_3$-$P_2$ 歩道の数は 1 です。