概念

边染色

边色数刻画「相邻边不同色」的最小颜色数，Vizing 定理说明边色数只可能是 Δ 或 Δ+1，直接应用于排课与调度问题。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

边染色图论

01定义

边染色要求有公共端点的边颜色不同，最少颜色数即边色数

\chi'(G)

。维津定理给出惊人的精确刻画：简单图的边色数只可能是

\Delta

或

\Delta+1

——二分类干净利落，直接服务排课与调度。

边染色 = 把边集分解为互不相邻的匹配

简单图 $\chi'=\Delta$ （第一类）或 $\Delta+1$ （第二类）；二部图恒为 $\Delta$ （柯尼希定理），奇圈为 $\Delta+1$ 。判定第二类是 NP 完全。

每种颜色的边构成匹配，故边染色恰是把 $E$ 分解为最少匹配；排课问题「每个时段=一色」即此模型。

列表边染色猜想（Galvin 已证二部图情形）、全染色猜想（顶点与边同时染）——边染色家族仍是活跃前沿。

\Delta(G)\leq\chi'(G)\leq\Delta(G)+1\quad(\text{维津})

柯尼希 1916 年证明二部图边染色定理；维津 1964 年给出一般图的二分类定理；霍利约克与古普塔完善了证明细节。

课程表编排（教师-班级-时段）、光纤波分复用（信道分配）、循环赛日程表构造、交换机的时隙调度。

边染色：二部图的 Δ 色定理逐步上色：共享端点的边不同色

step 已着色边数0