图的边着色问题 边着色问题关注如何为图的边分配颜色，使得任何两条相邻边（即共享一个公共顶点的边）获得不同的颜色。所需的最少颜色数称为图的边色数，记作 χ'(G)。 基本定义与动机 边着色 ： 设 G=(V, E) 是一个图（可以是简单图，也可以是多重图）。一个 边 k-着色 是从边集 E 到颜色集合 {1, 2, ..., k} 的一个函数 c: E → {1, 2, ..., k}。 正常边着色 ： 如果一个边着色满足对任意两条相邻的边 e 和 f，都有 c(e) ≠ c(f)，则称该着色为正常的或 正常边着色 。 边色数 ： 图 G 的 边色数 χ'(G) 是使得 G 存在正常边 k-着色的最小正整数 k。 动机 ： 边着色可以建模许多调度问题。一个经典的例子是课程表问题：将顶点视为教师，边视为课程（连接授课教师），颜色视为不同的时间段。任何一位教师不能在同一时间段上两门课，这就转化为相邻的边必须着不同颜色。 平凡下界与 Vizing 定理 简单下界 ： 对于任意图 G，其边色数有一个明显的下界：χ'(G) ≥ Δ(G)。其中 Δ(G) 是图 G 中顶点的最大度数。原因很简单：与最大度顶点关联的所有 Δ 条边都必须彼此颜色不同。 Vizing 定理（核心结论） ： 对于任何简单图（无环、无重边）G，其边色数 χ'(G) 要么等于 Δ(G)，要么等于 Δ(G)+1。即 χ'(G) ∈ {Δ(G), Δ(G)+1}。 图分类 ： 根据 Vizing 定理，简单图被分为两类： 第一类图 ： 满足 χ'(G) = Δ(G) 的图。 第二类图 ： 满足 χ'(G) = Δ(G) + 1 的图。 例子 ： 偶圈（如正方形）是 Δ=2 的第一类图（χ'=2）。 奇圈（如三角形）是 Δ=2 的第二类图（χ'=3）。 完全图 K_ n： 当 n 为奇数时，χ'(K_ n) = n（第一类）；当 n 为偶数时，χ'(K_ n) = n-1（第二类）。 二分图的边着色（König 定理） 一个非常重要的结论是：对于 二分图 （特别是树），其边色数恰好等于最大度。即，如果 G 是二分图，则 χ'(G) = Δ(G)。这被称为 König 线着色定理 。 这个定理保证了二分图总是第一类图。证明思路通常使用对最大度 Δ 的归纳法，并利用二分图的性质（无奇圈）来构造 Δ 种颜色的边着色。 边着色的算法 判断一个简单图是属于第一类还是第二类是 NP-困难的。然而，存在多项式时间算法可以为任何图 G 找到一个使用至多 Δ(G)+1 种颜色的正常边着色。这由 Vizing 定理保证。 贪心着色 ： 一种简单的方法是依次为每条边着色，每次分配可用的最小颜色编号（即不与已着色的相邻边冲突的最小颜色）。这种方法最多使用 Δ(G)+1 种颜色。 更优的算法 ： 对于二分图，存在更高效的算法，如基于匈牙利算法或网络流技术的算法，可以在 O(m√n) 或类似复杂度内找到使用 Δ 种颜色的最优边着色。 推广与相关概念 多重图的边着色 ： 对于允许有重边的多重图，Vizing 定理不再成立。多重图的边色数下界是最大度，但上界可以更高。一个重要的定理是 Shannon 定理 ：对于任何多重图 G，有 χ'(G) ≤ ⌊3Δ(G)/2⌋。 列表边着色 ： 这是边着色的一个推广。为每条边 e 赋予一个可用颜色的列表 L(e)。问题是为每条边从其列表中选择一种颜色，使得相邻边颜色不同。 列表边色数 χ'_ l(G) 是保证无论如何分配颜色列表（每个列表大小至少为 k），都存在正常列表边着色的最小 k。著名的 列表边着色猜想 （由 Vizing 等人提出）断言，对于任意图 G，有 χ'_ l(G) = χ'(G)。这个猜想尚未被普遍证明。 边着色的应用 ： 除了排课，边着色还应用于任务调度、资源分配、通信网络中的波长分配（光网络路由）等领域。