形式陈述
设 是有限简单无向图理路有限简单无向图Graph · Finite simple undirected graph · 图由有限顶点集与无序二元顶点子集组成的边集所确定的简单无向图。, 是正整数。一个正常顶点 -染色是函数理路函数Function · Map · Mapping由定义域、陪域和单值图共同组成,并把每个输入送到唯一输出的映射。
满足
若存在这样的函数,就称 是 -可染的。颜色的名称没有数学作用;对调调色板标签会得到另一个函数表示,却保持哪些顶点同色的划分不变。
令
染色合法,当且仅当每个非空颜色类 都是独立集理路团与独立集Clique · Independent set · 团 · 独立集顶点集内部的边关系分别达到两两全有与两两全无时形成的两类结构。。所以正常染色也可理解为把 划分理路集合划分Set partition把集合表示为两两不交非空块且其并为全体的块族。成至多 个独立集;允许某些颜色未使用,不会改变可染性。
给定一个具体染色函数是可行性证书,而色数理路色数Chromatic number一张图存在正常顶点染色所需的最少颜色数。 是所有可行调色板大小中的最小值。前者描述一项赋值,后者描述图的不变量;验证一个给定染色只需检查所有边,证明颜色已经最少还需要下界。
直觉
每条边提出一个局部“不许同色”约束,染色要让所有约束同时成立。一个顶点选色后,会占用其所有未染邻点的一种选择;影响沿边传播,顶点处理次序因而可能让同一套贪心规则产生截然不同的结果。
把颜色类看成独立集后,问题的整体图像更清楚:我们正在把一批彼此冲突的对象分装进若干槽,每个槽内部不能含边。颜色标签只是槽名,真正的结构是顶点划分。
例子与边界
路径与偶圈理路路与圈Path and cycle in a graph用相邻顶点序列刻画图中的行走、简单路径与首尾闭合的简单圈。可沿边交替使用两色。奇圈交替到最后一条边时,两端被迫同色,因此两色不够;给其中任一点第三种颜色即可完成染色。这一失败机制正是二分图奇圈判据的着色版本。
贪心染色理路贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。按某个顶点顺序处理,每次选当前最小可用颜色。顶点至多看见 种邻色,因此总能用至多 种颜色;这是对算法输出的上界,不说明输出达到最优。
次序依赖可以在 crown graph 中放大。令两侧为 与 ,保留所有跨侧边但删去 。该图是二分图理路二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。,两色足够;若按
运行 first-fit,非相邻的一对 会共同获得一种新颜色,最终使用 色。按 作归纳理路数学归纳法Mathematical induction · Weak induction由基例和从 n 到 n+1 的归纳步推出性质对全部自然数成立。:处理 时,先前的 分别禁掉颜色 ,故它取色 ;随后 的先前邻点 禁掉同样的颜色,而 与它不相邻,所以它也取色 。空前缀给出 的起步。输出随顶点次序改变,不能作为图的不变量。
自环要求 ,所以含自环图没有正常顶点染色。平行边重复同一个异色约束,不改变可行染色集合。非空无边图可用一种颜色;零阶图存在到空调色板的唯一空函数,色数是否记为零留给参数页约定。
列表染色为每个顶点分别限制可用颜色,边染色则给边赋色并让关联边异色。它们不能只用普通顶点染色的 -可行性判断;即使符号和贪心图像相似,输入约束已经改变。
Ramsey 定理理路Ramsey 定理Finite Ramsey theorem足够大的有限结构中必然出现给定大小的同质子结构。及其Ramsey 数理路Ramsey 数Ramsey number · 拉姆齐数 · R(s,t)保证任意红蓝完全图边染色出现指定大小单色团所需的最小宿主顶点数。研究完全图的任意边染色,允许关联边同色;这与正常顶点染色要求相邻顶点异色的可行性条件不同。
推论与应用
每个团中的顶点两两相邻,必须使用不同颜色,因此 给出任何着色所需颜色数的下界。贪心法给出 上界;Brooks 定理理路Brooks 定理Brooks' theorem除完全图和奇环外,连通图色数不超过其最大度数。进一步说明,除完全图和奇圈外,连通简单图可把上界降到 。
退化序理路k-core分解与退化序k-core decomposition · Core decomposition · Coreness · Degeneracy ordering · Smallest-last ordering · 核分解与退化序用真剩余度的双链桶剥离求全部核数,证明退化度与有界后邻居序等价,并交可独立复查的上下证书。进一步把贪心上界改写为δ+1:按删除序反向着色时,每点至多有δ个已经着色的邻居。δ是所有非空诱导子图最小度的最大值,可以远小于原图最大度;星形的δ为1,即使中心邻点很多也只需两色。
二分图理路二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。恰是可二染图,也就是没有奇圈的图。平面图理路平面图Planar graph可把顶点与边嵌入平面且除公共端点外没有交叉的抽象图。的四色定理则保证四种颜色总够,但具体嵌入不是顶点着色输入的一部分;地图区域先要按共享边界关系构成对偶式邻接图。
考试排程可把考试作为顶点,把有学生同时参加的两门考试连边;同色考试即可放在同一时段。若时段还有教室总容量、教师连续授课或三门课联合冲突等聚合限制,单纯的成对冲突图不再完整,需要额外约束。
一般图的最优着色计算困难,实践中常先构造一个可行染色作为上界,再用团、松弛或分支搜索产生下界。上、下界相遇时才得到最优性证书;只展示一份看起来紧凑的染色仍不能证明颜色最少。
图着色寄存器分配理路图着色寄存器分配Graph-coloring register allocation · Chaitin–Briggs register allocation从活跃性和调用破坏集合建立干涉图,执行简化与乐观选色,再把失败节点交给真实溢出重写。把程序活跃性转成带固定颜色的干涉图,再执行低度简化、潜在溢出与反向选色。这里的着色定义用于检查可行性;某个名字最终放到私有槽,仍需生成实际重载与保存代码,不能只给图换一种颜色便算完成机器分配。
合法解的定义也没有规定各顶点如何取得它。Cole–Vishkin 颜色缩减理路Cole–Vishkin 颜色缩减Cole–Vishkin color reduction · 确定性环三染色在给定一致方向的同步环上,用首次差异位反复压缩合法颜色,再以三轮消色得到三染色。研究一种分布式获取过程:给定一致方向的同步环从已有合法染色出发,各点只交换邻居颜色,反复缩小调色板,再以三轮消色得到三染色。这里的颜色类是独立集,恰好允许同色顶点同时改色而不彼此冲突;分析的主要成本是通信轮数,目标也不要求在偶环上进一步求得最少的两色。
结图上的 Fox 染色理路Fox 染色不变量Fox coloring · Fox n-coloring交叉同余 2b=a+c 在 Reidemeister 变换下给出染色双射;完整计算三叶结模 3 的九种染色,并说明线性代数算法。采用另一种约束:两个欠弧颜色之和等于过弧颜色的两倍模 ,而不是相邻顶点颜色不同。三叶结的模 3 约束只剩一条独立线性方程,得到九种染色;它的不变性通过 Reidemeister 变换的染色双射验证。
参考资料
- Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017, Chapter 5.
- Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001, Chapter 5.
- Tommy R. Jensen and Bjarne Toft, Graph Coloring Problems, Wiley, 1995, Chapters 1–2.