隣接行列

提供: miniwiki
2018/8/19/ (日) 17:39時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内検索

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

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

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

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

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

[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) とすると、An で表される行列の (i, j) 成分は、i から j への相違なる長さ nの数と等しくなる。実際、Anの(i, j)成分をaij (n)とすると、
[math]A^n = A^{n-1} A = \left( \sum_k {a_{ik}^{(n-1)} a_{kj}} \right)[/math]
であり、aik (n-1) akjは、(i から k への相違なる長さ n-1 の路の数)×(k から j への相違なる長さ 1 の路の数)であることから、帰納的に従う。
したがって、An の (i, i) 成分が 0 でないとき、頂点 i を通る長さ nループが存在し、逆も成立する。この性質は、有向グラフでも無向グラフでも成り立つ。
  • G が無向グラフでかつ自己ループを持たないとき、G に含まれる三角形の数は、G の隣接行列 A を用いて、
[math]\frac{1}{6} \cdot {\rm tr}(A^3)[/math]
で表せる。

関連項目