为什么给图着色?
设共用资源的任务不能同时执行。把任务看作顶点,在有冲突的两项任务之间连边,再用颜色表示时段:相邻顶点必须颜色不同。在这个模型中,所需的最少颜色数就是最少时段数。图只记录两两冲突;若还有其他调度限制,则需要补充模型。
定义 5.3.1
(合法着色与色数)
设 是有限简单无向图。合法的 -着色是映射 ,使每条边 的两端满足 。色数 是可行的最小 ;空图规定为 。团是任意两个不同顶点均相邻的顶点集合。非空图的最大度记为 。
每个颜色类都是独立集;颜色多于实际所需时,某些颜色类可以为空,而非空颜色类构成顶点集的划分。大小为 的团必须使用 种不同颜色,因此 。这只是下界,不一定取等号:其他边也可能迫使我们增加颜色。
概念视角结构
把着色看作到完全图的映射
合法 -着色就是图同态 ,即把每条边映到边的顶点映射。 的顶点就是颜色,两种颜色相邻当且仅当它们不同,所以“边映到边”恰好表示相邻顶点颜色不同。用这种语言, 是使 存在同态的最小 ,而图可用两色着色当且仅当它可映到 。
这个描述可以复合。若 是同态、 是合法着色,则 是 的合法着色,故 。取子图 的包含映射,得到 ;取 团的包含映射 ,便得到团下界 。
贪心着色
选定次序 。处理 时,给它分配尚未被已着色邻点使用的最小正整数。之后处理的邻点会避开 的颜色,因此不会破坏这一步。
定理 5.3.2
(贪心度数界)
任意非空有限简单图在任意顶点次序下,贪心着色均合法且至多使用 种颜色。更精确地说,若在所选次序中每个顶点至多有 个更早的邻点,则至多使用 种颜色。
证明
(计算被禁用的颜色)
处理某顶点时,更早的邻点至多禁用 种颜色。因此 中至少有一种可用。每条边都有一个较晚处理的端点;该端点会避开另一端点的颜色,所以最终着色合法。每个顶点的邻点总数不超过 ,便得到度数界。选择较好的次序可能改善上界,但不保证得到最优着色。
例题 5.3.3
(奇圈与最优性证明)
在圈 上按顺序处理,贪心给出 。前四个顶点交替着色,最后一个顶点看到两种颜色。三色足够;两色不可能,因为沿前四条边交替后, 与 颜色相同,但二者相邻。故 ,虽然最大团只有两个顶点。
两色与奇圈
定义 5.3.4
(二分图)
若图 的顶点集可划分为 ,且没有任何边的两端同时属于 或同时属于 ,便称 为二分图。允许其中一类为空。
两类都是独立集;给 用颜色 1、给 用颜色 2,就得到合法两色着色。反过来,任何合法两色着色的两个颜色类也给出这样的划分。因此二分性和可用两色着色描述的是同一性质:前者用集合划分表述,后者用颜色标签表述。
定理 5.3.5
(二分图判别法)
有限简单图可用两种颜色合法着色,当且仅当它没有奇圈。这里“可用两色”指两色的调色板足够,亦包括无边图和空图。
证明
(广度优先距离的奇偶性)
在合法两色着色中,沿路径颜色交替。若存在奇圈,绕圈回到起点时会得到与原来相反的颜色,矛盾。
反之,假设没有奇圈。对每个连通分支选根 ,并选定一棵 BFS 父树。树中从 到每个顶点的路径都是最短路径,记其长度为 ,再按 的奇偶把顶点分为两类。若 是边,在到 的最短路径后接上该边,就得到 ;交换两端,同理有 。所以相邻顶点到根的距离至多相差一;若奇偶性相同,距离必定相等,记为 。
假设存在这样的边。两条树路径共用一段从根开始的路径,直至最后公共祖先;设该祖先到根的距离为 。在此之后,两段路径没有公共顶点,长度各为 。这两段路径加上该边构成长度为 的简单圈。它是奇圈,矛盾。因此每条边都连接不同奇偶类。给两类不同颜色即可;孤立顶点也没有困难。各连通分支分别处理。
证明透视
没有奇圈这一假设在哪里使用
正方向只需要颜色沿每条边交替。反方向依靠两个步骤。第一,每条边上的距离不等式 把“奇偶相同”变成等式 ;仅凭奇偶性并不能说明两条树路径等长。第二,停在最后公共祖先,使两段尾路径只在该点相交,于是尾路径、该边与反向尾路径构成简单圈,而不是可能重复顶点的闭游走。由于 ,有 ;假设恰好只使用一次,用来排除长度为奇数 的这个圈。论证要在每个连通分支分别进行,因为 只在 所在的分支上有定义。
例题 5.3.6
(贪心结果取决于次序)
设边为 ,即四顶点路径。按 的次序,贪心得到 。但 、 已是合法着色。因此一次贪心运行只给出上界,不能单凭它证明所用颜色数最少。
用删除法寻找合适的次序
较早邻点数的精确界启发我们选择次序。假设每个非空子图内部都有一个度不超过 的顶点。反复删除这样的顶点并记录次序,直至没有顶点;然后按相反次序着色。恢复某顶点时,已经恢复的邻点恰是删除它时仍留在子图中的邻点,最多有 个。因此贪心至多用 色。这里的度是在当前子图内计算,不一定等于原图中的度。
例如森林的每个非空子图都有度至多为一的顶点:非平凡树有叶,孤立顶点则度为零。删除法给出森林的两色着色。非空无边森林只需一色;含边的森林需要两色。这得到准确答案,但没有声称森林的每个顶点次序都只用两色;前面的四顶点路径已否定后者。
例题 5.3.7
(为什么必须倒转删除次序)
再看路径 。依次删除 ,它们在被删除时的度分别为 。特别是 原本的度为二,但删除它时,邻点只剩 。按相反次序 着色,得到 :恢复 和 时,各自只看到 ;恢复 时,只看到 。每个顶点至多有一个较早着色的邻点,因此可以使用两色界。
如果直接按删除次序 着色,反而得到前面使用三色的结果。删除时的较小度数计算的是删除后仍留在图中的邻点;只有倒转次序,这些邻点才会先被着色。因此只记录较小的剩余度数、却不倒转次序,并不能证明所声称的界。
从定理到证据
要核对图可用 色着色,只须检查每条边两端的颜色。要证明它至少需要 色,则需要另一种证据。 个顶点的团就是一种证据,但五圈说明它不是唯一方法:奇圈排除了两色,而一个具体的三色着色给出配套上界。要确定准确的色数,两部分都不可少。尝试着色失败,本身不能证明不存在合法着色。
例题 5.3.8
(上下界相遇)
取顶点为 的三角形,加入顶点 ,令它与 相邻,但不与 相邻。三角形需要三色。令 ; 可能具有颜色 3 的邻点是 ,但二者之间没有边。因此三色足够,也达到下界:。只数顶点只能给出较弱的上界四,而只指出三角形只能得到下界。
空图需要单独约定: 时,唯一的空着色不使用颜色,故 。非空无边图的色数是 。非连通的非空图的色数等于各连通分支色数的最大值:整个图的着色限制在每个分支上,仍是合法着色;反之,每个分支的最优着色可以重复使用同一组颜色。因此这里取最大值,而不是求和。
找到着色或奇圈
广度优先搜索(BFS)把奇偶性证明变为可执行的方法。在每个尚未访问的连通分支中选根,令根的距离为零,逐层访问邻点,并在首次发现顶点时记录其父顶点。根据 BFS 距离的奇偶性给每个顶点着色。如果每条边连接不同奇偶类,就得到合法两色着色。如果一条边的端点奇偶性相同,它们的距离实际上相等,因为相邻顶点的距离至多相差一。从两端沿父指针回溯到最后一个公共祖先,两段树路径加上该边便构成奇圈。
例题 5.3.9
(构造奇圈)
设边为 ,从 开始 BFS。 的距离是 , 的距离是 , 的距离是 。边 的两端奇偶性相同。父路径分别为 和 ,最后公共祖先是 ;加上 便得到长度为五的圈 。这是不能两色着色的可核验证据;仅有 BFS 父路径并不矛盾,必须检查到边 才能得到这个结论。
使用邻接表时,BFS 对每个顶点和每条边只处理常数次,故运行时间为 。图不连通时,必须从每个尚未访问的顶点重新开始:只检查根所在分支可能漏掉其他分支的奇圈。若使用邻接矩阵,扫描所有可能邻点需要 时间。这些是针对所述图表示的算法界,并不包括取得图数据的成本。
次序能有多差?
差的贪心次序不只可能多用一种颜色。对于 ,取顶点 ,恰在 时连接 。所有 与所有 分别构成两个独立集,给出两色着色;图中有边,所以色数恰为二。现在按 处理。归纳可知 和 均获得颜色 :每个顶点都从较早的另一类顶点看到所有较小颜色,而 与 不相邻。因此贪心使用 色,最优解却只需两色。这解释了为什么某一次运行的颜色数只是上界,而不是最优性证明。
度数界仍然成立:每个顶点的度是 ,因此这次贪心恰好使用 色。某算法的上界可以达到,并不意味着图的色数也必须达到该上界。要给出更好的结论,可以寻找更好的次序,或用其他方法构造着色,再配合下界。
只有完全图与奇圈:其他连通图都可用不超过最大度的颜色数着色。
自然的下一个问题
哪些连通图真的需要比最大度多一种颜色?
只有完全图与奇圈:其他连通图都可用不超过最大度的颜色数着色。
完全图 与奇圈(此时 )需要 种颜色。Brooks 定理指出它们是仅有的连通例子:既不是完全图、也不是奇圈的连通图满足 。它的证明仍是贪心着色,只是精心选取次序,使最后一个顶点的邻点中出现重复的颜色。这个界仍可能与 相差很远,正如常见错误中的星图所示。
常见错误
常见错误
(度数数的是邻点,不是被禁用的颜色)
邻点的数量不一定等于被禁用的颜色数。在中心为 、有 个叶的星图中,中心的度是 ,但所有叶都可以共用一种颜色,因为任意两片叶之间都没有边。给叶用颜色 1,给中心用颜色 2,就得到合法着色。图中有边,排除了一色,所以无论 多大,色数都恰好是二。度数界之所以有效,是因为不同禁用颜色的数量至多等于较早邻点的数量,并不要求这些邻点彼此颜色不同。
常见错误
(可用两色不等于色数为二)
“可用两色”表示两种可用颜色已经足够,并不要求两种都出现。非空无边图可用两色,但色数是一;二分图判别法刻画的是 ,而 恰好在此之外图还有边时成立。
二分图判别法也容易引出一个看似合理的捷径,五个顶点的图就能否定它。
反例模式
排除三角形不等于排除奇圈
声称:没有三角形的图可用两色着色。取顶点按循环次序为 的 。每个顶点 恰有两个邻点 与 (下标按模 计),而这两点不相邻,所以没有三角形。然而两色着色会沿 交替为 ,于是 的颜色与 不同,即与 相同,但 是边。因此 不能两色着色。修正方法是使用判别法的完整假设:必须排除所有奇圈,而不只是长度为三的奇圈;或者直接给出合法划分。
练习
快速检查
(求 时的 ,并说明上下界。)
解答 · 答案
全部 个顶点构成团,至少需要 色;每个顶点用不同颜色可达到 色,所以 。
快速检查
(图的最大度为 且含三角形,可得什么界?分别举例达到两个端点。)
解答 · 答案
三角形给出 ,贪心界给出 。三角形加一个悬挂顶点的最大度为 ,可用三色; 的最大度为 ,需要四色。
快速检查
(按 的次序对路径 贪心着色。为什么至少需要两色?)
解答 · 答案
依次为 。图中有边,一色不可能,故色数为 。
快速检查
(图由互不相连的 、三角形和一个孤立顶点组成。求其色数。)
解答 · 答案
各分支的色数为 。在每个分支重复使用同三种颜色; 给出下界三。因此答案为 ,不是 。
快速检查
(从 出发的 BFS 父边为 ,另有边 。找出奇圈。为何必须利用这条边,而不能只看父树?)
解答 · 答案
圈为 ,长度为五。父树本身没有圈;额外的边 把两条父路径闭合。
快速检查
(边为 的图的色数是多少?)
解答 · 答案
构成三角形,至少需要三色。令 。由于 不相邻,这是合法着色,故 。