11.6 图着色与平面性

第 11.1–11.5 节把边看作需要保存的关系、需要优化的连接或可以行走的路线。边还可以表示冲突：若两门考试有共同学生，就不能安排在同一时段；若两个无线发射器互相干扰，就不能使用同一频道。

图着色要在相邻顶点不能获得同一资源的前提下分配有限资源。平面性则研究另一个设计问题：能否在没有交叉的情况下画出所有边？

正常顶点着色

顶点着色为每个顶点分配一种颜色。若所有相邻顶点颜色都不同，就称着色是正常的：

其中 $c(v)$ 表示分配给顶点 $v$ 的颜色。

颜色只是标签，可以代表时间段、频率、寄存器、存储区域，也可以是真正的颜色。

若一张图存在最多使用 $k$ 种颜色的正常着色，就称它是$k$-可着色的。所需颜色数的最小值称为色数，记作

独立集是一组两两之间都没有边的顶点。正常着色中的每个颜色类都是独立集，因为同色顶点不能相邻。

在三角形 $K_3$ 中，每一对顶点都相邻，所以必须且只需三种颜色：

这里，$K_n$ 表示含 $n$ 个顶点的完全图，其中每一对不同顶点都相邻。

下界与上界

团是一组两两相邻的顶点。如果图中存在大小为 $r$ 的团，那么其中每个顶点都要使用不同颜色，所以

这只是下界，不一定就是精确答案。

一个简单的上界来自贪心过程。先选定顶点顺序，然后依次为每个顶点分配尚未被已着色邻居使用的最小编号颜色。

若最大度为

那么处理某个顶点时，至多有 $\Delta(G)$ 种邻居颜色被禁止。因此贪心着色最多使用

种颜色。

结果会受到顶点顺序影响。较差的顺序可能使用超过实际需要的颜色，所以贪心着色只能给出上界，不能自动证明 $\chi(G)$ 的精确值。

二分图与两种颜色

如果顶点能被分成互不相交的集合 $X$ 与 $Y$，且每条边的两个端点分别属于两个集合，就称这张图是二分图。$X$ 内部与 $Y$ 内部都没有边。

给 $X$ 中所有顶点一种颜色，给 $Y$ 中所有顶点另一种颜色，就证明每张非空二分图都可以用两种颜色正常着色。

反过来，任何正常的两色着色都会把顶点分成两个独立颜色类，所以图是二分图。因此

还可以通过路线判断：

先看正向：沿环前进时颜色必须交替，要回到起点的原颜色，边数必须是偶数。再看反向：在每个连通分量中运行 BFS，把偶数距离层涂成一种颜色，奇数距离层涂成另一种。若同一奇偶层内部存在边，就会形成奇环。

为实时考试冲突网络安排时段：直接分配颜色并立即观察冲突，改变贪心调度顺序，显示团所给出的下界，再切换到二分图场景，让 BFS 层成为二着色证书。

图的绘制、交叉与平面图

绘制一张图时，用点表示顶点，用连接端点的曲线表示边。边可以在共同端点处相遇。若两条边的内部相交，就产生一个交叉。

若一张图至少存在一种没有交叉的画法，就称它是平面图。一幅已经没有交叉的具体图形称为平面嵌入图。

必须区分图与画法：平面图也可能被画得交叉重重，移动顶点或改变边的路线可以消除这些交叉。反过来，仅仅没能解开某一幅画，也不能证明原图不平面。

无交叉绘制会把平面分成若干区域，这些区域称为面。外部无界区域也算一个面。

每张连通平面嵌入图都满足

这就是平面图的欧拉公式。它把抽象的顶点数、边数与无交叉绘制中的区域数连接起来。

对树而言，$|E|=|V|-1$，而且只有外部这一个面。代入可得

说明这个公式延续了第 10 章的树性质。

简单平面图的边数上界

设一张连通简单平面图有 $n=|V|\ge3$ 个顶点、$m=|E|$ 条边。若每个面的边界至少出现三条边，那么统计所有面边界上的边出现次数可得

因为每条边会位于两个面的边界侧。再结合 $|F|=2-n+m$，得到

这是简单平面图的必要条件。若简单图违反该不等式，就一定不平面；满足它却不能证明一定平面。

二分图没有奇环，所以简单二分平面图不存在三角形面。每个面边界至少出现四条边，于是得到更强的上界

两张基本非平面图

完全图 $K_5$ 满足

所以它不是平面图。

完全二分图 $K_{r,s}$ 有两个大小分别为 $r$ 与 $s$ 的顶点组；两个组之间所有可能的边都存在，而每个组内部没有边。对于 $K_{3,3}$，

所以二分平面图上界证明 $K_{3,3}$ 不平面。

普通上界 $m\le3n-6$ 无法排除 $K_{3,3}$，这说明利用图的结构可以加强计数论证。

证书与适用边界

要证明一张图平面，可以给出无交叉绘制或精确描述一种嵌入。要证明一张图不平面，只要适用，违反边数上界就是充分证据；但并非每张非平面图都会违反基本上界。

交叉数量属于某一种画法，平面性则属于图本身。可拖动的图形有助于发现嵌入并建立直觉，但数学结论仍需要证书：用零交叉绘制证明平面，或用有效的不可能性论证证明不平面。

拖动顶点来解开直线边图形，几何扫描器会指出每一处交叉。比较能够达到零交叉的平面棱柱图与 $K_5$、$K_{3,3}$；后两者无论怎样拖动，边数证书都会阻止成功。

第 11 章总结

图用来描述对象与关系。各种表示方法把模型转化为数据；度统计局部关联；路线定义连通性；BFS、DFS 与 Dijkstra 用于探索或优化路径；生成树算法构造最低成本连接骨架；欧拉与哈密顿问题区分边覆盖和顶点覆盖；着色分配互相冲突的资源；平面性则通过计数限制图的画法。

第 2.4 节已经用布尔代数描述了即时决策。第 12 章会进一步加入状态变化：有限状态机描述受控转移，最终项目则把这些思想与本章的网络模型结合起来。