动机
正常染色回答的是:相邻顶点能否被赋予不同的颜色。若把所有这样的赋值都数出来,则提出了一个更丰富的问题:当有名字的调色板大小变化时,这个数目如何变化?令人惊讶的是,对每个非负整数的调色板大小,同一个多项式都给出答案。
这个多项式既可以通过禁止单色边来构造,也可以按照被删除的一条边的两个端点是否获得相同颜色来拆分。这两种方法给出同一个对象的不同证明。它们也揭示了一些有用的局限:对带名字的颜色计数不同于对无名的颜色类计数,而且色多项式相等并不迫使两个图同构。
定义
定义 10.1.1
(正常染色与有名字的调色板)
设 是有 个顶点、 条边的有限简单无向图。对整数 ,正常 -染色是一个函数 ,它给相邻顶点赋予不同的值。它不必用完所有可用的颜色。调色板中不同的名字给出不同的赋值。把正常染色的个数记为 。
没有顶点的图恰有一种染色,即空函数,即使调色板为空也是如此。非空图在调色板为空时没有染色。非空图的色数是容许正常染色的最小正整数 ;对零顶点图我们取零。
对 ,令 为生成图 的连通分支个数,其中孤立顶点也计入。对一条边 ,删除 是去掉这条边。收缩 是把它的两个端点等同,去掉被收缩的边,并把重复出现的边合并为单条边。因为原图是简单图,不会出现其他自环。所得的简单图表示两个端点颜色相等。
定理/命题
定理 10.1.2
(色多项式的存在性与最初几项系数)
对每个非负整数 ,染色个数都等于下面这个整系数多项式的值:
它是首一的,次数为 。当 时,其常数项为零, 的系数为 。当 时, 的系数为 ,其中 是三角形的个数。零顶点图的多项式为一。
定理 10.1.3
(删除–收缩与乘积法则)
对每条边 ,
不相交并满足 。若 是两个图的并,这两个图的顶点交恰为一个顶点,且没有其他连接边,则
这是一个多项式恒等式,因此在零处也有意义,而无需在数值上除以零。
定理 10.1.4
(树、森林与圈)
个顶点的树的多项式为 。有 个顶点、 个连通分支的森林的多项式为 。当 时,圈 满足
证明思路或证明
证明
(容斥原理与最初几项系数)
从全部 种染色出发,让每个禁止事件要求某一条边的两个端点颜色相同。要求由 所标记的全部事件同时发生,就迫使 的每个连通分支都是单色的。各分支独立地选择颜色,共得到 种赋值。由容斥原理即得该求和公式。对零顶点图,对应的项是常数多项式 ,在零处也是如此。
只有空边子集有 个连通分支,这证明了多项式是首一的。非空图的每个生成子图至少有一个连通分支,所以没有常数项。要得到 个连通分支,简单图必须恰好选取一条边,由此得系数 。要得到 个连通分支,每个两条边的子集都贡献正项。唯一额外的可能是构成三角形的三条边,它贡献负项。事实上,连通分支总共减少二,允许的情形是两个互不相连的二顶点分支,或一个三顶点分支;简单的三顶点图至多有三条边。这就证明了三角形的系数公式。
证明
(按端点颜色作删除–收缩)
对于删除–收缩,把 的正常染色分为两组:端点颜色不同的和端点颜色相同的。第一组恰好是 的正常染色。把颜色相同的端点等同起来,给出第二组到 的正常染色的双射。等同所产生的多重相邻约束是完全相同的,这就是合并平行边无妨的原因。该等式对每个整数调色板大小都成立,因此是多项式恒等式。
证明透视
删除–收缩中唯一的分类用到了什么
证明从 而不是从 出发:删除 去掉了一个约束,所以 的染色包含 的全部染色。唯一的分类是看 与 是否同色。异色情形恰好恢复被删除的约束,其余不变,所以它计数的是 。收缩在同色情形中出场。把 合并为一个顶点 是可逆的,因为两个端点颜色相同;而 必须与 或 的每个邻点异色。若 与 有公共邻点 ,则 与 之间得到的两个约束完全相同,这就是合并平行边不会损失任何信息的原因。 的简单性在这里用到:合并唯一可能产生的自环来自 本身,而它已被移除。论证在每个整数 处证明了恒等式;由于在无穷多点上一致的两个多项式相等,它成为多项式恒等式。
证明
(不相交并与单顶点并的乘积)
不相交的图从同一个调色板独立地选择染色,这证明了乘积法则。对于仅共享一个顶点的并,设 为正整数,由颜色名字的对称性,每一块在共享顶点被指定为某个给定颜色时恰有 种染色。该颜色有 种选法,再把两块组合起来,就证明了 。对无穷多个正整数相等,就证明了多项式恒等式。每一块都有一个顶点,所以它的多项式含有因子 ;形式上除以一个因子得到的商是多项式,而不是在零处无定义的求值。
证明
(树、森林与圈)
给树选定根。根有 种选择;在其父顶点染色之后,其他每个顶点有 种选择,且没有额外的边约束。这证明了树的公式,对各连通分支取乘积即得森林公式,空森林也包括在内。三角形的多项式为 ,与 时的圈公式一致。对 ,删除圈的一条边得到 个顶点上的路径,收缩这条边得到 。把归纳假设中的圈表达式代入删除–收缩,即得所示公式。三角形是单独的归纳基础,因为收缩其一条边得到一条简单的边,而不是简单的二重圈。
例题详解
例题 10.1.5
(用删除与收缩计算四圈)
删除 的一条边得到四个顶点上的路径,收缩这条边得到三角形。因此
用两种颜色时它的值是二,用三种颜色时是十八。系数记录了四条边以及 个三角形,与该图相符。
例题 10.1.6
(带一片叶子的三角形在两块之间共享一个顶点)
在三角形的一个顶点上接一片叶子。把三角形的多项式与一条边的多项式结合,并形式上除以共享顶点的因子,得 。用三种颜色时有十二种染色。等价地,三角形有六种染色,叶子可以从与其邻点不同的两种颜色中任选一种。两种计算都是在数有名字的调色板赋值。
例题 10.1.7
(该多项式不是完全的图不变量)
四个顶点上的路径与有三片叶子的星图不同构:它们的度序列分别为 和 。两者都是树,因此多项式都是 。它们的染色数对每个调色板大小都相同,而邻接结构却不同。计数多项式可以保留有用的统计量,却无法编码整个图。
为什么必须保留生成顶点集
在容斥公式中,删除边并不删除它们的端点。孤立顶点仍然独立地选择颜色,并贡献连通分支。特别地,空边子集的连通分支数恰好等于原图的顶点数。若只数含有边的连通分支,就会抹去这些自由的颜色选择,甚至破坏多项式的首项。
这些禁止事件并不互斥。单色三角形同时满足三个边相等事件,而其中只有两个相等关系是独立的约束。容斥原理保留了三重交,并修正了这一重叠。这解释了第三项系数中的三角形修正:公式是按约束的连通效应来计数的,而不仅仅是按所选边的条数。
图是简单图,对系数的解释很重要。平行边施加的是同一个颜色不等约束,所以把它们当作不同的图边来数,不会得到系数为负的总重数。自环则会禁止所有染色。所述范围排除了这两种现象,而收缩明确地回到简单图的情形。
有名字的颜色与无名字的独立类
正常染色把顶点集划分为它的各个非空颜色类,每个颜色类都是独立集。若一个划分恰有 块,给这些块分配互不相同的调色板名字,就得到 种染色。因此另一种展开是
其中 是把顶点集划分成 个非空独立块的划分个数。这由一个可逆的纤维分解得出,而不是把整个染色数除以某个固定的阶乘。
对于无边图,每个块都是独立的,所以这些系数就是第二类 Stirling 数。该恒等式成为 按下降阶乘的展开。对于有边的图,被禁止的同块关系改变了块划分的计数。这种关系把图的染色与带标号集合的枚举联系起来,同时保留了各对象不同的定义。
反例模式
一般情况下,除以调色板的阶乘是无效的
两个孤立顶点用三色调色板有九种染色。除以 得到一又二分之一,它不可能是无名划分的个数。实际上有两种颜色类划分:一个块包含两个顶点,或两个单点块。它们分别有三种和六种带名字的实现。未使用的颜色使纤维的大小依赖于非空类的个数。
计数、判定与计算代价
对于非空图,使多项式取正值的最小正整数就是它的色数。这个等式由整数处的计数解释得出。在任意实数或负数处的取值只是多项式的求值,并不是对非整数个或负数个颜色的调色板的计数。
删除–收缩会终止,因为每个分支都通过删除或收缩去掉了一条原来的边,而合并平行边可能去掉更多的边。直接的递归计算仍可能有指数多个分支。关于调色板变量的多项式存在,并不意味着用这种方法能在图的大小的多项式时间内算出它的系数。
特殊结构可以简化计算。森林有直接的乘积公式;固定割点的颜色之后,割点把图分成相互独立的几块。这些简化必须由实际的分解假设来证明。把任意子图的多项式相乘,会重复计数,或忽略它们交集上的约束。
概念视角组合
同一个图有几种不同的计数描述
容斥原理数的是由所选相等关系迫使成为单色的连通分支。删除–收缩区分端点颜色不同与相同两种情形。下降阶乘展开在给类命名之前先数独立的顶点划分。它们描述的是同样的染色,但组织的中间对象不同,从而使不同的恒等式变得显而易见。
常见错误
常见错误
(调色板大小不是所用颜色的数目)
正常染色不必用完调色板中的所有名字。对单独一条边,,而这六种染色没有一种用到全部三种颜色。若把 读作恰好使用 种颜色的染色数,这里便会得到零。用完全部 种调色板颜色的染色数是 ,其中 来自上文的下降阶乘展开;它不是 。
常见错误
(删除–收缩并不自动就是高效算法)
一连串较小图的计算并不自动就是高效算法;递归的规模和算术运算必须分别分析。对有 条边的森林,收缩从不产生平行边,所以两个分支都保留 条边并仍是森林;一直递归到没有边为止,恰好产生 个无边的叶子,尽管乘积公式能立即给出答案。
收缩是把端点的颜色合并,而删除一个顶点则会彻底去掉一个颜色选择。
最初几项系数揭示了顶点数、边数和三角形数,但树的例子证明它们并不决定同构。另外,不要在虚构的简单二重圈上应用圈的收缩递推;三圈这一基础情形必须直接验证。
总结
有名字的调色板下的正常染色,通过容斥原理定义出一个整系数多项式。删除–收缩与图的分解提供了互补的计算方法。树与圈的公式、系数统计量以及独立类展开,既显示了该多项式所含的结构信息,也显示了它的局限。
练习
快速检查
(求有七个顶点、三个连通分支的森林的多项式。它有多少种正常二染色和三染色?)
若有孤立的分支,也要计入。
解答 · 答案
多项式为 。用两种颜色时值为八;用三种颜色时为 。孤立顶点是只有一个根的选择且没有额外因子的连通分支,所以公式已经把它们包括在内。
快速检查
(一个简单的五顶点图的最前几项是 。求它的边数和三角形数。)
题目给出了一种可能的系数模式;这两个统计量的公式不同。
解答 · 答案
的系数是边数的相反数,所以 。 的系数等于 ,因此 。这个模式是可以实现的,例如从四团中去掉一条边,再接上一片新叶子:这个图有六条边和两个三角形。由此并不能断言存在唯一的图。
快速检查
(计算四个顶点的完全图的多项式,并验证关于边数与三角形数的系数解释。)
依次为互相邻接的顶点选择颜色。
解答 · 答案
多项式为 。它记录了六条边,其第三项系数给出 个三角形,恰好是四个三顶点子集。当调色板大小小于四时乘积为零,符合要求;在四时有 种赋值。