隣接行列

隣接行列（りんせつぎょうれつ、英: adjacency matrix）とは、代数的グラフ理論における基本的な概念で、グラフの頂点と頂点の隣接関係を表わす正方行列である。

頂点集合を {1, …, n} とする有限無向グラフ G に対して、その隣接行列 A(G) = [a_ij] とは（頂点集合によって添字づけられた）n 次正方行列であって、その (i, j) 成分 a_ij は頂点 i と頂点 j を結ぶ枝の数で定義される。これによりグラフ G の固有多項式やスペクトルがそれぞれ隣接行列 A(G) の固有多項式やスペクトルとして定義される。これらはグラフの不変量である（隣接行列そのものは頂点集合上の置換を除いてしか定まらない）。

有向グラフの場合、i から j に向かう枝があるときのみ (i, j) 成分を 1 に、そうでないとき (i, j) 成分を 0 にする。また、枝に重みがついているグラフの場合は、 (i, j) 成分を重みとする。

例

6つの頂点と7つの枝から成るグラフの一例

ファイル:6n-graf.svg

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

[math]\begin{bmatrix} 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{bmatrix}[/math]

性質

• 重みなしグラフ G の隣接行列を A = A(G) とすると、Aⁿ で表される行列の (i, j) 成分は、i から j への相違なる長さ n の路の数と等しくなる。実際、Aⁿの(i, j)成分をa_ij ⁽ⁿ⁾とすると、

[math]A^n = A^{n-1} A = \left( \sum_k {a_{ik}^{(n-1)} a_{kj}} \right)[/math]

であり、a_ik ^(n-1) a_kjは、（i から k への相違なる長さ n-1 の路の数）×（k から j への相違なる長さ 1 の路の数）であることから、帰納的に従う。

したがって、Aⁿ の (i, i) 成分が 0 でないとき、頂点 i を通る長さ n のループが存在し、逆も成立する。この性質は、有向グラフでも無向グラフでも成り立つ。

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

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

で表せる。

関連項目

• 隣接リスト
• 接続行列（incidence matrix）—グラフの頂点と枝の接続関係を表す行列
• ラプラシアン行列
• スペクトラルグラフ理論