图 Laplacian

把 $x_u$ 看作顶点 $u$ 上的温度或电势。每条边都惩罚两端数值的差，$x^{\mathsf{T}}Lx$ 汇总了全图的不协调能量。若能量为零，正权边两端必须取相同值；沿路径传播后，每个连通分量只能保持一个常数。Laplacian 因而把图的连通结构转写成矩阵的核。

$Lx$ 在顶点 $u$ 的分量是 $d_u{x}_u-\sum _v{w}_{uv}{x}_v$，也就是本点值与邻居加权值之间的差。它与连续空间中的 Laplace 算子承担相似角色：检测局部偏离平衡的程度，但图上没有坐标或微分，全部信息由边给出。

三顶点路径 $P_3$ 的 Laplacian 为

其特征值是 $0,1,3$。唯一零特征方向由常向量张成，反映图连通。完全图 $K_n$ 的 Laplacian 是 $nI-J$，谱为 $0$ 一次、$n$ 重数 $n-1$；高对称性把所有与常向量正交的振动方向赋予相同能量。若图由两个互不相连的连通图组成，分别取两个分量的示性向量便得到两个线性无关的零特征向量。

这些结论不能原样套到有向图：邻接矩阵不再对称，$D-A$ 可能不是对称半正定矩阵。允许负边权时，上式会成为带符号的平方项之和，二次型可能取负值，因而失去半正定性。组合 Laplacian、归一化 Laplacian 与随机游走 Laplacian $I-D^{-1}A$ 还具有不同的特征值尺度；比较谱隙时必须先固定所用规范。

由核的刻画可立即得到：有限无向图连通，当且仅当 $0$ 是 $L$ 的单特征值。第二小特征值因此衡量离断开还有多远，并把连通性公理库图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。与割的瓶颈联系起来。Rayleigh 商

把寻找低能量顶点函数转为特征值问题，是谱划分和扩张估计的入口。

Laplacian 的任一主余子式还出现在矩阵树定理中，用行列式计数生成树公理库生成树Spanning tree包含原图全部顶点且自身为树的子图。；其伪逆编码电网络的有效电阻。随机游走、扩散、谱聚类和图信号平滑看似来自不同应用，实质上都在使用同一个“邻边差异能量”。