問題プレビューID: 20fb5847

問 3

隣接行列 $A$ で表されるグラフはどれか。ここで，隣接行列とは， $n$ 個の節点から成るグラフの節点 $V_i$ と $V_j$ を結ぶ枝が存在するときは第 $i$ 行第 $j$ 列と第 $j$ 行第 $i$ 列の要素が $1$ となり，存在しないときは $0$ となる $n$ 行 $n$ 列の行列である。

〔隣接行列 $A$ 〕

A = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix}

解説

隣接行列 $A$ の要素が $1$ である位置から，枝の有無を読み取る。

第1行： $V_1$ は $V_2$ ， $V_3$ と隣接
第2行： $V_2$ は $V_1$ ， $V_4$ と隣接
第3行： $V_3$ は $V_1$ ， $V_4$ と隣接
第4行： $V_4$ は $V_2$ ， $V_3$ と隣接

つまり枝は $V_1 - V_2$ ， $V_1 - V_3$ ， $V_2 - V_4$ ， $V_3 - V_4$ の4本である。 $V_1$ と $V_4$ ， $V_2$ と $V_3$ の間には枝がない。これを表すグラフは「エ」です。