chromatic_polynomial

chromatic_polynomial(G)

返回图 G 的色多项式

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

色多项式 X_G(x) 是一个基本的一元图多项式不变量。对自然数 k 计算 X_G(k) 可以枚举 G 的适当 k-着色。

有几种等价的定义；以下是三种：

定义 1（显式公式）： 对于无向图 G ， c(G) 是 G 的连通分量数， E 是 G 的边集， G(S) 是以 S 为边集的 G 的生成子图 [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 的顶点进行着色的不同方式数（对于最多 n(G) 的自然数 i ）， X_G(x) 是通过点 (0, k_0), (1, k_1), dots, (n(G), k_{n(G)}) 的唯一拉格朗日插值多项式，次数为 n(G) [2]。

定义 3（色递归）： 对于无向图 G ， G-e 是通过删除边 e 从 G 得到的图， G/e 是通过收缩边 e 从 G 得到的图， n(G) 是 G 的顶点数， e(G) 是 G 的边数 [3]：

\[\begin{split}X_G(x) = \begin{cases} x^{n(G)}, & \text{如果 $e(G)=0$} \\ X_{G-e}(x) - X_{G/e}(x), & \text{否则，对于任意边 $e$} \end{cases}\end{split}\]

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

Parameters:

GNetworkX 图

Returns:

sympy.core.add.Add 实例

表示 G 的色多项式的 Sympy 表达式。

Notes

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

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

色多项式可能取负参数，尽管计算结果可能没有色解释。例如， X_G(-1) 枚举了 G 的无环方向 [7]。

References

[1]

D. B. West, “Introduction to Graph Theory,” p. 222

[2]

E. W. Weisstein “Chromatic Polynomial” MathWorld–A Wolfram Web Resource https://mathworld.wolfram.com/ChromaticPolynomial.html

[3]

D. B. West, “Introduction to Graph Theory,” p. 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

Examples

>>> 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