ラプラシアン行列
グラフ中の連結成分(英語版)の数はラプラシアンの零空間の次元であり、0固有値の代数的多重度である。
Lの最小の非ゼロ固有値はスペクトルギャップ(英語版)と呼ばれる。
Lの2番目に小さな固有値(ゼロかもしれない)はGの代数的連結度(英語版)(Fiedler値)であり、グラフの最疎カットを近似する。
ラプラシアンは、関数 f : V → R {\textstyle f:V\to \mathbb {R} } ( V {\textstyle V} はGの頂点セット、 n = | V | {\textstyle n=|V|} )のn次元ベクトル空間上の作用素である。
Gがk正則である時、正規化ラプラシアンは L = 1 k L = I − 1 k A {\textstyle {\mathcal {L}}={\tfrac {1}{k}}L=I-{\tfrac {1}{k}}A} である(Aは隣接行列、Iは単位行列)。
複数の連結成分を持つグラフについて、Lは区分対角行列であり、それぞれの区分はそれぞれの成分についての(場合によると頂点を順序付けし直した後の)各ラプラシアン行列である(すなわちLは区分対角行列と置換相似である)。
ラプラシアン行列Lの跡(トレース)は 2 m {\textstyle 2m} ( m {\textstyle m} は考慮されているグラフの辺の数)と等しい。
グラフ上の酔歩に関する余談として、単純無向グラフを考える。酔歩者が時間tに頂点iにいる確率を考え、酔歩者が時間t-1に頂点jにいた確率分布を仮定する(任意の頂点に結合したいかなる辺に沿った一歩について一様の見込みを仮定する):
p i ( t ) = ∑ j A i j deg  ( v j ) p j ( t − 1 ) , {\displaystyle p_{i}(t)=\sum _{j}{\frac {A_{ij}}{\deg \left(v_{j}\right)}}p_{j}(t-1),}
または行列-ベクトル記法で:
p ( t ) = A D − 1 p ( t − 1 ) . {\displaystyle p(t)=AD^{-1}p(t-1).}
( t → ∞ {\textstyle t\rightarrow \infty } として設定される平衡は p = A D − 1 p {\textstyle p=AD^{-1}p} として定義される。)
この関係は
グラフラプラシアン行列は、有限差分法によって得られた(半正定値)ラプラシアン作用素に対する近似の行列形式としてさらに見ることができる。この解釈では、グラフの全ての頂点はグリッド点として扱われる; 頂点の局所連結性はグリッド点における有限差分近似ステンシル(英語版)を決定し、グリッドのサイズは常に全ての辺について1であり、いかなるグリッド点上にも制約はない。これは斉次なノイマン境界条件、すなわち自由境界の場合に相当する。