动机
在最大度顶点处,每条关联边都需要不同的颜色。这给出了边染色的一个下界;但贪心地选取颜色可能会卡住,即使每个顶点都还有未用的颜色。下一条边两端可用的颜色可能并不相同。
扇在保持正常性的同时移动未染色边的位置。双色路径则改变哪些颜色可用。二者的结合需要小心:一次路径互换可能破坏扇的某个条件。下面的证明准确指出这个条件,并说明哪段扇前缀仍然可用。
本节把二部图的结果推广到每个简单图,给出构造性上界、取得该上界的例子与初等实现的代价。它不判定某个图是否只用最大度种颜色便已足够,也不把简单图的结论推广到任意平行边。
比较证明见 Misra 与 Gries 的构造性论述。这里明确追踪变化的扇关系并核算初等实现。
定义
定义 10.3.1
(部分边染色与缺失颜色)
设 为 个顶点的有限简单无向图,最大度为 。正常部分边染色是指给某些边赋予颜色,使得在同一顶点处关联的、已染色的不同边颜色互不相同;其余的边保持未染色。若一个顶点的当前已染色关联边都没有使用某种颜色,则称该颜色在该顶点处缺失。
使用固定的、含 种颜色的颜色集。即使一个顶点的所有关联边都已染色,它处仍至少有一种缺失颜色。在带有未染色关联边的顶点处至少有两种缺失颜色,不过证明只需要选定其中一种缺失颜色。
固定一条未染色边 。以 为中心的顺序扇是由互不相同的邻点构成的列表 ,并且对每个 ,边 已染色,其颜色在 处缺失。扇的任一前缀仍是扇。图是简单图,所以每个扇邻点唯一确定一条中心边。
若不存在新的邻点 ,使得中心边 已染色、且其颜色在当前最后一个顶点处缺失,则称该顺序扇是极大的。这里的极大指的是这张特定列表不能再延长,而不是指在所有列表中扇顶点数最多。
对于两种不同的颜色 ,由这两种颜色的已染色边构成的子图在每个顶点处度数至多为二。它的连通分支是交替路径、偶数长度的交替圈以及孤立顶点。在整个一个连通分支上互换 与 的颜色,仍然保持正常部分边染色。
定理/命题
定理 10.3.2
(扇可以搬运未染色边而不产生冲突)
设 是一个扇,并且颜色 在 与 处都缺失。对 从一到 ,把 的颜色移到 上,同时随着空位前进而把它从 上移除。然后用 给最后的空位 染色。
所得的部分染色是正常的,并且恰好多了一条已染色边。只有被选中的中心边发生了变化;其他未染色边不受影响。
定理 10.3.3
(一次双色路径互换总能产生可用的扇前缀)
对于每条未染色边及其极大顺序扇,取 在中心处缺失、 在最后一个顶点处缺失。要么 已经在中心处缺失;要么在包含中心的连通分支上互换 之后,得到一个扇前缀,它的最后一个顶点与中心处都缺失 。
前缀的选取取决于某个特定的前驱顶点是否在该路径上。互换之后不加区分地旋转旧的扇,并不属于该定理的内容。
定理 10.3.4
(最大度的下界至多需要多一种颜色)
每个有限简单图都满足
其中 是正常边染色所需的最少颜色数。无边图的 与 均为零。反复进行扇/路径插入即可构造出满足上界的染色。
借助带下标的邻接表和顶点-颜色关联表,直接实现需要 时间和 存储空间,其中 为边数。这些只是初等的字操作界,并不是经过优化的边染色运行时间,也不是最小颜色集的判定算法。
证明思路或证明
沿着扇移动空位
证明
(扇的旋转)
起初 是空位。 上的颜色在 处缺失,于是把它从 上移除并放到 上。在 处,该颜色只是在两条关联边之间移动,从不会重复出现。在 处它原本缺失,而在 处把它移除不会产生冲突。
继续向前进行。即将移动的颜色在原染色中于其接收方扇顶点处缺失。之前的空位移动并没有把该颜色引入那里:之前的每个接收方都是不同的顶点,而当前的接收方只是清除了它自己的中心边。因此每一步移动都保持正常。等价地说,最终的旋转使每个接收方得到其后继原先的颜色,并移除最后一条中心边的颜色。
在 处,旋转前后出现的颜色集合不变。在最后一个扇顶点处,唯一变化的关联边被清除。因此原来在两处都缺失的颜色 ,旋转后在该处仍然缺失。把它放在最后的空位上,已染色边数增加一,这就证明了第一个定理。只有一个顶点的扇则直接给原来的边染色。
延长扇,直到每条可能的下一条中心边都得到处理
证明
(延长为极大扇)
从只含 的列表开始。每当从 出发的某条已染色边到达列表之外的邻点,并且其颜色在当前最后一个顶点处缺失,就把该邻点添加进去。每个添加的顶点都是新的,所以该过程至多添加 的度数那么多个顶点后停止。所得列表在上述延长意义下是极大的。
选取在 处缺失的颜色 ,以及在最后一个顶点 处缺失的颜色 。若 在 处也缺失,则整个扇立即可用,无需路径互换。否则 与 不同。由于部分染色是正常的,在 处关联的 色边是唯一的。
极大性蕴含这条 色边是已染色扇边之一:若其邻点在扇之外,则由于 在 处缺失,该邻点可以被添加。把它记作 ,其中 ,并令 。扇的条件说明 在 处缺失。注意 不同于最后一个顶点。
从中心出发进行互换,并追踪唯一受威胁的条件
证明
(路径互换及其两种情形)
设 为包含 的 连通分支。在 处有一条 色边而没有 色边,所以 在该分支中的度数为一。一个有限连通、最大度为二且带有这样一个端点的图是简单路径,而不是圈。它的第一条边颜色为 。沿 互换这两种颜色。结果仍是正常的,并且 现在在 处缺失。
互换之前,没有扇边的颜色是 ,因为 在 处缺失。只有 的颜色是 。因此其他每条扇边的颜色都在 这一对之外。它们的边颜色及其在前驱处的缺失状态在互换后保持不变。唯一可能需要修复的扇关系,是涉及 及前驱 的那一个。
分两种情形。
若 不在 上,则它仍然缺失 。终止于 的前缀不含 ,所以它的全部扇关系都属于未变化的那些。该前缀可用,其最后一个顶点 与中心 处都缺失 。旋转这个前缀即完成。
若 在 上,则互换之前它缺失 。这样的顶点不可能是一条非平凡 路径的内部顶点,因为内部顶点各有一条每种颜色的边。因此它是 以外的另一个端点。它关联的路径边颜色为 ,互换后 在那里缺失。同时,中心边 的颜色由 变成 ,所以它的颜色现在在 处缺失。先前受威胁的扇关系得到恢复。
最后一个顶点 在互换前缺失 。若它属于 ,则它也会是一个端点。但 的两个端点是 与 ,都不同于 。因此最后一个顶点在 之外,仍然缺失 。现在所有扇关系都成立,所以整个扇可用。旋转它,并用 给其最后的空位染色。
证明透视
一个例外关系决定前缀的选取
简单性、极大性与正常性各在一处用到。极大性把 处唯一的 色边放进扇内,成为某条 ,其中 ;没有它,这条边可能通往列表之外的顶点。正常性加上 在 处缺失,使 成为其 分支的端点,所以 是路径;它也保证没有扇边颜色为 ,而颜色为 的只有 。因此互换恰好只可能破坏一个扇关系,即 与 之间的那一个。
分类依据是 是否在 上。若不在,终止于 的前缀根本不用 。若在, 缺失 ,所以它不可能是内部顶点,只能是另一个端点;互换把 变成颜色 ,并在 处空出 ,于是该关系得到修复。端点计数完成第二种情形: 只有 与 两个端点,所以同样缺失 的 不在路径上,仍然缺失 。简单性使每个扇顶点只对应一条中心边;若有平行边,上界本身便会失效,见下面的反例。
这样就完成了所有情形,而无需假设路径互换会保持任意一个扇。每次插入都保持正常性,并增加一条已染色边。从没有已染色边开始,重复有限次便可用固定的颜色集给整个图染色。最大度顶点要求其关联边颜色互不相同,这就证明了下界。无边的情形不用任何颜色,也无需插入。
直接实现的代价核算
证明
(直接实现的代价)
对每个顶点和每种颜色集中的颜色,存储该颜色的唯一关联边,或者一个表示不存在的标记。同时存储边的端点、颜色以及邻接表。该表有 个条目,支持常数时间的缺失颜色检测,以及交替路径的下一条边查询。
延长扇时,扫描至多 个中心邻点,检测该边是否已染色、其邻点是否在扇之外、其颜色是否在当前末端处缺失。至多 次延长,或者最后一次失败的扫描,总计 的工作量。求两种缺失颜色需要对颜色集做线性扫描。
交替路径至多包含 个顶点。保留它的边列表和成员标记,清除表中相关的旧条目,然后写入互换后的颜色及其条目。先清除可以避免把临时的表冲突误认为最终染色中的冲突。这需要线性的路径工作量。检查 的成员关系,选取前缀,并沿至多 条扇边移动空位,同时更新表条目。
因此一次插入的代价为 ,初始化的代价为 。共有 次插入。所存储的表、列表、路径和扇给出了所述的存储界。
例题详解
例题 10.3.5
(三角形已经需要额外的一种颜色)
三角形的最大度为二。它的三条边中任意两条共享一个顶点,所以三条边需要互不相同的颜色。它的边色数为三,恰好比最大度大一。
当两条边已染上不同的颜色后,第三条边的两个端点处所缺失的颜色,在较小的双色颜色集中可能并不相同。该定理全程使用三种颜色,从而使重新染色的保证成为可能。顶点染色与边染色是两个不同的问题,即使这个小图碰巧在两者中都需要三种颜色。
例题 10.3.6
(不经任何双色互换也可以旋转扇)
设中心为 ,取边 为空位, 为颜色一, 为颜色二。设颜色一在 处缺失,颜色二在 处缺失,颜色三在 与 处都缺失。列表 是一个扇。
把一移到 并清除 ;把二移到 并清除 ;用三给 染色。此时 处的关联颜色为一、二、三,并且接收方端点处具有所需的缺失颜色。扇顶点处的其他关联边可以存在,只要这些缺失颜色的条件成立即可。
例题 10.3.7
(奇数阶完全图给出一个无穷的紧族)
对于 个顶点的完全图,其中 ,最大度为 ,边数为 。一个颜色类是一个匹配,至多含 条边。因此覆盖所有边至少需要 种颜色。
已证明的上界恰好提供这么多种颜色,所以它的边色数恰为 。相比之下,四个顶点的完全图有一个三色边染色,由匹配 ;;以及 给出。在那里,最大度所给的三种颜色的颜色集已经足够。
概念视角算法
局部重新染色操作在改变路线的同时保持进度
已染色边的数目是全局进度度量。扇的旋转移动空位,交替路径交换可用颜色,二者都不改变这一数目。最后的共同缺失颜色使边数增加一。该不变量保证,即使最初选定的完整扇必须被缩短,这一进度也不会丢失。
常见错误
反例模式
平行边使简单图的上界失效
在三个顶点的三角形的每条边上放置两条平行边。最大度为四,但它的六条边中任意两条都共享一个端点。每个颜色类至多含一条边,所以需要六种颜色,超过了五。一般简单图的结论不适用于这个多重图。
常见错误
(只互换分支的一部分)
不要只互换双色连通分支的一个起始部分,除非已证明其端点条件;整个连通分支一起互换才能保持正常性。在路径 上,设 为颜色 、 为颜色 ;只互换 ,便使 有两条颜色为 的边。
常见错误
(互换后旋转整个扇)
不要在没有检查例外关系的情况下旋转互换之前的完整扇。当 不在 上时,边 现在的颜色是 ,而没有任何保证说 在 处缺失。旋转经过 时会把 移到 上,可能在 处重复;只有终止于 的前缀是安全的。
常见错误
(多一种颜色不是分类)
多用一种颜色的构造,本身并不能确定哪些图可以不用这多出的一种颜色。算法在 与 上同样使用 种颜色,但 只需三种, 则需要五种。
总结
顺序扇搬运一条未染色的中心边。极大性把最后一个顶点处的缺失颜色定位在某条扇边上,而一次交替路径互换要么留下一个可用前缀,要么留下修复后的整个扇。反复插入以明确的初等工作量证明了最大度加一的上界,而奇数阶完全图与平行边反例分别说明了该上界的紧性与适用范围。
练习
快速检查
(解释为什么仅含初始顶点的极大扇总能让该边直接用该顶点处的某种缺失颜色染色。)
若所选的缺失颜色在中心处出现,请考察其邻点。
解答 · 答案
选取在唯一的扇顶点处缺失的颜色 。若 在 处出现,则它唯一的关联边不可能是空位边。它的另一个端点会是一个新的扇邻点,且 在旧的最后一个顶点处缺失,这与极大性矛盾。因此 在 处也缺失,可以直接给空位边染色。该论证用到了简单图中通向那个原邻点的边是唯一的。
快速检查
(在路径互换的证明中,为什么在互换之前,前驱 与最后一个扇顶点不可能同时位于中心的交替路径上?)
两者都缺失 ,而中心已经占据了一个端点。
解答 · 答案
互换之前,中心缺失 而拥有 ,所以它是一条非平凡路径的一个端点。该路径上任何其他缺失 的顶点必然是它的另一个端点;内部顶点两种颜色都有。前驱 与最后一个顶点是不同的,所以它们不可能同时占据那一个端点。
快速检查
(求五圈与五个顶点的完全图的边色数。给出与定理上界相匹配的下界。)
一个颜色类是一个匹配;对于圈,还要考虑奇偶性。
解答 · 答案
五圈的度为二,不能用两种颜色做边染色:绕圈一周会迫使颜色交替,然后使起点处的第一条与最后一条关联边得到相同的颜色。由定理知三种颜色足够。五个顶点的完全图有十条边,每个匹配至多有两条边,所以它至少需要五种颜色。它的最大度为四,而定理给出五,达到了这个下界。