1. 概述
在本教程中，我们将讨论 什么是 Incident Edge（关联边），以及它在有向图和无向图中的表现形式。
理解这个概念有助于我们更好地掌握图论中的一些核心操作，比如计算顶点度数、边着色问题、边覆盖问题等。
2. 核心概念
简单来说：
✅ 如果两条边共享一个公共顶点，那么它们就是“关联边”（incident edges）
✅ 顶点也可以与边相关联。如果一个顶点是某条边的端点之一，那么该顶点就与这条边“关联”（incident）
举个例子：假设我们有两条边 e₁ 和 e₂，它们有一个共同的顶点 V，那么 e₁ 和 e₂ 就是关联边。
再比如，如果边 e₃ 连接了顶点 V₁ 和 V₂，那么我们说 e₃ 与 V₁ 和 V₂ 都是关联的。
⚠️ 注意：顶点和边之间的“关联”关系是双向的，既可以说边关联于顶点，也可以说顶点关联于边。
3. 无向图中的例子
我们来看一个无向图的例子：
图 G₁ 包含顶点集合 V = {A, B, C, D, E}，边集合 E = {E₁, E₂, E₃, E₄, E₅, E₆}
我们可以观察到以下关联关系：
- 边 E₁、E₂、E₃ 都连接顶点 A → 所以它们是相互关联的
- 顶点 A 与边 E₁、E₂、E₃ 相关联
- 边 E₁ 和 E₄ 共享顶点 B → 所以它们是关联边
- 顶点 B 与边 E₁ 和 E₄ 相关联
以此类推，我们可以找出图中其他边和顶点之间的关联关系。
4. 有向图中的例子
接下来我们看一个有向图的例子：
图 G₂ 的顶点集合为 V = {A, B, C, D, E, F}，边集合为 E = {E₁, E₂, E₃, E₄, E₅, E₆, E₇, E₈}
观察图中关联关系：
- 边 E₁ 和 E₂ 都从顶点 A 出发 → 它们是关联边
- 顶点 A 与边 E₁ 和 E₂ 相关联
- 边 E₁ 从 A 指向 B → 所以 E₁ 与 B 是关联的（从 A 出发）
- 边 E₂ 从 A 指向 C → 所以 E₂ 与 C 是关联的（从 A 出发）
✅ 有向图中边具有方向性，因此我们在描述“关联”时，通常会加上方向信息，例如“边 E₁ 从顶点 A 关联到顶点 B”。
⚠️ 踩坑提醒：在有向图中，判断边是否关联时，方向不影响“共享顶点”的判断，但描述时建议说明方向，以避免歧义。
5. 应用场景
关联边的概念在图论中非常基础且实用，常见应用包括：
✅ 计算顶点度数（Vertex Degree）
- 顶点的度数 = 与该顶点关联的边的数量
- 在无向图中直接统计即可
- 在有向图中分为入度（in-degree）和出度（out-degree）
✅ 边着色问题（Edge Coloring）
- 要求：任意两个关联边不能使用相同颜色
- 目标：用最少颜色完成着色
- 参考：Vizing 定理指出颜色数量最多为最大度数 Δ 或 Δ+1
✅ 边覆盖问题（Edge Cover）
- 目标：找出一个边集合，使得图中每个顶点至少与集合中的一条边相关联
- 该集合中的每条边都“覆盖”了一个或多个顶点
6. 总结
在本教程中，我们讲解了：
- 什么是关联边（Incident Edge）
- 无向图和有向图中的关联关系
- 如何判断边与边、边与顶点之间是否关联
- 该概念在图论中的几个关键应用场景
理解“关联”这一概念，有助于更深入地掌握图结构的分析与算法设计。