Google Classroom
GeoGebraGeoGebra Classroom

隣接行列

グラフを行列で表現する・・・trはトレース(対角線の和)

行列で表現する

図のグラフを行列にしてみる。 点ABCDに1234と数字を割り振ると行列ができる。  |1 2 3 4 1|  2| 3| 4| 1と2は線分で結ばれているので1とする。 1と3も結ばれているので1.  |1 2 3 4 1|0 1 1 2|1 0 3|1   0 4| という様に作った行列を隣接行列という。 この行列で、図のように3角形の数を計算することができる。 An で表される行列の (ij) 成分は、i から j への相違なる長さ n のの数と等しくなる。
  • 実際、Anの(ij)成分をaij (n)とすると、
であり、aik (n-1) akjは、(i から k への相違なる長さ n-1 の路の数)×(k から j への相違なる長さ 1 の路の数)であることから、帰納的に従う。したがって、An の (ii) 成分が 0 でないとき、頂点 i を通る長さ n のループが存在し、逆も成立する。この性質は、有向グラフでも無向グラフでも成り立つ。