图的流多项式与图的多项式不变量
字数 2476 2025-12-10 19:47:05

图的流多项式与图的多项式不变量

我们来探讨图论中的一个深刻主题：图的流多项式。 这是一种强大的多项式不变量，它统一并扩展了图在多种流配置下的计数问题。理解它需要循序渐进的构建。

第一步：从图的“流”的基本概念开始

首先，忘掉网络流。在图论中，“流” 通常指**“无源汇的流”** 或**“环流”。其核心思想是为有向图的每条边分配一个值（通常来自一个阿贝尔群，如整数模某个数），使得在每个顶点处，流入的总值等于流出的总值**（基尔霍夫电流定律）。这称为**“守恒条件”**。

  • 正式定义：给定一个有向图 \(G\) 和一个阿贝尔群 \(A\)（例如 \(A = \mathbb{Z}_k\)，整数模k）。一个 A-流 是一个函数 \(f: E(G) \to A\)，满足对每个顶点 \(v\)：

\[ \sum_{e \in E^+(v)} f(e) - \sum_{e \in E^-(v)} f(e) = 0 \]

其中 \(E^+(v)\) 是指向 \(v\) 的边集，\(E^-(v)\) 是从 \(v\) 指出的边集。

  • 平凡流：给所有边赋值为0的流总是满足条件。
  • 处处非零流：如果对所有边 \(e\) 都有 \(f(e) \neq 0\)，则称之为处处非零流 或无零流。

第二步：一个关键问题与塔特定理

一个自然的问题是：对于一个给定的图 \(G\) 和整数 \(k > 1\)，是否存在一个处处非零的 \(\mathbb{Z}_k\)-流？
塔特在20世纪中叶给出了一个里程碑式的答案，它将流的存在性与图的着色 联系起来：

  • 塔特定理（流版本）：一个无向图 \(G\) 存在一个处处非零的 \(k\)-流（即 \(\mathbb{Z}_k\)-流），当且仅当 它的每条边都包含在某个偶环中（即，\(G\) 是2-边连通的）并且 \(k \ge 2\)。特别地，存在性与有向图的方向选取无关。
  • 与着色的对偶性：对于平面图 \(G\)，存在一个处处非零的 \(k\)-流，等价于其对偶图 \(G^*\) 是 \(k\)-可着色的。这揭示了流与着色之间深刻的对偶关系。

第三步：从计数到多项式——流多项式的引入

塔特定理回答了“是否存在”的问题。下一步是计数：对于一个给定的 \(k\)，图 \(G\) 上有多少个不同的处处非零的 \(k\)-流？更一般地，有多少个 \(k\)-流（允许有零值）？这个计数结果被证明是 \(k\) 的一个多项式函数，这引导我们定义流多项式。

  • 定义：设 \(G\) 是一个无向图。流多项式 \(F(G; k)\) 定义为：当 \(k\) 为正整数时，\(F(G; k)\) 等于图 \(G\) 上处处非零的 \(k\)-流的数目。关键定理（由W.T. Tutte等人证明）指出，这个函数可以延拓为变量 \(k\) 的一个多项式。
  • 基本性质：
    1. 不依赖于定向：由于塔特定理，计算时可以先任意给定一个定向，结果多项式相同。
  1. 不连通图：若不连通，则流多项式是各连通分支流多项式的乘积：\(F(G; k) = \prod_i F(G_i; k)\)。
  2. 桥（割边）：如果图 \(G\) 含有桥（即删除后使图不连通的边），则不存在处处非零流，故 \(F(G; k) = 0\)。
  3. 环（自环）：如果图 \(G\) 含有环，由于环上可以任意分配非零值而不影响守恒条件，所以每条环对计数的贡献因子是 \((k-1)\)。因此，我们可以先删除所有环，最后乘以 \((k-1)^{(\text{环数})}\)。

第四步：计算与递推关系——类似色多项式的删缩公式

流多项式的计算可以通过对图的边进行递归操作来完成，这与色多项式 的递推关系极为相似，体现了它们之间的对偶性。

  • 删边-缩边递推：对于图 \(G\) 中一条既不是环也不是桥的边 \(e\)，有：

