图的邻接矩阵与关联矩阵
我将为您详细讲解图的邻接矩阵与关联矩阵，这是图论中用于表示图结构的两种基本且重要的矩阵方法。
第一步：理解图的基本表示需求
在开始之前，我们需要明确一个核心问题：如何将直观的图形结构转化为计算机易于存储和处理的数学形式？图形虽然直观，但不便于进行大规模的代数运算。矩阵，作为一种强大的数学工具，可以完美地解决这个问题。它将图的结构信息（顶点和边的关系）编码成一个二维数组，使得我们可以运用线性代数的方法来研究图的性质。
第二步：定义邻接矩阵
邻接矩阵是描述图中各顶点之间连接关系的矩阵。
-
定义：对于一个具有 n 个顶点（标记为 v₁, v₂, ..., vₙ）的简单图（没有自环和重边），其邻接矩阵 A 是一个 n × n 的方阵。矩阵中的元素 aᵢⱼ 定义如下：
- aᵢⱼ = 1，如果顶点 vᵢ 和 vⱼ 之间有一条边相连。
- aᵢⱼ = 0，如果顶点 vᵢ 和 vⱼ 之间没有边相连。
-
示例：考虑一个具有4个顶点的图（四边形）。
- 顶点集合: {v1, v2, v3, v4}
- 边集合: {v1-v2, v2-v3, v3-v4, v4-v1}
- 它的邻接矩阵 A 为：
v1 v2 v3 v4
v1 [ 0 1 0 1 ]
v2 [ 1 0 1 0 ]
v3 [ 0 1 0 1 ]
v4 [ 1 0 1 0 ]
- 关键性质：
- 对称性：对于无向图，邻接矩阵总是对称的（即 A = Aᵀ），因为边是没有方向的。
- 对角线元素：在简单图中，所有对角线元素 aᵢᵢ 都为0，因为不存在顶点到自身的边（自环）。
- 顶点的度：矩阵中第 i 行（或第 i 列，因为对称）所有元素之和，就等于顶点 vᵢ 的度（即与该顶点相连的边的数量）。
第三步：扩展邻接矩阵到更复杂的图
上述定义是针对简单无向图的。现在我们来扩展它：
-
有向图：如果图是有向的，那么邻接矩阵的定义需要体现方向。此时，元素 aᵢⱼ = 1 表示存在一条从顶点 vᵢ 指向顶点 vⱼ 的边。在这种情况下，矩阵不再对称。第 i 行的和是顶点 vᵢ 的出度，第 i 列的和是顶点 vᵢ 的入度。
-
带权图：如果图的边具有权重（例如距离、成本），邻接矩阵可以推广为权重矩阵。此时，元素 aᵢⱼ 不再只是0或1，而是表示边 (vᵢ, vⱼ) 的权重。如果两点之间没有边，通常用0或无穷大（∞）来填充。
第四步：定义关联矩阵
关联矩阵是描述顶点与边之间关联关系的矩阵。它提供了另一种视角。
-
定义：对于一个具有 n 个顶点和 m 条边（标记为 e₁, e₂, ..., eₘ）的无向图，其关联矩阵 M 是一个 n × m 的矩阵。矩阵中的元素 mᵢⱼ 定义如下：
- mᵢⱼ = 1，如果顶点 vᵢ 是边 eⱼ 的一个端点。
- mᵢⱼ = 0，如果顶点 vᵢ 不是边 eⱼ 的端点。
-
示例：同样考虑那个四边形图。
- 顶点集合: {v1, v2, v3, v4}
- 边集合: {e1: v1-v2, e2: v2-v3, e3: v3-v4, e4: v4-v1}
- 它的关联矩阵 M 为：
e1 e2 e3 e4
v1 [ 1 0 0 1 ]
v2 [ 1 1 0 0 ]
v3 [ 0 1 1 0 ]
v4 [ 0 0 1 1 ]
- 关键性质：
- 每列的和：每列恰好有两个1，因为每条边都连接两个顶点。
- 每行的和：第 i 行所有元素之和，就是顶点 vᵢ 的度。
第五步：比较两种矩阵并理解其应用
| 特性 | 邻接矩阵 | 关联矩阵 |
|---|---|---|
| 维度 | n × n (顶点数 × 顶点数) | n × m (顶点数 × 边数) |
| 描述关系 | 顶点与顶点之间的邻接关系 | 顶点与边之间的关联关系 |
| 稀疏性 | 对于边数较少的稀疏图，矩阵中会有大量0 | 总是很稀疏，因为每列只有两个非零元 |
| 主要应用 | 计算路径数量、图的谱分析、网络中心性度量 | 电网络理论、拟阵理论、研究图的环路空间 |
一个重要的应用是计算路径数量：邻接矩阵 A 的 k 次幂 (Aᵏ) 中的元素 aᵢⱼ⁽ᵏ⁾ 的值，表示从顶点 vᵢ 到 vⱼ 长度为 k 的路径的总数。这展示了矩阵表示如何将图论问题转化为代数计算问题。