tutte_polynomial#

tutte_polynomial(G)[源代码]#

返回下式的图特多项式 G

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

Tutte多项式 T_G(x, y) 是两个变量的基本图多项式不变量。它编码了一系列与图的边连通性有关的信息；“许多关于图的问题可以归结为寻找和计算特定值的图特多项式的问题。” [1]. 事实上，图的每个删除-收缩-可表达特征都是Tutte多项式的特化 [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(生成树扩展)：let G 是一个无向图， T 的一棵生成树 G ，以及 E 的边集 G 。让我们 E 具有任意严格的线性顺序 L 。让我们 B_e 是的唯一最小非空边割 \(E \setminus T \cup {{e}}\) 。一种优势 e 在内部是活跃的，关于 T 和 L 如果 e 是最小的边缘 B_e 根据线性顺序 L 。的内部活动 T (表示为 i(T) )中的边数 \(E \setminus T\) 在内部是活跃的，关于 T 和 L 。让我们 P_e 成为中国唯一的道路 \(T \cup {{e}}\) 其源顶点和目标顶点相同。一种优势 e 对于以下方面在外部是活跃的 T 和 L 如果 e 是最小的边缘 P_e 根据线性顺序 L 。的外部活动 T (表示为 e(T) )中的边数 \(E \setminus T\) 在外部是活跃的关于 T 和 L 。然后 [4] [5] ：

\[T_G(x，y)=\sum_{T\Text{生成树}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{Case} X^{k(G)}y^{l(G)}，&\Text{如果所有边都是割边或自环}\\ T_{G-e}(x，y)+T_{G/e}(x，y)，&\Text{否则，对于任意边$e$，不是切边或环} \结束{案例}\end{split}\]
参数
G网络X图表
返回
实例 sympy.core.add.Add

一种表示Tutte多项式的符号表达式 G 。

笔记

Tutte多项式的一些特化：

  • T_G(1, 1) counts the number of spanning trees of G

  • T_G(1, 2) counts the number of connected spanning subgraphs of G

  • T_G(2, 1) counts the number of spanning forests in G

  • T_G(0, 2) counts the number of strong orientations of G

  • T_G(2, 0) counts the number of acyclic orientations of G

定义了边收缩，并引入了删除-收缩 [6]. 中介绍了系数的组合含义。 [7]. 中讨论了通用性、属性和应用 [8].

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

工具书类

1

M.勃兰特，《图特多项式》。谈2015年https://math.berkeley.edu/~brandtm/talks/tutte.pdf组合对象研讨会

2

A.比约克伦德，T.HusFeldt，P.Kaski，M.Koivisto，《在顶点指数时间内计算图特多项式》，第49届IEEE计算机科学基础年会，2008 https://ieeexplore.ieee.org/abstract/document/4691000

3

石勇，M·德默，李祥，I·古特曼，《图形多项式》，第14页

4

石勇，M·德默，李晓华，I·古特曼，《图形多项式》，第46页

5

Https://iuuk.mff.cuni.cz/~andrew/Tutte.pdf，《图形不变量、同态和š多项式》

6

D.B.韦斯特，《图论导论》，第84页

7

G·库蒂尼奥，《图特多项式简介》，《复杂网络的结构分析》，2011年https://homepages.dcc.ufmg.br/~gabriel/seminars/coutinho_tuttepolynomial_seminar.pdf

8

《图多项式及其应用I：图特多项式》，《复杂网络的结构分析》，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