图的团多项式与独立集多项式
我们先从最基础的概念开始。您已经了解了“图的独立集问题”和“图的团问题”。一个独立集是图中一组互不相邻的顶点，而一个团则是图中一组两两相邻的顶点。这两个概念是互补的：一个图G的独立集，正是其补图G̅中的团。
今天，我们深入探讨与这两个结构密切相关的组合不变量——团多项式和独立集多项式。它们不仅是计数工具，也揭示了图的结构性质。
第一步：定义与直观理解
- 独立集多项式：对于一个图G，我们用 \(i_k(G)\) 表示图中大小为k的独立集的个数。这里，大小为0的空集也被视为一个独立集，所以 \(i_0(G) = 1\)。那么，图G的独立集多项式 \(I(G; x)\) 定义为：
\[ I(G; x) = \sum_{k \ge 0} i_k(G) x^k \]
这是一个以x为变量的形式幂级数（对有限图来说是多项式），其系数按独立集的大小“分类计数”。例如，若 \(I(G; x) = 1 + 3x + 2x^2\)，表示G有1个空独立集，3个大小为1的独立集（即3个孤立点或互不相邻的单点），2个大小为2的独立集。
- 团多项式：类似地，用 \(c_k(G)\) 表示图中大小为k的团的个数。同样，单个顶点是一个大小为1的团，所以我们定义 \(c_0(G) = 1\) 和 \(c_1(G) = |V(G)|\)。图G的团多项式 \(C(G; x)\) 定义为：
\[ C(G; x) = \sum_{k \ge 0} c_k(G) x^k \]
它按团的大小对团进行计数。
第二步：基本性质与递推关系
这两个多项式最强大的性质之一是它们满足递推关系，这允许我们通过“分解”图来计算它们。关键在于选取一个顶点v进行处理。
- 对于独立集多项式：考虑图中任意顶点v。所有独立集可以分为两类：
- 不包含v的独立集：这些集合就是图 \(G - v\)（删除顶点v及其关联边）中的独立集。
- 包含v的独立集：如果一个独立集包含v，则它不能再包含v的任何邻居。因此，这类独立集等价于从图中删除v及其所有邻居后得到的图 \(G - N[v]\) 中的独立集，其中 \(N[v]\) 表示v及其邻居的集合。
因此，我们得到关键递推式：
\[ I(G; x) = I(G - v; x) + x \cdot I(G - N[v]; x) \]
等号右边的x因子是因为，在从 \(G - N[v]\) 中任取一个独立集S后，我们加入顶点v，得到了G中一个大小为 \(|S|+1\) 的独立集，在多项式中体现为次数增加1，所以乘以x。
- 对于团多项式：利用独立集与团的互补关系。图G的团，是其补图G̅的独立集。因此，团多项式可以通过补图的独立集多项式来定义：
\[ C(G; x) = I(\overline{G}; x) \]
同样地，在G上也可以建立直接的递推，思路类似：考虑一个顶点v，所有团分为不包含v的（即 \(C(G-v; x)\)）和包含v的。包含v的团，其剩余顶点必须都是v的邻居，且它们彼此也相邻。因此，这类团就是v的邻居集合 \(N(v)\) 在G中诱导出的子图 \(G[N(v)]\) 中的团，再每个加上v。所以有：
\[ C(G; x) = C(G - v; x) + x \cdot C(G[N(v)]; x) \]
注意这里是 \(N(v)\) 而非 \(N[v]\)，因为v自身已包含在内。
第三步：与图运算的关系
利用递推关系，我们可以推导多项式在图的基本运算下的行为。
- 不交并：如果图G由两个不相交的组件G₁和G₂组成，那么G中的一个独立集（或团）由G₁中的一个和G₂中的一个独立组合而成。因此有：
\[ I(G_1 \cup G_2; x) = I(G_1; x) \cdot I(G_2; x) \]
\[ C(G_1 \cup G_2; x) = C(G_1; x) \cdot C(G_2; x) \]
多项式相乘，系数对应卷积，这正反映了组合计数的乘法原理。
- 顶点粘连：将两个图在一个顶点处粘合，情况更复杂，但递推关系仍然适用，是计算复杂图多项式的基本工具。
第四步：根的分布与图的性质
独立集多项式和团多项式不仅是计数工具，其作为实系数多项式的根（零点）的分布，也与图的结构性质有深刻联系。
- 实根性：一个重要的发现是，对于任意图G，其独立集多项式 \(I(G; x)\) 的所有根都是实数（更准确地说，是负实数）。这个性质并非显然，它可以从多项式满足某种特定类型的递推关系推导出来，与对数凹性、单峰性等组合序列的性质相关。
- 复平面上的分布：即使不全是实根，研究这些多项式在复平面上根的分布（例如，是否总在单位圆盘内？是否避开某些区域？）是图论与统计物理（如配分函数）交叉的热点问题。例如，在计算某些模型的相变点时，多项式根的分布至关重要。
第五步：算法复杂性与计算
计算一个图的独立集多项式或团多项式的所有系数通常是极其困难的。
- #P-完全性：计算特定系数 \(i_k(G)\)（即大小为k的独立集个数）或 \(c_k(G)\) 已经是#P-完全问题，即使对于二分图或平面图也是如此。这意味着没有已知的多项式时间算法，除非P=NP。
- 近似计算：由于精确计算的困难，研究重点转向了近似计算多项式的值（在某点x处的函数值），以及研究多项式的确定性多项式时间近似方案。对于某些图类（如有界树宽的图），可以利用动态规划在多项式时间内精确计算这些多项式。
总结：
图的团多项式和独立集多项式是从组合计数角度刻画图结构的重要代数不变量。它们通过简洁的递推关系与图的基本运算相连，其根的分布蕴含着深刻的组合与概率性质。尽管精确计算通常是困难的，但对它们的研究连接了极值图论、代数组合、统计物理和计算复杂性理论等多个数学领域。