5.17. ラプラシアンに関する他の話題

有向グラフのラプラシアンに関して言えることは他にも多くある。グラフと有向グラフに関連付く行列を研究する分野はスペクトルグラフ理論 (spectral graph theory) と呼ばれる。スペクトルグラフ理論が扱う行列の中で最も重要なのがラプラシアンではないかと私は思う (定義の理解しやすさでは隣接行列に分があるだろう)。行列木定理を (定理 5.15.1 (a) に似た命題として) 初めて発見したのは Gustav Kirchhoff であり、彼は電気回路に関する研究 [Kirchh47] の中で行列木定理を発見した ([Holzer22, § 2.1.1] に現代的な解説がある)。電気回路ネットワークにおける任意のノード間の実効抵抗は全域木の個数の比として表すことができ、そのためラプラシアンを使って計算できる (例えば [Vos16, § 2 and § 3] を見てほしい)。なお、正確に言うと実効抵抗は全域木の個数の重み付き平均に依存するので、その計算は本書で考えてきた問題より一般的な問題となる。この問題は第 5.19 節で考える。

ラプラシアンの応用としては他にグラフの描画がある。「スペクトルレイアウト (spectral layout)」や「スペクトルグラフ描画 (spectral graph drawing)」といった用語が登場する。例えば [Gallie13] を参照してほしい。