ラプラシアンマトリックス
ラプラシアンなんて聞くと、2階微分するんだろ!なんて思ってました。
数日前の日記にも書きましたが、頂点キャッシュの問題を調べていてラプラシアン行列なるものに出会いました。
で、今日はお勉強して覚えた事を備忘録として。
ラプラシアン行列はキルヒホッフ行列とも呼ぶらしいです。
どんな行列かといいますと、微分とかは全然関係なくて、グラフの各ノードに関する隣接数と隣接しているかどうかを0か-1で表現した行列です。
たとえば、グラフの各ノードに一意の整数を順番にふっていったと仮定し。
行列のi,i成分(対角成分)はi番目のノードの隣接数を、i,j番目の成分にはiがjに隣接していたら-1、してなかったら0。
ある列(行)に着目して各成分を足すと当然0になります。
そんな行列をラプラシアン行列と呼びます。
このラプラシアン行列は、実は、グラフの特性をいろいろと調べるのに使えます。
グラフのスペクトル分解という技はこのラプラシアン行列の固有値と固有ベクトルを使って行います。
続きは…また今度。