9.4 着色
本章目录 · 1 节
本章导读
【本节范围】依次讨论点着色、地图面着色、平面图点着色和边着色。这里“无环”指没有自环,不是没有回路;有普通圈的图仍可着色。自环会要求一个顶点或一条边与自身取不同颜色,所以排除它。重边不改变点着色的约束,但会影响边着色及度数。
【定义9.4.1:点着色与色数】给每个顶点一种颜色,使相邻点颜色不同,称合法点着色。若能用不超过 种颜色完成,称 可着色;所需的最少颜色数为 。同色点组成独立集,故点着色也是把顶点分成若干独立集。非空零图需要1色;顶点集为空时通常约定色数0。
工作排期时以任务为点、不能同日完成的冲突为边,一种颜色代表一天,最少天数为色数。寄存器分配中,同时活跃且不能共用寄存器的变量相邻,一种颜色代表一个寄存器。无线设备分配中,互相干扰的设备相邻,一种颜色代表一个允许使用的波长。这些模型都以先明确冲突关系为前提,不能把任意两项任务都连边。
【例9.4.1:基本点色数】(1)非空图 当且仅当它没有边。(2),因为任意两点都相邻。(3)偶圈可用两色交替,奇圈不能两色交替而可用三色。轮图 的外圈是 ,中心必须用外圈未用的新颜色,所以总阶数 为奇数时色数3,为偶数时色数4。(4)至少含一条边的无自环图,色数2当且仅当它是二部图;二部划分直接给两色,而合法两色的两类顶点反过来给出二部划分。
【定理9.4.1:最大度上界】无自环图满足 。可按阶数归纳:删去一点 ,先给其余图用 色着色; 至多有 个不同邻点,至多禁用这么多颜色,因此至少剩一色可用。也可逐点贪心着色得到同一上界,不能据此断言贪心一定用了最少颜色。
【定理9.4.2:Brooks定理】对 的连通简单图,若它不是完全图,也不是奇圈,则 。完全图和奇圈是需要保留的例外;对不连通图应分别考虑连通分支,不能去掉连通条件而直接沿用例外的表述。本节不展开其完整证明。若原图含平行边,点着色可先取其基础简单图再应用这个版本。
【例9.4.2:四幅图的点色数】下图给出实际可行的着色;同一种填充色代表同一类颜色。
【解】(a)是至少有边的二部图,故 。两种颜色分别放在二部的两类点上,立方体图的每条连接边都跨两类。
(b)外圈为五边形,需要3色,中心邻接全部外围点,必须用第4色,所以 ,不是3。
(c)为彼得松图,最大度3,连通且既非完全图又非奇圈,Brooks定理给 ;外五圈是奇圈,给 ,故 。内部无圆点交叉不增添顶点。
(d)外三角形三点必须各用不同颜色。三个中层点分别邻接外三角形的两端,因此在仅用3色的假设下,它们被迫分别使用第三种颜色,三个中层点于是用齐3色。最内点邻接这三点,不能再用其中任何一色,至少需要4色。图中实际给出4色方案,故 ;最大度4与Brooks上界也一致。不能只凭图有奇圈就断定需要4色,奇圈本身只推出至少3色。
【地图与定义9.4.2:面着色】教材把连通、无桥平面图的固定嵌入及其全部面称地图,各面称国家。两国相邻是指边界至少共享一条边,只在一点接触不算相邻。给相邻国家不同颜色,称面着色;最少颜色数为面色数 。外部面也算国家,不可遗漏。
【定理9.4.3:面着色转为对偶点着色】地图 的 可面着色,等价于对偶图 的 可点着色,因此 。证明来自国家与对偶点一一对应、共享边与对偶点相邻一一对应。原图无桥,故对偶图无自环;对偶仍可有普通圈和平行边,不能把“无自环”误写或误读为“没有任何圈”。
【定理9.4.4:四色定理】任意无自环平面图均可用不超过4色点着色,从而任何上述地图也可用不超过4色面着色。多条平行边不增加点着色约束,故可先化为基础简单图。包含 的平面图确实需要4色,上界不代表每幅图都必须用满4色。
四色问题起于19世纪的地图着色研究;Heawood在1890年证明五色定理,Appel与Haken在1976年给出计算机辅助的四色证明。其思路涉及不可避免构形与可约性的有限验证,不是枚举“所有平面图只有有限几种”,也不是只检查若干普通例图就得到定理。本节陈述定理,不将历史说明冒充完整证明。
【定义9.4.3:边着色与边色数】给每条边一种颜色,使有公共端点的两条不同边颜色不同,称合法边着色;所需最少颜色数记为 。区分 、 和 ,分别是点、面、边的色数。一点关联的全部边两两相邻,故总有 。
【定理9.4.5:Vizing定理】简单图满足
这个上界不能直接用于任意含重边的图。定理只将简单图的取值限制在两种可能中,不能不看具体图就任选其一;本节不展开一般判别算法或完整证明。
【定理9.4.6:二部图的边着色】无自环二部图的边色数为 ,这也允许平行边,边数为0时边色数为0。与点着色“非空边二部图用2色”不同,这里是在边上着色,最大度可以远大于2。
【例9.4.3:圈的边色数】偶圈的边可两色交替,边色数为2;奇圈不能两色交替,却可先交替给前偶数条边着色,再给最后一条第三色,故边色数3。简单偶圈至少有4边;教材提到的长度2偶圈,是允许两条平行边的二边圈,它的边色数同样为2。
【例9.4.4:轮图的边色数】对 ,证明 。
【解】中心关联 条边,给出下界 。当 ,两图分别展示3色和4色合法方案,达到下界。对于 ,先给各辐条分配互不相同的 色,再沿外圈逐边着色。
每条外圈边要避开两端的两条辐条颜色,以及已经着色的相邻外圈边颜色。最后一条还同时邻接第一条和前一条,最多共禁4色,所以5色以上的现有颜色集中始终还有可用色。这样给出整个圈的完整构造,不把最后闭合的一条边遗漏。因此 ,与下界结合得等式。
【例9.4.5:完全图的边色数】对奇数 ,;对偶数 ,。 没有边,另有 。
【解】若 为奇数,同色边组成匹配,至多含 条边。全图有 边,故至少用 色;Vizing给出至多 色,所以等号成立。
给一个更明确的构造:将奇数阶完全图的顶点编号为模 的 。给边 分配满足 的颜色 。因 为奇数,2可逆;在固定顶点 处,其他端点 不同便得到不同颜色,且恰缺颜色 。
当 时只有一条边,显然只需1色。以下取偶数 ,先按上述规则给外围的奇数阶 用 色着色;在中心加一点,并把连接外围点 的新边着成它原来恰缺的颜色 。每个外围点仍无同色相邻边,中心的 条边颜色也互异,达到最大度下界 。图中 ,五种颜色各形成三边完美匹配,覆盖全部十五条边。
