着色的计数与色多项式

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：May.11 2022

    本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

目录

有特定需要的内容直接跳转到相关章节查看即可。

正在加载目录...

色多项式的概念

    给定图 `G` 和颜色数 `k \in N`，`P_k(G)` 的值是对 `G` 正常 `k` 点着色的方式数，即满足 `f: V(G) \rightarrow [k]` 是正常点着色的所有映射的数目，其中 `[k]={1,2,...,k}`。给一个点着不同的颜色，则产生不同的染色方式。

    可以证明，`P_k(G)` 是 `k` 的多项式，因此称为图 `G` 的 色多项式 (Chromatic Polynomial)。由点色数 `\chi(G)` 和色多项式 `P_k(G)` 的定义可得如下性质，我们省去对它们的证明:

若 `k<\chi(G)`，则 `P_k(G)=0`，并且有 `\chi(G) = \min {k|P_k(G) \ge 1}`

若 `G` 为空图 (i.e. 没有边的图)，则 `P_k(G)=k^n`

`P_k(K_n) = k(k-1)...(k-n+1)`

色多项式的两种求法

递推计数法

方法定义

    首先我们对符号表示作出定义。

    如上图所示，我们使用 `G-e` 来代表从图 `G` 中删去边 `e`，使用 `G \cdot e` 来代表从图 `G` 中删去 `e` 后再重合 `e` 的端点后所得的图。基于这样的符号约定，我们给出如下关于色多项式的递推计数法:

设 `G` 为简单图，则对任意 `e \in E(G)`，有:

`P_k(G) = P_k(G - e) - P_k(G \cdot e)`

    证明: 设 `e=uv`，考虑 `G-e` 的着色方式，可以分为两种情况:

1. `u` 和 `v` 着不同的颜色，则加上边 `e` 后着色方式不变，则`G-e` 的这类着色方式数即等于 `G` 的着色方式数;
2. `u` 和 `v` 着相同的颜色，这种情况在 `G-e` 中被允许，在 `G` 中不被允许。`G-e` 的这类着色方式数等于 `G \cdot e` 的着色方式数

    综上可以得到定理。

    由上述定理我们可以得到如下推论:

设 `G` 是简单图，`e=uv` 是 `G` 的一条边，且 `d(u)=1`，则:

`P_k(G) = (k-1) \cdot P_k(G-u)`

    证明:

    因为 `G` 是简单图，`e=uv`，`d(u)=1`，所以 `G \cdot e = G - u`，也即「删去点 `u`」 和「合并边 `e` 两边的端点」这两件事情的本质是一样的。基于这层理解，又有 `P_k(G-e) = k \cdot P_k(G-u)`，也即只删去边 `e` 的图的着色方式数将是只删去点 `u` 的着色方式数的 `k` 倍。

    基于上述结论，可得 `P_k(G) = P_k(G-e) - P_k(G \cdot e)` `= k \cdot P_k(G-u) - P_k(G-u)` `=(k-1) \cdot P_k(G-u)`。

    在递推公式的使用方面，有如下的经验:

1. 当图 `G` 的边数较少时，使用减边递推法进行计算:
   `P_k(G) = P_k(G-e) - P_k(G \cdot e)`
2. 当图 `G` 的边数较多时，使用加边递推法进行计算:
   `P_k(G-e) = P_k(G) + P_k(G \cdot e)`

方法示例

    下面我们给出几个关于使用递推计数法的例子。

    如上图所示，给定图 `G`。为了将图 `G` 转化为完全图以利用 3 所给出的性质，并且使用 2 进行求解，我们可以将图 `G` 转化为:

    由此转化，基于 3 和 2 可得：

`P_k(G) = P_k(G+e) + P_k(G \cdot e)` `= P_k(K_3) + P_k(K_2)` `=k(k-1)(k-2) + k(k-1)` `=k^3 - 2k^2 + k`

    另一种求法是基于推论 5，可得

`P_k(G) = (k-1) \cdot P_k(K_2)` `= (k-1) \cdot k(k-1)` `=k^3 - 2k^2 + k`

理想子图计数法

    下面我们来看图的色多项式的另一种求法，我们首先给出一些基础概念:

基础概念

    设 `H` 是图 `G` 的生成子图，若 `H` 的每个分支均为完全图，称 `H` 是 `G` 的一个理想子图。我们使用 `N_r(G)` 表示图 `G` 具有 `r` 个分支的理想子图的个数。

    例如，对于上图来说，我们可以通过枚举得到它的 `N_4(G)` 的大小。如下所示:

    基于对理想子图的理解，我们给出一个定理:

设 `q_r(G)` 表示将简单图 `G` 的顶点集合 `V` 划分为 `r` 个不同色类的划分数，则有: `q_r(G) = N_r(\bar{G}) ...... (1 \le r \le |V|)`

    证明:

    一方面，设 `G` 的任一 `r` 色划分为 `{V_1, V_2, ..., V_r}`。由于 `V_i` 内部的点在 `G` 上一定不相邻，因此对于 `1 \le i \le r`，`\bar{G}[V_i]` 是 `\bar{G}` 的完全子图，如下图所示:

    又因为 `V_i \cap V_j = \emptyset (i \ne j)`，所以 `\bigcup_{i=1}^r \bar{G}[V_i]` 是 `\bar{G}` 的具有 `r` 个分支的理想子图。因此 `G` 的任一个 `r` 色划分必然唯一对应 `\bar{G}` 的一个具有 `r` 个分支的理想子图。

    所以 `q_r(G) = N_r(\bar{G}) ...... (1 \le r \le |V|)`