\[ F(G; k) = F(G\setminus e; k) - F(G/e; k) \]

其中 \(G\setminus e\) 是删除边 \(e\) 后的图，\(G/e\) 是收缩边 \(e\) 后的图（收缩产生的自环要保留）。

  • 与色多项式的关系：对于一个平面图 \(G\) 及其对偶图 \(G^*\)，存在漂亮的对偶公式：

\[ F(G; k) = k^{-1} P(G^*; k) \]

其中 \(P(G^*; k)\) 是 \(G^*\) 的色多项式（表示用 \(k\) 种颜色给 \(G^*\) 正常着色的方式数）。这直接将对一个图的流计数，转化为对其对偶图的着色计数。

第五步：流多项式作为图多项式不变量

流多项式 \(F(G; k)\) 是图的多项式不变量 家族的重要成员。

  • 不变性：同构的图具有相同的流多项式。因此，它可以帮助区分不同构的图。
  • 根的诠释：流多项式的根（即使得 \(F(G; k)=0\) 的 \(k\) 值）蕴含着图的结构信息。例如，根据塔特定理，所有整数 \(1 < k < \lambda\) 都可能是根，其中 \(\lambda\) 是保证处处非零流存在的最小整数（称为“流数”）。
  • 与塔特多项式的联系：流多项式是更一般的塔特多项式 \(T(G; x, y)\) 的特殊化。具体地，有：

\[ F(G; k) = (-1)^{|E|-|V|+c} T(G; 0, 1-k) \]

其中 \(c\) 是连通分支数。这表明流多项式编码了图的诸多组合不变量（如生成树数目、流数目、着色数目等）。

总结：图的流多项式 \(F(G; k)\) 从一个简单的组合计数问题（计算处处非零环流的数目）出发，通过深刻的数学（塔特定理、多项式延拓、删缩递推）发展成为一个强有力的图多项式不变量。它不仅在纯图论中联系着色、流和拓扑结构，也与统计物理中的波特模型、结理论中的琼斯多项式有着内在的关联，是连接组合数学与其它数学分支的优雅桥梁。

