图的矩阵表示：不止邻接矩阵
前面我们学习了邻接矩阵来表示图的连接关系。 本章介绍图论中的其他重要矩阵：关联矩阵（节点-边关系）、度矩阵（节点度数）、拉普拉斯矩阵（图的谱性质）。
这些矩阵不仅是图的不同表示方式，更是分析图结构、 实现图算法（如谱聚类）的基础工具。
✦
21.2
关联矩阵
节点与边的关系矩阵（V × E）
关联矩阵（Incidence Matrix）的行对应节点，列对应边。 对于有V个节点、E条边的图，关联矩阵的形状为V × E。 无向图中元素为0或1，有向图中元素为-1、0或+1（表示边的方向）。
🔄 线图（Line Graph）
定义
• 原图G的边变成线图L(G)的节点
• 若两条边在G中共享节点，则在L(G)中连接
• 若两条边在G中共享节点，则在L(G)中连接
关联矩阵关系
AL = CT C - 2I
线图的邻接矩阵可由原图的关联矩阵计算
✦
21.3
度矩阵
对角矩阵，对角线元素 = 节点度数
度矩阵（Degree Matrix）是一个对角矩阵， 其对角线元素D[i][i]表示节点i的度数，非对角线元素为0。 对于有向图，可以分别定义入度矩阵和出度矩阵。
📐 度矩阵计算
D = diag(A · 1)
邻接矩阵A的行和（或列和）构成的对角矩阵
• 无向图：D[i][i] = 节点i的度
• 有向图：分别计算入度和出度
🎯 度矩阵用途
• 拉普拉斯矩阵：L = D - A
• 归一化邻接矩阵：D-1A
• 随机游走：转移矩阵 = D-1A
• 度中心性：识别重要节点
• 谱方法：图信号处理
✦
21.4
拉普拉斯矩阵
图的谱分解与聚类
拉普拉斯矩阵（Laplacian Matrix）定义为度矩阵与邻接矩阵之差： L = D - A。它是对称半正定矩阵，编码了图的重要结构信息。 通过谱分解（特征值分解），可以实现图聚类、社区检测等任务。
✨ 拉普拉斯矩阵的深刻意义
几何意义
• 离散版拉普拉斯算子
• 度量函数在图上的"平滑度"
• (Lf)i = 节点值与邻居均值之差
谱性质
• 对称半正定：λ ≥ 0
• λ₁ = 0，v₁ = [1,1,...,1]
• λ₂：代数连通度（Fiedler值）
• 0特征值数 = 连通分量数
应用场景
• 谱聚类：社区检测
• 图分割：最小割
• 图嵌入：Laplacian Eigenmaps
• 图信号处理：滤波平滑
🎯 谱聚类：从拉普拉斯到社区发现
1
构建拉普拉斯矩阵 L = D - A
2
谱分解：L = VΛV^T
3
取第二特征向量（Fiedler向量）
4
按符号分割：v₂ > 0和v₂ ≤ 0
为什么使用第二特征向量？
第一特征向量v₁ = [1,1,...,1]无法区分节点。 第二特征向量v₂（对应第二小特征值λ₂）给出了最优的二分割， 最小化割边数同时保持簇的平衡。
✦
本章小结
本章介绍了图的三种重要矩阵表示：关联矩阵（节点-边关系）、度矩阵（节点度数）、拉普拉斯矩阵（谱性质）。 这些矩阵是图论与线性代数的桥梁，为图分析提供了强大的数学工具。
📊 三种矩阵对比
关联矩阵 C
• V × E（节点 × 边）
• 无向图：0/1，有向图：-1/0/+1
• 描述节点-边关系
• 无向图：0/1，有向图：-1/0/+1
• 描述节点-边关系
度矩阵 D
• V × V（对角矩阵）
• D[i][i] = 节点i的度
• 非对角线元素=0
• D[i][i] = 节点i的度
• 非对角线元素=0
拉普拉斯矩阵 L
• V × V（对称矩阵）
• L = D - A
• 编码图的谱性质
• L = D - A
• 编码图的谱性质
🎯 核心应用
1
网络流分析
关联矩阵用于建模流量守恒
2
中心性分析
度矩阵识别重要节点（hub）
3
谱聚类
拉普拉斯谱分解实现社区检测
4
图信号处理
拉普拉斯算子用于图上的滤波
✨ 图论 + 线性代数 = 强大的分析工具 ✨
邻接矩阵只是起点
关联、度、拉普拉斯矩阵揭示更深层的结构
谱方法：将图问题转化为线性代数问题