隣接行列

出典: フリー百科事典『ウィキペディア(Wikipedia)』
Jump to navigation Jump to search

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

頂点集合を {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つの枝から成るグラフの一例

6n-graf.svg

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

性質[編集]

  • 重みなしグラフ G の隣接行列を A = A(G) とすると、An で表される行列の (i, j) 成分は、i から j への相違なる長さ nの数と等しくなる。実際、Anの(i, j)成分をaij (n)とすると、
であり、aik (n-1) akjは、(i から k への相違なる長さ n-1 の路の数)×(k から j への相違なる長さ 1 の路の数)であることから、帰納的に従う。
したがって、An の (i, i) 成分が 0 でないとき、頂点 i を通る長さ nループが存在し、逆も成立する。この性質は、有向グラフでも無向グラフでも成り立つ。
  • G が無向グラフでかつ自己ループを持たないとき、G に含まれる三角形の数は、G の隣接行列 A を用いて、
で表せる。

関連項目[編集]