ラプラシアン行列

グラフ理論の分野に、ラプラシアン行列（キルヒホッフ行列）と呼ばれるものがある。

これはグラフの構造を行列で表したもので、対角成分で頂点の価数を、その他の成分で隣接関係を表す。

具体的には、成分(i, j)の値は次のように決まる。
・i=j のとき：頂点iに接続する辺の数
・i≠jのとき：頂点iと頂点jが辺でつながっていれば-1。そうでなければ0

Wikipediaに載っている次の具体例がわかりやすい。

何のために、このような行列表現をするのか？

このような行列表現をすると、グラフの性質が行列の性質を通して明らかになるから。

例：値がゼロとなる固有値の数が、Connected componentの数と等しい。（つまり、少なくとも1つの固有値は値がゼロである）
例：全域木の数え上げに使える（External Memory：グラフと線形代数）

ほかにも、3DCGで使われるメッシュモデルの平滑化にも使われる。（nursの日記：離散ラプラシアンメッシュスムージング）

離散数学「数え上げ理論」―「おみやげの配り方」から「Nクイーン問題」まで (ブルーバックス)

情報科学のためのグラフ理論 (入門 有限・離散の数学)