隣接行列
- 作成者:
- Bunryu Kamimura
グラフを行列で表現する・・・trはトレース（対角線の和）
行列で表現する
図のグラフを行列にしてみる。
点ＡＢＣＤに１２３４と数字を割り振ると行列ができる。
｜１ ２ ３ ４
１｜
２｜
３｜
４｜
１と２は線分で結ばれているので１とする。
１と３も結ばれているので１．
｜１ ２ ３ ４
１｜０ １ １
２｜１ ０
３｜１ ０
４｜
という様に作った行列を隣接行列という。
この行列で、図のように３角形の数を計算することができる。
An で表される行列の (i, j) 成分は、i から j への相違なる長さ n の路の数と等しくなる。
であり、aik (n-1) akjは、（i から k への相違なる長さ n-1 の路の数）×（k から j への相違なる長さ 1 の路の数）であることから、帰納的に従う。したがって、An の (i, i) 成分が 0 でないとき、頂点 i を通る長さ n のループが存在し、逆も成立する。この性質は、有向グラフでも無向グラフでも成り立つ。
- 実際、Anの(i, j)成分をaij (n)とすると、
であり、aik (n-1) akjは、（i から k への相違なる長さ n-1 の路の数）×（k から j への相違なる長さ 1 の路の数）であることから、帰納的に従う。したがって、An の (i, i) 成分が 0 でないとき、頂点 i を通る長さ n のループが存在し、逆も成立する。この性質は、有向グラフでも無向グラフでも成り立つ。