第 27 章 线性代数在图论与网络中的应用¶
前置：矩阵基础 (Ch02) · 特征值 (Ch06) · 组合矩阵结构 (Ch65B)
本章脉络：从图到矩阵的映射 \(\to\) 邻接矩阵 (Adjacency Matrix) 及其性质 \(\to\) 度矩阵 (Degree Matrix) \(\to\) 核心对象：拉普拉斯矩阵 (Laplacian Matrix) \(L = D - A\) \(\to\) 矩阵-树定理 (Matrix-Tree Theorem) \(\to\) 谱图论 (Spectral Graph Theory) 初步：特征值与连通性 \(\to\) 代数连通度 (Fiedler 向量) \(\to\) 关联矩阵 (Incidence Matrix) \(\to\) 应用：Google PageRank 算法的线性代数解释、社区发现（谱聚类）、电阻网络计算
延伸：图论是离散的线性代数；它将矩阵的每一行看作网络中的节点，将非零元看作流动的渠道，证明了网络的拓扑性质完全编码在其谱结构中，是现代社交网络分析与互联网搜索的代数灵魂
图（Graphs）是由顶点和边构成的离散结构。谱图论（Spectral Graph Theory）通过研究与图关联的矩阵的特征值和特征向量，揭示了图的连通性、瓶颈和对称性。通过将“找路径”的问题转化为“求特征值”的问题，线性代数为大规模复杂网络提供了极其高效的全局解析工具。本章将介绍如何利用矩阵代数来“阅读”图的几何蓝图。
27.1 核心矩阵定义¶
定义 27.1 (邻接矩阵 \(A\))
对于 \(n\) 个顶点的图 \(G\)，\(A\) 是一个 \(n \times n\) 矩阵： $\(a_{ij} = \begin{cases} 1 & \text{若顶点 } i, j \text{ 相连} \\ 0 & \text{否则} \end{cases}\)$ 性质：\(A^k\) 的 \((i,j)\) 元素代表从 \(i\) 到 \(j\) 长度为 \(k\) 的路径数量。
定义 27.2 (拉普拉斯矩阵 \(L\))
定义为 \(L = D - A\)，其中 \(D = \operatorname{diag}(\text{各顶点的度})\)。 性质：\(L\) 始终是半正定的，且其零特征值的个数等于图的连通分量个数。
27.2 矩阵-树定理¶
定理 27.1 (Matrix-Tree Theorem)
图 \(G\) 的所有生成树（Spanning Trees）的数量，等于 \(L\) 矩阵任一主子式的行列式值。 意义：这一结论实现了从极大规模组合枚举到行列式计算的惊人跨越。
27.3 谱聚类与分层¶
技术：Fiedler 向量
拉普拉斯矩阵的第二小特征值 \(\lambda_2\) 称为代数连通度。 其对应的特征向量（Fiedler 向量）的分量符号可以将图划分为两个内部紧密、相互松散的社区。这是图像分割和社交网络分群的标准算法。
练习题¶
1. [基础] 写出三角形图（三个顶点两两相连）的邻接矩阵 \(A\)。
参考答案
构造： 所有 \(i \neq j\) 的位置都是 1，对角元为 0。 \(A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}\)。
2. [计算] 计算上述三角形图的拉普拉斯矩阵 \(L\)。
参考答案
步骤： 1. 计算度矩阵：每个顶点度数为 2。\(D = \operatorname{diag}(2, 2, 2)\)。 2. \(L = D - A = \begin{pmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{pmatrix}\)。 验证：每一行之和均为 0，这是拉普拉斯矩阵的普遍特征。
3. [路径计数] 若邻接矩阵 \(A\) 的 \(A^2\) 中 \((1, 3)\) 元素为 2，这意味着什么？
参考答案
结论： 意味着从顶点 1 到顶点 3 存在 2 条长度为 2 的路径。 例如 \(1 \to 2 \to 3\) 和 \(1 \to 4 \to 3\)。
4. [生成树] 利用矩阵-树定理计算三角形图的生成树数量。
参考答案
步骤： 1. 取 \(L\) 的一个主子式（划掉第一行第一列）：\(\begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}\)。 2. 计算行列式：\(2 \cdot 2 - (-1)(-1) = 4 - 1 = 3\)。 结论：共有 3 棵生成树。对于三个顶点的全联通图，显然三条边中去掉任意一条都能得到一棵生成树。
5. [特征值] 证明：拉普拉斯矩阵 \(L\) 的最小特征值始终为 0。
参考答案
证明： 1. 观察 \(L\) 的每一行之和均为 0。 2. 令向量 \(\mathbf{1} = (1, 1, \ldots, 1)^T\)。 3. \(L\mathbf{1} = \mathbf{0} = 0 \cdot \mathbf{1}\)。 结论：1 是 \(L\) 对应于特征值 0 的特征向量。
6. [连通性] 若 \(L\) 有两个特征值为 0，该图具有什么拓扑结构？
参考答案
结论：该图由两个不连通的子图组成。 理由：特征值 0 的几何重数等于图的连通分量数。这说明系统存在两个独立的“零能量”模态，互不干扰。
7. [二部图] 判定：二部图的邻接矩阵特征值有什么对称性质？
参考答案
结论：谱关于原点对称。 理由：若 \(\lambda\) 是特征值，则 \(-\lambda\) 也是。这是因为二部图的邻接矩阵可以化为分块反对角形式 \(\begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}\)。
8. [应用] Google PageRank 的核心计算是一个特征值问题吗？
参考答案
是的。 PageRank 寻找的是概率转移矩阵 \(P\)（基于网页链接图构造）的主特征向量（对应特征值 1）。 \(P\mathbf{x} = \mathbf{x}\)。 特征向量分量 \(x_i\) 的大小即代表了网页 \(i\) 的重要性排名。
9. [关联矩阵] 什么是图的关联矩阵 \(M\)？它与拉普拉斯矩阵有何关系？
参考答案
定义与关系： 1. \(M\) 的行对应顶点，列对应边。若边 \(k\) 连接 \(i, j\)，则 \(M_{ik}=1, M_{jk}=-1\)（有向情形）。 2. 核心等式：\(L = M M^T\)。 这证明了拉普拉斯矩阵本质上是一个 Gram 矩阵（见 Ch16），其半正定性由此得到完美解释。
10. [应用] 简述谱聚类（Spectral Clustering）在图像处理中的基本思想。
参考答案
- 将像素视为节点，像素相似度视为边权。
- 构造加权拉普拉斯矩阵。
- 求前 \(k\) 个最小特征值对应的特征向量。
- 将特征向量作为新坐标，对像素进行聚类。 优势：能够识别复杂的、非凸形状的物体轮廓，这在传统的 K-means 算法中是难以实现的。
本章小结¶
线性代数是解析网络拓扑结构的“通用显微镜”：
- 拓扑的谱表示：它证明了宏观的连通性、分群和树结构都可以浓缩为微观的特征值序列，实现了离散几何与连续代数的不对称统一。
- 流动的代数本质：从 PageRank 到电阻网络，线性代数揭示了网络上的扩散与平衡过程本质上是算子作用下的能量极小化。
- 计算的飞跃：矩阵-树定理等结论展示了代数形式如何通过“降维打击”，将原本不可能完成的组合计数任务转化为标准的矩阵运算，是现代信息检索与社交分析的数学基座。