图的拉普拉斯矩阵与谱图理论 基本定义与构造 设 \( G = (V, E) \) 是一个无向简单图，其顶点集 \( V = \{v_ 1, v_ 2, \dots, v_ n\} \)。图的拉普拉斯矩阵 \( L \) 是一个 \( n \times n \) 的对称矩阵，定义如下： 对角线元素 \( L_ {ii} \) 表示顶点 \( v_ i \) 的度数（即与 \( v_ i \) 相连的边的数量）。 非对角线元素：若顶点 \( v_ i \) 和 \( v_ j \) 之间有一条边，则 \( L_ {ij} = -1 \)；否则 \( L_ {ij} = 0 \)。 用矩阵形式可写为 \( L = D - A \)，其中 \( D \) 是度矩阵（对角矩阵），\( A \) 是邻接矩阵。 拉普拉斯矩阵的性质 半正定性 ：对任意实向量 \( x \in \mathbb{R}^n \)，有 \( x^T L x = \sum_ {(i,j) \in E} (x_ i - x_ j)^2 \geq 0 \)。这表明 \( L \) 的所有特征值非负。 零特征值 ：拉普拉斯矩阵的最小特征值总是 \( 0 \)，其对应的特征向量为全1向量（即 \( (1,1,\dots,1)^T \)）。若图连通，则零特征值的重数为1；若图有 \( k \) 个连通分支，则重数为 \( k \)。 特征值范围 ：拉普拉斯矩阵的特征值 \( \lambda_ 1, \lambda_ 2, \dots, \lambda_ n \) 满足 \( 0 = \lambda_ 1 \leq \lambda_ 2 \leq \dots \leq \lambda_ n \leq 2 \max(\text{度}) \)。 谱图理论的核心思想 谱图理论通过研究拉普拉斯矩阵（或邻接矩阵）的特征值来揭示图的组合性质。例如： 代数连通度 ：第二小特征值 \( \lambda_ 2 \)（称为Fiedler值）衡量图的连通强度。\( \lambda_ 2 \) 越大，图越难被分割（即需要移除更多边才能断开图）。 图的分割 ：特征值可用于分析图的割问题（如Cheeger不等式关联了 \( \lambda_ 2 \) 与图的最优割比例）。 应用示例：图划分与聚类 利用拉普拉斯矩阵的第二小特征值对应的特征向量（Fiedler向量），可以对顶点进行排序并实现图划分： 计算 Fiedler 向量 \( u_ 2 \) 的分量值。 按分量大小将顶点分为两组（如正负值分组），从而得到近似最优的割。 此方法广泛应用于图像分割、社区发现等领域。 归一化拉普拉斯矩阵 为消除顶点度数不均的影响，常使用归一化拉普拉斯矩阵 \( L_ {\text{sym}} = D^{-1/2} L D^{-1/2} \) 或 \( L_ {\text{rw}} = D^{-1} L \)。它们的特征值范围在 \( [ 0, 2 ] \) 内，更适合分析异质度图。 扩展方向 高阶拉普拉斯算子 ：用于研究图的高维拓扑结构（如单纯形复形）。 动态图分析 ：通过跟踪拉普拉斯谱的变化监测网络演化。 图信号处理 ：将特征向量视为傅里叶基，实现图上的滤波与压缩。 通过拉普拉斯矩阵的谱分析，可将图的结构问题转化为线性代数问题，为理解复杂网络提供强大工具。