图拉普拉斯矩阵

图拉普拉斯矩阵是描述图结构的矩阵，是谱图理论的核心对象，在聚类、图信号处理与网络分析中有广泛应用。

定义

设有限、无自环、无重边的无向图 $G=(V,E)$，$n\ge1$，，顶点数 $n=|V|$，邻接矩阵 $A$，度矩阵 $D=\operatorname{diag}(d_1,\dots,d_n)$（$d_i$ 为顶点 $i$ 的度），则（组合）拉普拉斯矩阵为

$$L = D - A$$

分量形式

$$L_{ij} = \begin{cases} d_i & i=j \\ -1 & i \sim j \text{（相邻）}\\ 0 & \text{其他} \end{cases}$$

基本性质

• 半正定：$x^T L x = \sum_{i \sim j} (x_i - x_j)^2 \ge 0$，故特征值非负
• 最小特征值 $\lambda_1 = 0$，对应特征向量为全 1 向量（任何此类图均成立；连通时零特征空间是一维）
• 特征值中 0 的重数 = 连通分量个数
• 当 $n\ge2$ 时，第二小特征值 $\lambda_2$（Fiedler 值）刻画图的连通程度，用于谱聚类

复杂度注记

稠密对称矩阵求全部特征对的标准算法通常需立方量级运算。稀疏矩阵只求少数特征对时可用 Lanczos 等迭代法，每次矩阵向量乘法约需 $O(\operatorname{nnz}(L))$ 运算；总成本还取决于迭代次数、谱间隙、精度及正交化，不能保证统一的 $O(n^{3/2})$。输出全部特征向量本身已有 $n^2$ 个元素。

二次型中的求和每条无向边只计一次。若 $Lx=0$，由非负平方和可知每条边两端的 $x_i$ 相等，即 $x$ 在每个连通分量上为常数；各分量的指示向量组成零空间的基，证明了零特征值重数等于连通分量数。加权无向图可令 $A_{ij}=w_{ij}=w_{ji}\ge0$、$D_{ii}=\sum_jw_{ij}$，相应平方和加上权重。