色多项式

chromatic_polynomial(G)

返回图 G 的色多项式

此函数通过删除-收缩算法的迭代版本计算色多项式。

色多项式 X_G(x) 是图论中一个基本的不变量多项式。对于自然数 k，计算 X_G(k) 可以得到图 G 的真 k-着色数。

色多项式有几个等价的定义；这里列出三个

定义 1 (显式公式): 对于无向图 G，c(G) 是 G 的连通分量数，E 是 G 的边集，G(S) 是 G 以 S 为边集的生成子图 [1]

\[X_G(x) = \sum_{S \subseteq E} (-1)^{|S|} x^{c(G(S))}\]

定义 2 (插值多项式): 对于无向图 G，n(G) 是 G 的顶点数，k_0 = 0，k_i 是用 i 种唯一颜色对 G 的顶点进行着色的不同方法数 (对于自然数 i 且 i 至多为 n(G))，则 X_G(x) 是通过点 (0, k_0), (1, k_1), dots, (n(G), k_{n(G)}) 的唯一 n(G) 次 Lagrange 插值多项式 [2]。

定义 3 (色递推): 对于无向图 G，G-e 是从 G 中删除边 e 得到的图，G/e 是从 G 中收缩边 e 得到的图，n(G) 是 G 的顶点数，e(G) 是 G 的边数 [3]

\[\begin{split}X_G(x) = \begin{cases} x^{n(G)}, & \text{if $e(G)=0$} \\ X_{G-e}(x) - X_{G/e}(x), & \text{otherwise, for an arbitrary edge $e$} \end{cases}\end{split}\]

此公式也称为基本归约定理 [4]。

参数:

GNetworkX 图

返回:

类型为 sympy.core.add.Add 的实例

一个表示图 G 色多项式的 Sympy 表达式。

注意

系数的解释在 [5] 中讨论。几种特殊情况列在 [2] 中。

色多项式是 Tutte 多项式的一个特例；特别是，X_G(x) = T_G(x, 0) [6]。

色多项式可以接受负数作为参数，尽管其计算结果可能没有颜色解释。例如，X_G(-1) 表示图 G 的无环定向数 [7]。

参考文献

[1]

D. B. West，《图论导引》(Introduction to Graph Theory)，第 222 页

[2] (1,2)

E. W. Weisstein，“色多项式”(Chromatic Polynomial)，MathWorld – Wolfram Web Resource https://mathworld.net.cn/ChromaticPolynomial.html

[3]

D. B. West，《图论导引》(Introduction to Graph Theory)，第 221 页

[4]

J. Zhang, J. Goodall，“色多项式导论”(An Introduction to Chromatic Polynomials) https://math.mit.edu/~apost/courses/18.204_2018/Julie_Zhang_paper.pdf

[5]

R. C. Read，“色多项式导论”(An Introduction to Chromatic Polynomials)，Journal of Combinatorial Theory, 1968 https://math.berkeley.edu/~mrklug/ReadChromatic.pdf

[6]

W. T. Tutte，“图多项式”(Graph-polynomials)，Advances in Applied Mathematics, 2004 https://www.sciencedirect.com/science/article/pii/S0196885803000411

[7]

R. P. Stanley，“图的无环定向”(Acyclic orientations of graphs)，Discrete Mathematics, 2006 https://math.mit.edu/~rstan/pubs/pubfiles/18.pdf

示例

>>> C = nx.cycle_graph(5)
>>> nx.chromatic_polynomial(C)
x**5 - 5*x**4 + 10*x**3 - 10*x**2 + 4*x

>>> G = nx.complete_graph(4)
>>> nx.chromatic_polynomial(G)
x**4 - 6*x**3 + 11*x**2 - 6*x