グラフの基礎グラフの行列表現隣接行列の演算和と積、完全グラフ、連結性

学習環境

情報系のための離散数学 (猪股俊光 (著)、南野謙一 (著)、共立出版)の第7章(グラフの基礎)、7.4(グラフの行列表現)、7.4.2(隣接行列の演算)、問7.19の解答を求めてみる。

隣接行列。

K = [\begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix}]

〈2〉

\begin{array}{l} [\begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix}] [\begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix}] \\ = [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix}] \end{array}

〈4〉

[\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix}]

よって、連続性については完全グラつKの隣接行列について、〈2〉、〈4〉、一般に2以上のnに対して、〈n〉は任意の2つの頂点に対して長さ2の歩道が存在する。