图的染色多项式
字数 2425 2025-11-03 18:01:13

图的染色多项式

图的染色多项式是代数图论中的一个重要计数工具，它通过一个多项式来记录一个图用给定数量的颜色进行正常顶点着色的方式数。

第一步：回顾图的正常着色概念
一个图 \(G\) 的（正常）\(k\)-着色是指从图的顶点集 \(V(G)\) 到颜色集 \(\{1, 2, ..., k\}\) 的一个映射 \(f\)，要求对于图 \(G\) 中的任意一条边 \(uv\)，都有 \(f(u) \neq f(v)\)，即相邻的顶点必须被染成不同的颜色。使得图 \(G\) 存在一个 \(k\)-着色的最小颜色数 \(k\) 称为图 \(G\) 的色数，记作 \(\chi(G)\)。

第二步：引入染色多项式作为计数函数
对于一个图 \(G\) 和一个给定的正整数 \(k\)，我们用 \(P(G, k)\) 表示图 \(G\) 的所有不同的 \(k\)-着色的数量。这里的“不同”是指将颜色视为有标签的（例如，颜色1、2、3是不同的），因此交换颜色的着色被视为不同的着色。
一个关键的发现是，对于任意一个固定的图 \(G\)，函数 \(P(G, k)\) 是关于变量 \(k\) 的一个多项式函数。这个多项式就被称为图 \(G\) 的染色多项式。

第三步：通过简单例子理解染色多项式

  1. 完全图 \(K_n\)：要使用 \(k\) 种颜色对 \(K_n\)（所有顶点都两两相连的图）进行着色，每个顶点颜色都必须不同。第一个顶点有 \(k\) 种选择，第二个有 \(k-1\) 种，以此类推。因此，\(P(K_n, k) = k(k-1)(k-2)...(k-n+1)\)。这是一个 \(n\) 次多项式。
  2. 空图 \(\overline{K_n}\)：一个具有 \(n\) 个顶点且没有任何边的图。由于没有边，对着色没有任何限制，每个顶点都可以独立地选择 \(k\) 种颜色中的任何一种。因此，\(P(\overline{K_n}, k) = k^n\)。
  3. 树 \(T_n\)：一个有 \(n\) 个顶点的树。我们可以从根节点开始着色，根节点有 \(k\) 种选择。对于根节点的每个子节点，由于不能与父节点同色，所以有 \(k-1\) 种选择。以此类推，每个后续顶点都有 \(k-1\) 种选择。因此，\(P(T_n, k) = k(k-1)^{n-1}\)。

第四步：染色多项式的递推关系——删除-收缩公式
染色多项式的一个核心性质是它可以由一个递推公式计算。这个公式涉及两种图操作：

  • 删除一条边 \(e\)：从图 \(G\) 中移除边 \(e\)，但保留其两个端点，得到图 \(G-e\)。
  • 收缩一条边 \(e=uv\)：从图 \(G\) 中移除边 \(e\)，并将顶点 \(u\) 和 \(v\) 合并成一个新的顶点，新顶点与原来与 \(u\) 或 \(v\) 相连的所有顶点相连，得到图 \(G/e\)。
    染色多项式的删除-收缩公式为：

\[P(G, k) = P(G-e, k) - P(G/e, k) \]

这个公式的意义在于：\(P(G-e, k)\) 计算的是在 \(G-e\) 上的着色数，这包括了那些在 \(G\) 中非法的着色（即 \(u\) 和 \(v\) 颜色相同的情况）。而 \(P(G/e, k)\) 恰好计算了在 \(G\) 中 \(u\) 和 \(v\) 颜色相同的着色数。因此，从前者减去后者，就得到了 \(G\) 中 \(u\) 和 \(v\) 颜色不同的合法着色数，即 \(P(G, k)\)。通过反复应用此公式，最终可以将任何图的染色多项式化为一些完全图或空图的染色多项式之和。

第五步：染色多项式的基本性质

  1. 首项：\(P(G, k)\) 是一个 \(n\) 次多项式，其中 \(n = |V(G)|\) 是顶点数。其首项是 \(k^n\)。
  2. 系数交替符号：如果将多项式写为 \(P(G, k) = \sum_{i=1}^{n} a_i k^i\)，则系数 \(a_i\) 的符号是正负交替的，即 \(a_n > 0, a_{n-1} < 0, a_{n-2} > 0, ...\)。
  3. 常数项为零：\(P(G, 0) = 0\)。
  4. 色数的信息：图 \(G\) 的色数 \(\chi(G)\) 是使得 \(P(G, k) > 0\) 的最小正整数 \(k\)。换句话说，染色多项式的正整数根（即 \(P(G, k)=0\) 的正整数解）是 \(0, 1, 2, ..., \chi(G)-1\)。例如，一个色数为3的图，其染色多项式在 \(k=1\) 和 \(k=2\) 时值为0。

第六步：染色多项式与图的结构
染色多项式编码了图的大量组合信息。例如：

  • 连通分支：如果图 \(G\) 由两个不相交的连通分支 \(G_1\) 和 \(G_2\) 组成，则 \(P(G, k) = P(G_1, k) \cdot P(G_2, k)\)。
  • 圈：一个长度为 \(n\) 的圈 \(C_n\) 的染色多项式为 \(P(C_n, k) = (k-1)^n + (-1)^n (k-1)\)。
  • 非平凡性：两个不同构的图可能具有相同的染色多项式（称为色等价），但染色多项式仍然是比色数更强的图不变量，它能区分更多不同构的图。

染色多项式是连接组合数学、代数和统计物理（例如Potts模型）的一个重要桥梁。

