隣接行列

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

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

例

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

ファイル:6n-graf.svg

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

<math>\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}</math>

性質

• 重みなしグラフ G の隣接行列を A とすると、Aⁿ で表される行列の (i, j) 成分は、i から j への相違なる長さ n の路の数と等しくなる。したがって、Aⁿ の (i, i) 成分が 0 でないとき、頂点 i を通る長さ n のループが存在し、逆も成立する。この性質は、有向グラフでも無向グラフでも成り立つ。

• G が自己ループを持たないとき、G に含まれる三角形の数は、G の隣接行列 A を用いて、

<math>\frac{1}{6} \cdot {\rm tr}(A^3)</math>

で表せる。

関連項目

• 隣接リスト