隣接行列

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

隣接行列(りんせつぎょうれつ)は、グラフを表現するために用いる行列である。

ある頂点 vw の間の枝の本数を行列の (v, w) 成分に割り当てる(単純グラフであれば、枝があるとき (v, w) を 1 に、枝がないとき (v, w) を 0 にする)。有向グラフの場合、v から w に向かう枝があるときのみ (v, w) を 1 に、そうでないとき (v, w) を 0 にする。また、枝に重みがついているグラフの場合は、 (v, w) に重みを代入する。

[編集]

6つのノードと7つのエッジから成るグラフの一例

6n-graf.svg


例えば、上の(重みなし)グラフは、以下の隣接行列で表現できる。

\begin{pmatrix}
0 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
\end{pmatrix}

性質[編集]

  • 重みなしグラフ G の隣接行列を A とすると、An で表される行列の (i, j) 成分は、i から j への相違なる長さ nの数と等しくなる。したがって、An の (i, i) 成分が 0 でないとき、頂点 i を通る長さ nループが存在し、逆も成立する。この性質は、有向グラフでも無向グラフでも成り立つ。
  • G が自己ループを持たないとき、G に含まれる三角形の数は、G の隣接行列 A を用いて、
\frac{1}{6} \cdot {\rm tr}(A^3)
で表せる。

関連項目[編集]