tutte_polynomial#

tutte_polynomial(G)[source]#

返回图 G 的 Tutte 多项式

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

Tutte 多项式 T_G(x, y) 是一个基本的二元图多项式不变量。它编码了与图的边连通性相关的广泛信息；“许多图问题都可以归结为在特定值处寻找和计算 Tutte 多项式的问题” [1]。事实上，图的每一个可由删除-收缩表示的特征都是 Tutte 多项式的一种特殊形式 [2]（示例请参阅“备注”）。

Tutte 多项式有几种等价定义；以下是三种

定义 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 根据线性序 L 是 B_e 中的最小边，则称边 e 关于 T 和 L 是内部活跃的。T 的内部活跃度（记作 i(T)）是 \(E \setminus T\) 中关于 T 和 L 内部活跃的边数。设 P_e 是 \(T \cup {e}\) 中源顶点和目标顶点相同的唯一路径。如果边 e 根据线性序 L 是 P_e 中的最小边，则称边 e 关于 T 和 L 是外部活跃的。T 的外部活跃度（记作 e(T)）是 \(E \setminus T\) 中关于 T 和 L 外部活跃的边数。则 [4] [5]

\[T_G(x, y) = \sum_{T \text{ a spanning tree of } G} x^{i(T)} y^{e(T)}\]

定义 3（删除-收缩递推关系）：对于无向图 G，G-e 是由 G 删除边 e 得到的图，G/e 是由 G 收缩边 e 得到的图，k(G) 是 G 的桥的数量，l(G) 是 G 的自环数量

\[\begin{split}T_G(x, y) = \begin{cases} x^{k(G)} y^{l(G)}, & \text{if all edges are cut-edges or self-loops} \\ T_{G-e}(x, y) + T_{G/e}(x, y), & \text{otherwise, for an arbitrary edge $e$ not a cut-edge or loop} \end{cases}\end{split}\]
参数:
GNetworkX 图
返回:
sympy.core.add.Add 的实例

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

备注

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]。系数的组合意义介绍见 [7]。关于普适性、性质和应用的讨论见 [8]。

在实践中，如果用户需要重复计算一个或多个图的边连通性相关信息，预先计算 Tutte 多项式可能会很有用。

参考文献

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

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

示例

>>> 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
在本页上