1. 引言
图论是计算机科学中的重要基础之一。在图结构中，顶点（Vertex）和边（Edge）构成了图的基本元素。邻接（Adjacency） 和 关联（Incidence） 是图论中两个核心概念，它们分别描述了顶点之间的连接关系以及顶点与边之间的归属关系。
本文将介绍这两个概念，并通过邻接矩阵、邻接表和关联矩阵三种常见图表示方法，帮助读者更深入地理解图的结构与操作。
2. 图的基本概念
一个图 $ G = (V, E) $ 由顶点集合 $ V $ 和边集合 $ E $ 构成。每条边是一个顶点对 $ (v_i, v_j) $，表示这两个顶点之间存在连接。
如下图所示，一个包含 5 个顶点和 6 条边的图：
3. 邻接（Adjacency）
定义
如果两个顶点之间通过一条边相连，则称这两个顶点是邻接的。例如，在上述图中，顶点 $ v_1 $ 的邻接顶点是 $ v_2 $ 和 $ v_3 $。
根据邻接关系，我们可以使用以下两种方式来表示图：
3.1 邻接矩阵（Adjacency Matrix）
邻接矩阵是一个 $ |V| \times |V| $ 的二维矩阵，其中：
- 若顶点 $ v_i $ 和 $ v_j $ 之间有边，则 $ A[i][j] = 1 $
- 否则为 $ 0 $
例如，上述图对应的邻接矩阵如下：
| v₁ | v₂ | v₃ | v₄ | v₅ | |
|---|---|---|---|---|---|
| v₁ | 0 | 1 | 1 | 0 | 0 |
| v₂ | 1 | 0 | 1 | 1 | 0 |
| v₃ | 1 | 1 | 0 | 0 | 1 |
| v₄ | 0 | 1 | 0 | 0 | 1 |
| v₅ | 0 | 0 | 1 | 1 | 0 |
特点：
- 空间复杂度：$ O(|V|^2) $
- 建立时间复杂度：$ O(|E|) $
- 查询边是否存在：$ O(1) $
- 删除边：$ O(1) $
✅ 适合稠密图（边的数量接近 $ |V|^2 $）
❌ 空间浪费较大，不适合稀疏图
3.2 邻接表（Adjacency List）
邻接表是一种链式结构，每个顶点对应一个链表，链表中存储与该顶点邻接的所有顶点。
例如，上述图对应的邻接表如下：
v₁ → v₂, v₃
v₂ → v₁, v₃, v₄
v₃ → v₁, v₂, v₅
v₄ → v₂, v₅
v₅ → v₃, v₄
特点：
- 空间复杂度：$ O(|E|) $
- 建立时间复杂度：$ O(|E|) $
- 查询边是否存在：$ O(|V|) $
- 删除边：$ O(|V|) $
✅ 适合稀疏图
❌ 查询效率较低
3.3 邻接矩阵 vs 邻接表
| 操作 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 存储空间 | $ O( | V |
| 判断边是否存在 | $ O(1) $ | $ O( |
| 删除边 | $ O(1) $ | $ O( |
| 插入边 | $ O(1) $ | $ O(1) $ |
📌 总结：
- 稠密图：推荐使用邻接矩阵
- 稀疏图：推荐使用邻接表
4. 关联（Incidence）
定义
在图中，如果两条边共享一个公共顶点，则它们是关联的。例如，边 $ (v_1, v_2) $ 和 $ (v_1, v_3) $ 是关联的，因为它们都连接了顶点 $ v_1 $。
另外，一个顶点与一条边是关联的，如果该顶点是这条边的两个端点之一。因此，关联可以表示为一个顶点和一条边的组合 $ {v, e} $。
4.1 关联矩阵（Incidence Matrix）
关联矩阵是一个 $ |V| \times |E| $ 的矩阵，行表示顶点，列表示边：
- 若顶点 $ v_i $ 是边 $ e_j $ 的端点，则 $ M[i][j] = 1 $
- 否则为 $ 0 $
例如，上述图的关联矩阵如下：
| e₁ | e₂ | e₃ | e₄ | e₅ | e₆ | |
|---|---|---|---|---|---|---|
| v₁ | 1 | 1 | 0 | 0 | 0 | 0 |
| v₂ | 1 | 0 | 1 | 1 | 0 | 0 |
| v₃ | 0 | 1 | 1 | 0 | 1 | 0 |
| v₄ | 0 | 0 | 0 | 1 | 0 | 1 |
| v₅ | 0 | 0 | 0 | 0 | 1 | 1 |
特点：
- 空间复杂度：$ O(|V||E|) $
- 建立时间复杂度：$ O(|E|) $
📌 用途：
- 主要用于理论图论研究，如图的关联着色（Incidence Coloring）
- 实际应用较少，因其空间开销较大
5. 总结
本文介绍了图论中的两个基本概念：邻接 和 关联，并分别介绍了它们在图表示中的应用方式：
- 邻接：描述顶点之间的连接关系，可通过邻接矩阵或邻接表表示
- 关联：描述顶点与边之间的归属关系，可通过关联矩阵表示
📌 不同表示方式的适用场景：
| 表示方式 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 邻接矩阵 | 查询、修改快 | 空间大 | 稠密图 |
| 邻接表 | 空间小 | 查询效率低 | 稀疏图 |
| 关联矩阵 | 结构清晰，适合理论研究 | 空间复杂度高 | 图论研究、算法分析 |
✅ 在实际开发中，选择合适的图表示方式可以显著提升性能，尤其在处理大规模图数据时。