图着色问题是什么？它和二分图有什么关系？
简化版
图着色是给图中的节点分配颜色，要求相邻节点颜色不同。
二分图判断可以看成 2 色着色问题：如果一个图能用两种颜色给所有节点染色，并且相邻节点颜色不同，那么它就是二分图。
一般的 k 色着色更难，常用于排课、寄存器分配、冲突资源安排等建模。
详细版
图着色问题关注冲突约束。
如果两个任务不能同时使用同一资源，就在它们之间连一条边；着色就是给任务分配资源编号，使相邻任务不同色。
| 问题 | 图模型 |
|---|---|
| 二分图 | 是否能用 2 种颜色 |
| 排课 | 相邻表示时间冲突 |
| 寄存器分配 | 相邻表示变量生命周期冲突 |
| 地图染色 | 相邻地区颜色不同 |
二分图可以用 BFS/DFS 染色在线性时间判断，但一般 k 色着色问题通常复杂得多。
完整版教学
1. 图着色的基本定义
图着色是给每个顶点分配一个颜色。
要求是：
如果 u 和 v 有边相连，那么 color[u] != color[v]目标可能是判断能否用 k 种颜色完成，也可能是尽量用更少颜色。
2. 二分图就是 2 色问题
二分图可以把节点分成两个集合，所有边都跨集合连接。
这等价于：
用 2 种颜色给图染色，相邻节点颜色不同所以判断二分图时，经常用 BFS 或 DFS 交替染色。
二分图是图着色中最常见、最容易在线性时间处理的特殊情况。
3. BFS 染色怎么做
从一个未染色节点开始，给它颜色 0。
遍历邻居：
- 如果邻居未染色，染成相反颜色；
- 如果邻居已染色且颜色相同，说明不是二分图。
color[start] = 0
for v in neighbors[u]:
if color[v] unset:
color[v] = 1 - color[u]
else if color[v] == color[u]:
conflict如果图不连通，要对每个连通分量都执行。
4. 奇环为什么会导致不能 2 色
奇数长度环无法用两种颜色交替染完。
例如三角形：
A - B - C - A如果 A 是红色，B 必须蓝色，C 必须红色，但 C 又和 A 相邻，冲突。
因此无向图是二分图的充要条件之一是不存在奇环。
5. k 色问题为什么更难
当 k = 2 时，可以线性判断。
但一般 k 色着色，尤其是判断是否能用 3 种颜色完成，是经典困难问题。
| 颜色数 | 难度直觉 |
|---|---|
2 | BFS/DFS 可判 |
3 | 一般图上很难 |
| 更多颜色 | 常需要搜索、贪心或近似 |
面试里通常不会要求完整求最优染色，但会考建模和二分图特例。
6. 图着色有哪些应用
图着色适合表达冲突关系。
| 应用 | 点 | 边 | 颜色 |
|---|---|---|---|
| 排课 | 课程 | 时间冲突 | 时间段 |
| 寄存器分配 | 变量 | 生命周期重叠 | 寄存器 |
| 会议安排 | 会议 | 参会人冲突 | 会议室或时间 |
| 地图染色 | 区域 | 相邻 | 颜色 |
只要问题是“有冲突的对象不能放同一组”，就可以想到图着色。
7. 贪心染色怎么理解
工程上有时用贪心近似。
按某个顺序遍历节点，给当前节点分配第一个不与邻居冲突的颜色。
for u in order:
used = colors of colored neighbors
color[u] = smallest color not in used它简单快速，但不保证颜色数最少。
8. 常见误区与追问
- 误区：图着色只和地图有关。 它本质是冲突资源分配模型，应用很广。
- 误区：二分图和图着色无关。 二分图判断就是
2色着色问题。 - 误区：贪心染色一定最优。 贪心依赖遍历顺序，通常不保证最少颜色。
- 追问：为什么奇环不能二染色？ 两色交替一圈后，奇数长度会让首尾颜色冲突。
- 追问：不连通图怎么染色？ 对每个连通分量分别启动 BFS 或 DFS。