tutte_polynomial#

tutte_polynomial(G)[source]#

返回图 G 的 Tutte 多项式

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

Tutte 多项式 T_G(x, y) 是一个在两个变量中的基本图多项式不变量。它编码了与图的边连通性相关的广泛信息；“关于图的许多问题可以简化为在某些值上找到并评估 Tutte 多项式的问题” [1]。事实上，图的每个可删除-收缩表达的特征都是 Tutte 多项式的一个特化 [R327ca76ea34f-2]_（参见注释中的示例）。

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

定义 1（秩-零度展开）：对于 G 是一个无向图， n(G) 是 G 的顶点数， E 是 G 的边集， V 是 G 的顶点集， c(A) 是具有顶点集 V 和边集 A 的图的连通分量数 [3]：

\[T_G(x, y) = \sum_{A \in E} (x-1)^{c(A) - c(E)} (y-1)^{c(A) + |A| - n(G)}\]

定义 2（生成树展开）：设 G 是一个无向图， T 是 G 的一个生成树， E 是 G 的边集。设 E 有一个任意的严格线性顺序 L 。设 B_e 是 \(E \setminus T \cup {e}\) 的唯一最小非空边割。边 e 相对于 T 和 L 是内部活动的，如果 e 是根据线性顺序 L 在 B_e 中的最小边。 T 的内部活动（记为 i(T) ）是 \(E \setminus T\) 中相对于 T 和 L 是内部活动的边的数量。设 P_e 是 \(T \cup {e}\) 中源顶点和目标顶点相同的唯一路径。边 e 相对于 T 和 L 是外部活动的，如果 e 是根据线性顺序 L 在 P_e 中的最小边。 T 的外部活动（记为 e(T) ）是 \(E \setminus T\) 中相对于 T 和 L 是外部活动的边的数量。然后 [4] [5]：

\[T_G(x, y) = \sum_{T \text{ 是 } G \text{ 的生成树}} x^{i(T)} y^{e(T)}\]

定义 3（删除-收缩递归）：对于 G 是一个无向图， G-e 是通过删除边 e 从 G 得到的图， G/e 是通过收缩边 e 从 G 得到的图， k(G) 是 G 的割边数， l(G) 是 G 的自环数：

\[\begin{split}T_G(x, y) = \begin{cases} x^{k(G)} y^{l(G)}, & \text{如果所有边都是割边或自环} \\ T_{G-e}(x, y) + T_{G/e}(x, y), & \text{否则，对于任意不是割边或自环的边 $e$} \end{cases}\end{split}\]
Parameters:
GNetworkX 图
Returns:
sympy.core.add.Add 实例

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

Notes

Tutte 多项式的一些特化：

  • T_G(1, 1) 计算 G 的生成树数量

  • T_G(1, 2) 计算 G 的连通生成子图数量

  • T_G(2, 1) 计算 G 的生成森林数量

  • T_G(0, 2) 计算 G 的强定向数量

  • T_G(2, 0) 计算 G 的非循环定向数量

边收缩在 [6] 中定义，删除-收缩在 [6] 中引入。系数的组合意义在 [7] 中引入。普遍性、性质和应用在 [8] 中讨论。

实际上，当用户希望重复计算一个或多个图的边连通性相关信息时，预先计算 Tutte 多项式可能是有用的。

References

[1]

M. Brandt, “The Tutte Polynomial.” Talking About Combinatorial Objects Seminar, 2015 https://math.berkeley.edu/~brandtm/talks/tutte.pdf

[2]

A. Björklund, T. Husfeldt, P. Kaski, M. Koivisto, “Computing the Tutte polynomial in vertex-exponential time” 49th Annual IEEE Symposium on Foundations of Computer Science, 2008 https://ieeexplore.ieee.org/abstract/document/4691000

[3]

Y. Shi, M. Dehmer, X. Li, I. Gutman, “Graph Polynomials,” p. 14

[4]

Y. Shi, M. Dehmer, X. Li, I. Gutman, “Graph Polynomials,” p. 46

[5]

A. Nešetril, J. Goodall, “Graph invariants, homomorphisms, and the Tutte polynomial” https://iuuk.mff.cuni.cz/~andrew/Tutte.pdf

[6] (1,2)

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

[7]

G. Coutinho, “A brief introduction to the Tutte polynomial” Structural Analysis of Complex Networks, 2011 https://homepages.dcc.ufmg.br/~gabriel/seminars/coutinho_tuttepolynomial_seminar.pdf

[8]

J. A. Ellis-Monaghan, C. Merino, “Graph polynomials and their applications I: The Tutte polynomial” Structural Analysis of Complex Networks, 2011 https://arxiv.org/pdf/0803.3079.pdf

Examples

>>> C = nx.cycle_graph(5)
>>> nx.tutte_polynomial(C)
x**4 + x**3 + x**2 + x + y

>>> D = nx.diamond_graph()
>>> nx.tutte_polynomial(D)
x**3 + 2*x**2 + 2*x*y + x + y**2 + y
On this page