图的流多项式与图的多项式不变量 我们来探讨图论中的一个深刻主题： 图的流多项式 。 这是一种强大的多项式不变量，它统一并扩展了图在多种流配置下的计数问题。理解它需要循序渐进的构建。 第一步：从图的“流”的基本概念开始 首先，忘掉网络流。在图论中， “流” 通常指** “无源汇的流”** 或** “环流” 。其核心思想是为有向图的每条边分配一个值（通常来自一个阿贝尔群，如整数模某个数），使得在每个顶点处， 流入的总值等于流出的总值** （基尔霍夫电流定律）。这称为** “守恒条件”** 。 正式定义 ：给定一个有向图 \(G\) 和一个阿贝尔群 \(A\)（例如 \(A = \mathbb{Z} k\)，整数模k）。一个 A-流 是一个函数 \(f: E(G) \to A\)，满足对每个顶点 \(v\)： \[ \sum {e \in E^+(v)} f(e) - \sum_ {e \in E^-(v)} f(e) = 0 \] 其中 \(E^+(v)\) 是指向 \(v\) 的边集，\(E^-(v)\) 是从 \(v\) 指出的边集。 平凡流 ：给所有边赋值为0的流总是满足条件。 处处非零流 ：如果对所有边 \(e\) 都有 \(f(e) \neq 0\)，则称之为 处处非零流 或 无零流 。 第二步：一个关键问题与塔特定理 一个自然的问题是：对于一个给定的图 \(G\) 和整数 \(k > 1\)，是否存在一个处处非零的 \(\mathbb{Z}_ k\)-流？ 塔特在20世纪中叶给出了一个里程碑式的答案，它将流的存在性与图的 着色 联系起来： 塔特定理（流版本） ：一个无向图 \(G\) 存在一个处处非零的 \(k\)-流（即 \(\mathbb{Z}_ k\)-流）， 当且仅当 它的每条边都包含在某个偶环中（即，\(G\) 是 2-边连通的 ）并且 \(k \ge 2\)。特别地，存在性与有向图的方向选取无关。 与着色的对偶性 ：对于平面图 \(G\)，存在一个处处非零的 \(k\)-流，等价于其对偶图 \(G^* \) 是 \(k\)-可着色的。这揭示了流与着色之间深刻的 对偶关系 。 第三步：从计数到多项式——流多项式的引入 塔特定理回答了“是否存在”的问题。下一步是计数：对于一个给定的 \(k\)，图 \(G\) 上有多少个不同的处处非零的 \(k\)-流？更一般地，有多少个 \(k\)-流（允许有零值）？这个计数结果被证明是 \(k\) 的一个多项式函数，这引导我们定义 流多项式 。 定义 ：设 \(G\) 是一个无向图。 流多项式 \(F(G; k)\) 定义为：当 \(k\) 为正整数时，\(F(G; k)\) 等于图 \(G\) 上处处非零的 \(k\)-流的数目。关键定理（由W.T. Tutte等人证明）指出，这个函数可以延拓为变量 \(k\) 的一个 多项式 。 基本性质 ： 不依赖于定向 ：由于塔特定理，计算时可以先任意给定一个定向，结果多项式相同。 不连通图 ：若不连通，则流多项式是各连通分支流多项式的乘积：\(F(G; k) = \prod_ i F(G_ i; k)\)。 桥（割边） ：如果图 \(G\) 含有桥（即删除后使图不连通的边），则不存在处处非零流，故 \(F(G; k) = 0\)。 环（自环） ：如果图 \(G\) 含有环，由于环上可以任意分配非零值而不影响守恒条件，所以每条环对计数的贡献因子是 \((k-1)\)。因此，我们可以先删除所有环，最后乘以 \((k-1)^{(\text{环数})}\)。 第四步：计算与递推关系——类似色多项式的删缩公式 流多项式的计算可以通过对图的边进行递归操作来完成，这与 色多项式 的递推关系极为相似，体现了它们之间的对偶性。 删边-缩边递推 ：对于图 \(G\) 中一条既不是环也不是桥的边 \(e\)，有： \[ F(G; k) = F(G\setminus e; k) - F(G/e; k) \] 其中 \(G\setminus e\) 是删除边 \(e\) 后的图，\(G/e\) 是收缩边 \(e\) 后的图（收缩产生的自环要保留）。 与色多项式的关系 ：对于一个平面图 \(G\) 及其对偶图 \(G^ \)，存在漂亮的对偶公式： \[ F(G; k) = k^{-1} P(G^ ; k) \] 其中 \(P(G^ ; k)\) 是 \(G^ \) 的色多项式（表示用 \(k\) 种颜色给 \(G^* \) 正常着色的方式数）。这直接将对一个图的流计数，转化为对其对偶图的着色计数。 第五步：流多项式作为图多项式不变量 流多项式 \(F(G; k)\) 是 图的多项式不变量 家族的重要成员。 不变性 ：同构的图具有相同的流多项式。因此，它可以帮助区分不同构的图。 根的诠释 ：流多项式的根（即使得 \(F(G; k)=0\) 的 \(k\) 值）蕴含着图的结构信息。例如，根据塔特定理，所有整数 \(1 < k < \lambda\) 都可能是根，其中 \(\lambda\) 是保证处处非零流存在的最小整数（称为“流数”）。 与塔特多项式的联系 ：流多项式是更一般的 塔特多项式 \(T(G; x, y)\) 的特殊化。具体地，有： \[ F(G; k) = (-1)^{|E|-|V|+c} T(G; 0, 1-k) \] 其中 \(c\) 是连通分支数。这表明流多项式编码了图的诸多组合不变量（如生成树数目、流数目、着色数目等）。 总结 ： 图的流多项式 \(F(G; k)\) 从一个简单的组合计数问题（计算处处非零环流的数目）出发，通过深刻的数学（塔特定理、多项式延拓、删缩递推）发展成为一个强有力的图多项式不变量。它不仅在纯图论中联系着色、流和拓扑结构，也与统计物理中的波特模型、结理论中的琼斯多项式有着内在的关联，是连接组合数学与其它数学分支的优雅桥梁。