隣接行列
グラフ理論の復習。 線形代数的グラフ理論（竹中 淑子）などを参考に。
グラフの表現のひとつとして、隣接行列を考える。 つまり、頂点が n 個のグラフの場合、n×n行列で、(i,j)成分 = i番目の頂点からj番目の頂点への辺の個数とする行列を、隣接行列という。無向グラフの場合は対称行列になる。 有向グラフの場合はそうとは限らない。辺に重みがあるとき、多重辺 （ある始点からある終点までの辺が２つ以上あること）を持たない場合に
(i,j)成分 = i番目の頂点からj番目の頂点への辺の重み。辺がないときは0。と定義することもある。ここでは重みの値は正であることを仮定する。 （参考： Weighted Graph (mathworld)） 仮定しない場合は、重みが０のときと辺がないときの区別がつけられない、 内積をうまく定義できない、などの弊害が出てしまう（後述）。 このように定義すると、隣接行列からグラフを構成することができる。 グラフから隣接行列を定義するには、頂点の順番の取り方によって 置換行列による相似変換の分だけのあいまいさがある。 とすると、グラフの性質を調べるには隣接行列の置換行列による 相似変換によって変化しない不変量を考えればよい。 隣接行列（またはそこから導かれるラプラシアン行列）の固有値について調べることは、 一般の相似変換によって変化しない不変量を調べていることになるから、 情報は少し落ちている。でも調べやすいので、まずはそこから考えてみる。