动机
顶点染色是把相邻的顶点分开。边染色则是把共享一个端点的任务分开:关联于同一顶点的边必须获得不同的颜色。每个高度数顶点立刻给出一个下界,但这种局部需求是否就是唯一的障碍,并不显然。
对二部图而言,答案是肯定的。一种证明把图补全为正则二部多重图,再反复移除完美匹配。第二种证明逐条插入边,并沿一条路径交换两种颜色来修复冲突。后者恰好说明了二部性为何能保证修复不会干扰另一个端点。
第一个证明使用先前已证明的二部图 Hall 定理;第二个证明则给出一个独立的直接构造。不满足二部性假设的一般边染色定理,在没有证明的情况下不予引入。
定义
定义 10.2.1
(正常边染色与最大度)
设 是有限无向二部多重图,其两侧指定为 。每条边在每一侧各有一个端点。允许带标号的平行边,不允许自环。度数把平行边分别计入。以 记最大度;当没有边时取 。
正常边染色是给每条边指定一种颜色,使得共享某个顶点的边颜色互不相同。其最小调色板大小称为边色数 ;无边图的边色数为零。每个单独的颜色类都是一个匹配。这一问题不同于对顶点指定颜色。
在使用调色板 的部分正常染色中,若某顶点没有任何当前已染色的关联边具有某颜色,则称该颜色在该顶点处缺失。固定两种不同的颜色 。只含这两种颜色已染色边的子图,其度数至多为二;它的各连通分支是路径、偶交错圈或孤立点。若某个分支含有缺失其中一种颜色的顶点,则它不可能是圈。
正则补全可以添加虚拟顶点和平行边。这些添加只服务于证明;在把较大的图分解为若干匹配之后,需要把每个颜色类限制回原来带标号的边。
定理/命题
定理 10.2.2
(二部图的边染色达到最大度这一界)
对每个有限二部多重图,
等价地,其边可划分为 个匹配;在描述固定调色板时允许某些类为空。该陈述包含平行边与不连通的情形。
定理 10.2.3
(正则二部多重图可分解为完美匹配)
设有限 -正则二部多重图满足 ,则其两侧大小相等,且存在完美匹配。反复移除完美匹配,可将其分解为 个边不相交的完美匹配。
每个最大度为 的有限二部多重图,都可通过添加顶点与边,扩充为两侧大小相等的 -正则二部多重图。限制其分解即可证明边染色定理。
定理 10.2.4
(双色路径修复给出直接算法)
设除一条边 (其中 )之外,其余边已使用 色调色板正常染色。取在 处缺失的颜色 与在 处缺失的颜色 。若二者不同,则包含 的双色子图分支不含 。交换该分支上的两种颜色后, 在两个端点处都缺失,因此 可染为 。
使用按颜色索引的关联表,在 个顶点上依次插入全部 条边需要 次基本操作与 的存储。这只是一个简单的构造性界,并非最快的边染色实现。
证明思路或证明
证明
(度数下界)
每组关联边都需要互不相同的颜色,所以 。当最大度为零时没有边,结论由空染色得到。下面给出匹配上界的两个完整证明。
正则性把 Hall 条件化为度数计数
证明
(正则分解与正则补全)
在 -正则二部多重图中,按左、右端点对所有边计数,得 ,所以两侧大小相等。对左侧任一子集 ,恰有 条边离开它,且全部终止于它的邻域集合。进入该集合的边总数至多为 。于是 。
已证明的 Hall 定理给出一个饱和左侧的匹配,因而由两侧大小相等,该匹配也饱和右侧。平行边不影响邻域判据:相应简单二部图中的匹配,可以对其每一对顶点在原有的边中任取一条可用边。移除该完美匹配会使每个顶点的度数减一。反复运用这一论证直至图中无边,即证明了正则分解。
对一般的图,添加孤立点直到两侧大小都等于 。每个顶点的亏量等于 减去其度数。任一侧的亏量之和为 ,所以两侧的总量相等。
若该总量为正,则在每一侧各选一个亏量为正的顶点,用一条新添的边连接它们,必要时允许产生平行边。两个亏量各减少一。重复这一步,恰在添加了亏量总数条边后终止。所有顶点的度数都变为 。分解补全后的图,并在每个匹配中只保留原图的边。这就给出原图使用所需调色板的一个正常边染色。
这一存在性证明并不假定正则补全仍是简单图。若在添加过程中强求简单性,将施加不必要的限制,并可能使这一初等构造失效。平行边的标号对度数计数与最终的限制都没有影响。
为何双色修复不会波及另一个端点
证明
(交错路径修复)
对于直接证明,按任意顺序处理原图的边。在插入 之前,每个端点至多有 条已染色的关联边,所以各自都有缺失的调色板颜色。若某颜色在两端都缺失,则立即使用它。否则如定理中那样选取不同的 。
在 处没有 边,所以它所在的双色分支是一条始于 的路径,或者是一个孤立点。若 属于这条路径,则由于 处缺失 ,该路径必定以 边开始,并以 边结束。交替性使其边数为偶数。但偶数长度的二部路径,其两个端点位于同一侧,而 位于相对的两侧。这一矛盾说明 不在该分支中。
在整个分支上交换 与 。在内部顶点处,关联的两种分支颜色只是互换;端点处每种颜色仍至多出现一次。依分支的定义,任一这两种颜色的边都不会从该分支跨到其补集,而其余颜色保持不变。因此各处的正常性都得以保持。
因为 原本在 处缺失,所以现在在那里缺失的颜色是 。顶点 不受影响,仍缺失 。把 赋给新边。这样就扩充了部分正常染色,因此对所有边作归纳即可构造性地证明该定理,包括多重图的情形。平行边对可能在别处构成两条边的交错圈,但缺失端点处的分支仍是路径,奇偶性论证仍然成立。
证明透视
二部性与度数上界在修复中何处用到
修复证明用到三个事实,各在一处。度数上界提供缺失的颜色:插入 之前,每个端点至多有 条已染色的边,所以 和 各有某种调色板颜色空出。正常性与 的选取决定了分支的形状: 没有 边,且至多有一条 边,所以 所在的分支是一条由 出发的路径,绝不是圈。二部性只在奇偶性一步用到。若路径到达 ,它会在 以 开始、在 以 结束;交错迫使边数为偶数,而偶数长的路径连接同一侧的两个顶点,但 、。
交换是安全的,因为该分支是一个完整的分支:没有 或 边离开它,所以交换两种颜色不会与分支外的边冲突。于是归纳逐边完成,而调色板从不增大。在三角形中失效的正是奇偶性这一步:由一个端点出发的路径可以终于另一个端点。
不必反复搜索每个关联边的修复实现
证明
(表格实现的成本)
对每个顶点和每种调色板颜色,存储该颜色的关联边的编号,或一个空标记。正常染色使这一表项即使在有平行边时也是唯一确定的。初始化这些表需要 的工作量。扫描其调色板,可在 时间内找到任一端点处缺失的颜色。
要找出始于 的分支,只需借助表查找沿交替的颜色前进。它是一条至多有 条边的路径,因为始于端点的最大度数为二的分支不会重访顶点。记录这些边,清除它们原先的关联表项,然后赋予互换后的颜色并写入新的表项。先清除可以避免覆盖更新过程中仍需使用的表项。分支的搜索与更新使用 的工作量与临时路径存储。
因此,初始化之后,每次插入边的代价为 。图及其颜色标号存储在 个边条目中,关联表存储在 个条目中。上述界计的是普通数组访问与有限整数下标;它并不把对任意外部标号的查找隐藏为常数时间操作。
直接算法无须实际构造可能大得多的正则补全。两个证明通过不同而有用的不变量建立同一个存在性定理:一个对正则图的每个度数层移除一个完美匹配,另一个则通过局部交错修复保持正常性。
例题详解
例题 10.2.5
(完全二部图 需要三种边颜色)
对 ,每个左顶点的度数为三,每个右顶点的度数为二。按右顶点的顺序,把第一个左顶点的三条边依次染为一、二、三,把第二个左顶点的三条边依次染为二、三、一。
每一行使用的颜色互不相同,每个右顶点看到两种不同的颜色,所以这是一个正常染色,并达到 。正则补全的证明添加一个虚拟左顶点,把它与全部三个右顶点相连,得到三正则图。其完美匹配所给出的颜色,限制后恰为这样一个有效的三色方案。
例题 10.2.6
(一条交错路径释放出所需的颜色)
设两侧为 与 。已染色的边为: 染色二, 染色一, 染色二, 染色一。现在插入未染色的边 。最终图的最大度为二。
颜色一在 处缺失,颜色二在 处缺失。 处的双色分支是路径 ,它不含 。交换其颜色,使这些边依次变为一、二、一。此时颜色二在 两处均缺失,所以把它赋给 。所有度数为二的顶点各看到每种颜色一次,而原有的边标号与端点都没有改变。
例题 10.2.7
(平行边说明边染色与顶点染色为何不同)
取分处两侧的两个顶点,用三条带标号的平行边将它们相连。其最大度为三,且三条边共享两个端点,所以三种不同的边颜色既是必要的,也是充分的。
相应的顶点染色问题只需要两种颜色。平行边并不增加新的顶点相邻要求,却增加了互相争夺边颜色的相异关联边。不能仅仅因为画的是同一个图,就用一个定理中的参数去替代另一个定理中的参数。
概念视角组合
一种边颜色就是一个匹配层
调色板把边集划分为若干组,每组都不重复使用任何端点。正则性使每一层覆盖每个顶点;非正则的图则使一些顶点在个别层中处于闲置。度数下界记录的是局部需求的最大个数,而二部性恰好使这些需求可以协调为恰好这么多个匹配层。
常见错误
反例模式
奇圈需要的颜色多于其最大度
三角形的最大度为二,却需要三种边颜色:它的三条边中每两条都相交。更一般地,奇圈无法在闭合处一致地交替使用两种颜色。三种颜色已经足够:沿除最后一条边之外的所有边交替使用一和二,再给最后一条边染色三。因此它的边色数为三,而最大度为二。
常见错误
(在到达另一端点的路径上交换)
不要在没有位于二部划分相对两侧的情形下套用双色端点论证。在三角形 中,设 染色一、 染色二,以调色板 插入 。颜色二在 处缺失,颜色一在 处缺失,但 所在的分支是路径 ,它到达了 。交换后 为颜色二、 为颜色一,于是 改为缺失一、 改为缺失二:冲突只是转移了。
常见错误
(颜色类不一定是完美匹配)
在非正则图中,颜色类是一个匹配,但不一定是完美匹配。两条边的路径有 ;它的两个颜色类各是一条边,各漏掉三个顶点中的一个。只有正则补全的各层才是完美匹配。
常见错误
(把虚拟边也报告出来)
正则补全中所用的虚拟边,在报告原图的染色之前必须移除。对 ,补全加入一个与全部三个右顶点相连的左顶点,而三个完美匹配各用到一条这样的新增边。报告的染色是限制到六条原有边上的染色。
总结
对有限二部多重图,最大度恰为边染色所需的颜色数。Hall 定理证明了正则图的完美匹配分解,而双色路径交换给出直接的增量算法。二部图的奇偶性排除了修复中的冲突;奇圈则说明了该假设以及它区别于顶点染色的必要性。
练习
快速检查
(利用行与列下标的规则,给出 的一个显式三边染色。)
使用下标零、一、二,并在模三下计算。
解答 · 答案
把每一侧用下标零、一、二标号。给边 染色 。沿固定的一行,三个列值使每种颜色恰好出现一次;沿固定的一列,三个行值也是如此。因此关联边的颜色总是互不相同。度数为三的下界证明了最优性。
快速检查
(对有 个叶子的星图,求其边色数与顶点色数。当 很大时,说明二者的差异。)
所有边都交于中心,但任意两片叶子不相邻。
解答 · 答案
星图的最大度为 ,所以它需要 种边颜色,在中心处每条边各占一种。它恰需要两种顶点颜色:一种给中心,另一种给全部叶子。由于至少有一条边,一种顶点颜色是不可能的。当 很大时,边的调色板增大,而顶点的调色板仍为二,直接说明了这两种约束的不同。
快速检查
(解释为什么始于缺失某一颜色的顶点的双色交错分支不可能是圈,并说明存在平行边时的情形。)
在使用任何奇偶性论证之前,先考察起始顶点在该分支中的度数。
解答 · 答案
正常性允许任一所选颜色在其关联边中至多出现一次。因此缺失其中一种颜色,会使该顶点在该子图中的度数为零或一。含有这样的顶点的连通分支是孤立点或路径,因为其所有顶点的度数至多为二。它不可能是圈,因为圈的所有顶点在分支中的度数都是二。由两条平行边构成的二边圈,其两个端点的度数同样是二,所以它不可能含有缺失颜色的顶点。随后的二部奇偶性论证适用于所得的路径。