图的染色多项式 图的染色多项式是代数图论中的一个重要计数工具，它通过一个多项式来记录一个图用给定数量的颜色进行正常顶点着色的方式数。 第一步：回顾图的正常着色概念 一个图 \( G \) 的（正常）\( k \)-着色是指从图的顶点集 \( V(G) \) 到颜色集 \( \{1, 2, ..., k\} \) 的一个映射 \( f \)，要求对于图 \( G \) 中的任意一条边 \( uv \)，都有 \( f(u) \neq f(v) \)，即相邻的顶点必须被染成不同的颜色。使得图 \( G \) 存在一个 \( k \)-着色的最小颜色数 \( k \) 称为图 \( G \) 的色数，记作 \( \chi(G) \)。 第二步：引入染色多项式作为计数函数 对于一个图 \( G \) 和一个给定的正整数 \( k \)，我们用 \( P(G, k) \) 表示图 \( G \) 的所有不同的 \( k \)-着色的数量。这里的“不同”是指将颜色视为有标签的（例如，颜色1、2、3是不同的），因此交换颜色的着色被视为不同的着色。 一个关键的发现是，对于任意一个固定的图 \( G \)，函数 \( P(G, k) \) 是关于变量 \( k \) 的一个多项式函数。这个多项式就被称为图 \( G \) 的染色多项式。 第三步：通过简单例子理解染色多项式 完全图 \( K_ n \) ：要使用 \( k \) 种颜色对 \( K_ n \)（所有顶点都两两相连的图）进行着色，每个顶点颜色都必须不同。第一个顶点有 \( k \) 种选择，第二个有 \( k-1 \) 种，以此类推。因此，\( P(K_ n, k) = k(k-1)(k-2)...(k-n+1) \)。这是一个 \( n \) 次多项式。 空图 \( \overline{K_ n} \) ：一个具有 \( n \) 个顶点且没有任何边的图。由于没有边，对着色没有任何限制，每个顶点都可以独立地选择 \( k \) 种颜色中的任何一种。因此，\( P(\overline{K_ n}, k) = k^n \)。 树 \( T_ n \) ：一个有 \( n \) 个顶点的树。我们可以从根节点开始着色，根节点有 \( k \) 种选择。对于根节点的每个子节点，由于不能与父节点同色，所以有 \( k-1 \) 种选择。以此类推，每个后续顶点都有 \( k-1 \) 种选择。因此，\( P(T_ n, k) = k(k-1)^{n-1} \)。 第四步：染色多项式的递推关系——删除-收缩公式 染色多项式的一个核心性质是它可以由一个递推公式计算。这个公式涉及两种图操作： 删除一条边 \( e \) ：从图 \( G \) 中移除边 \( e \)，但保留其两个端点，得到图 \( G-e \)。 收缩一条边 \( e=uv \) ：从图 \( G \) 中移除边 \( e \)，并将顶点 \( u \) 和 \( v \) 合并成一个新的顶点，新顶点与原来与 \( u \) 或 \( v \) 相连的所有顶点相连，得到图 \( G/e \)。 染色多项式的删除-收缩公式为： \[ P(G, k) = P(G-e, k) - P(G/e, k) \] 这个公式的意义在于：\( P(G-e, k) \) 计算的是在 \( G-e \) 上的着色数，这包括了那些在 \( G \) 中非法的着色（即 \( u \) 和 \( v \) 颜色相同的情况）。而 \( P(G/e, k) \) 恰好计算了在 \( G \) 中 \( u \) 和 \( v \) 颜色相同的着色数。因此，从前者减去后者，就得到了 \( G \) 中 \( u \) 和 \( v \) 颜色不同的合法着色数，即 \( P(G, k) \)。通过反复应用此公式，最终可以将任何图的染色多项式化为一些完全图或空图的染色多项式之和。 第五步：染色多项式的基本性质 首项 ：\( P(G, k) \) 是一个 \( n \) 次多项式，其中 \( n = |V(G)| \) 是顶点数。其首项是 \( k^n \)。 系数交替符号 ：如果将多项式写为 \( P(G, k) = \sum_ {i=1}^{n} a_ i k^i \)，则系数 \( a_ i \) 的符号是正负交替的，即 \( a_ n > 0, a_ {n-1} < 0, a_ {n-2} > 0, ... \)。 常数项为零 ：\( P(G, 0) = 0 \)。 色数的信息 ：图 \( G \) 的色数 \( \chi(G) \) 是使得 \( P(G, k) > 0 \) 的最小正整数 \( k \)。换句话说，染色多项式的正整数根（即 \( P(G, k)=0 \) 的正整数解）是 \( 0, 1, 2, ..., \chi(G)-1 \)。例如，一个色数为3的图，其染色多项式在 \( k=1 \) 和 \( k=2 \) 时值为0。 第六步：染色多项式与图的结构 染色多项式编码了图的大量组合信息。例如： 连通分支 ：如果图 \( G \) 由两个不相交的连通分支 \( G_ 1 \) 和 \( G_ 2 \) 组成，则 \( P(G, k) = P(G_ 1, k) \cdot P(G_ 2, k) \)。 圈 ：一个长度为 \( n \) 的圈 \( C_ n \) 的染色多项式为 \( P(C_ n, k) = (k-1)^n + (-1)^n (k-1) \)。 非平凡性 ：两个不同构的图可能具有相同的染色多项式（称为色等价），但染色多项式仍然是比色数更强的图不变量，它能区分更多不同构的图。 染色多项式是连接组合数学、代数和统计物理（例如Potts模型）的一个重要桥梁。