理想子图法

    基于 6，用 `k` 种颜色对简单图 `G` 进行正常点着色，那么便有:

`P_k(G) = \sum_{i=1}^nN_i(\bar{G})[k]_i`，其中 `[k]_i = k(k-1)(k-2)...(k-i+1)`

    可以理解为，首先在 `G` 中找出分为 `i` 种色类的划分方案 (i.e. 划分数为 `q_i(G)`)，等同于在 `\bar{G}` 中找出拥有 `i` 个分支的理想子图的划分方案 (i.e. 划分数为 `N_i(G)`)。然后对于分为 `i` 种色类的划分方案来说，由于一共有 `k` 种颜色，所以相当于可以找出 `[k]_i = A_k^{i} = k(k-1)(k-2)...(k-i+1)` 种填充方案，因此对于分为 `i` 种色类的划分方案来说，一共有 `q_i(G) \cdot [k]_i` 种划分方案。另外，由于 `i` 的范围可以取 `[1,n]`，因此就有 3 的式子。

    基于理想子图法的基本思路，我们再给出定义: 设 `G` 是简单图，令 `N_i(G)=r_i`，`[k]_i = x_i`，则称:

`h(G,x) = \sum_{i=1}^{n}r_ix^i`

    为图 `G` 的 伴随多项式。因此可得，求解 `P_k(G)` 就是要求出 `\bar{G}` 的伴随多项式。

    使用理想子图法求解 `P_k(G)` 的步骤总结如下：

1. 画出 `G` 的补图 `\bar{G}`;
2. (使用枚举的方法) 求出关于补图的 `r_i = N_i(\bar{G})`, `(1 \le i \le n)`;
3. 写出关于补图的伴随多项式 `h(G,x) = \sum_{i=1}^{n}r_ix^i`;
4. 将 `x^i = [k]_i` 代入伴随多项式中得到 `P_k(G)`

改进的理想子图法

    使用理想子图法求解图的色多项式，还可以通过如下定理进行改进 (p.s. 不加证明):

若 `G` 有 `t` 个分支 `H_1`, `H_2`, `...`, `H_t`，且 `H_i` 的伴随多项式为 `h(H_i, x)` (`i=1,2,...,t`)，则有:

`h(G, x) = \prod_{i=1}^{t}h(H_i, x)`

    该定理说明，在求解 `\bar{G}` 的伴随多项式时，可以分别求出它的每个分支的伴随多项式，然后将它们作乘积。

色多项式的性质

    本节给出关于色多项式的一些性质。

`n` 阶简单图 `G` 的色多项式 `P_k(G)` 是常数项为 0 的首 1 整系数 (i.e. 第一个系数 `a_0` 为 `1` 且系数均为整数) 多项式，且各项系数符号正负相间。

    证明:

    我们对 `G` 的边数进行数学归纳证明。

    当 `m=0` 时，`G` 是空图，根据 2，`P_k(G) = k^n`，命题结论成立。

    假设当 `m=k` 时，命题的结论成立。

    考虑 `m=k+1` 的简单图 `G` `(m \ge 1)`。取 `G` 的一条边 `e`，考虑 `G-e` 和 `G \cdot e`。

• 对于 `G-e` 来说，由归纳假设，可设其色多项式为:

  `P_k(G-e) = k^n - a_1k^{n-1} + a_2k^{n-2} - ... + (-1)^{n-1}a_{n-1}k`, `a_i \ge 0`

  同样对于 `G \cdot e` 来说，由归纳假设，可设其色多项式为 (p.s. 注意 `G \cdot e` 只有 `n-1` 个点):

  `P_k(G \cdot e) = k^{n-1} - b_1k^{n-2} + b_2k^{n-3} - ... + (-1)^{n-2}b_{n-2}k`, `b_i \ge 0`

    由色多项式递推公式 2 可得:

`P_k(G) = P_k(G-e) + P_k(G \cdot e)` `=k^n - (a_1+1)k^{n-1} + (a_2+b_1)k^{n-2} - ... + (-1)^{n-1}(a_{n-1}+b_{n-2})k`

若 `G=(n,m)` 是简单图，则在其色多项式 `P_k(G)` 中 `k^{n-1}` 的系数是 `-m`

    证明:

    我们对边数使用数学归纳法。当 `m=1` 时，`P_k(G)=P_k(G-e)-P_k(G \cdot e)``=k^n - k^{n-1}`，显然结论成立。

    假设命题对于少于 `m` 条边的 `n` 阶单图成立。考虑简单图 `G=(n,m)`，由递推公式可得 `P_k(G)=P_k(G-e)-P_k(G \cdot e)`。由假设可令:

`P_k(G-e)=k^n+a_1k^{n-1}+...+a_{n-1}k`，且 `a_1=-(m-1)=-m+1`。

    以及：

`P_k(G \cdot e) = k^{n-1} + b_1k^{n-2} + ... + b_{n-2}k` (注意 `b_1=-m+1` 并不一定成立)

    因此有:

`P_k(G) = k^{n} + (a_1-1)k^{n-1} + (a_2+b_1)k^{n-2} + ... + (a_{n-1}+b_{n-2})k`

    由于有 `a_1-1 = -m`，因此结论成立。

    基于 9，我们可以推断出，不存在以 `k^4-3k^3+3k^2` 为多项式的简单图，理由如下:

1. 一方面，如果它是某简单图的色多项式，则由多项式本身可以得到点色数为 `1`，因为上述多项式代入 `1` 后不为 `0`;
2. 另一方面，由 9 和多项式本身，如果多项式是某简单图的色多项式，则 `m(G)=3`，于是点色数至少为 `2`，这与 (1) 矛盾，因此不成立。