tutte_polynomial#
- tutte_polynomial(G)[source]#
Returns the Tutte polynomial of
G
This function computes the Tutte polynomial via an iterative version of the deletion-contraction algorithm.
The Tutte polynomial
T_G(x, y)
is a fundamental graph polynomial invariant in two variables. It encodes a wide array of information related to the edge-connectivity of a graph; “Many problems about graphs can be reduced to problems of finding and evaluating the Tutte polynomial at certain values” [1]. In fact, every deletion-contraction-expressible feature of a graph is a specialization of the Tutte polynomial [2] (see Notes for examples).There are several equivalent definitions; here are three:
Def 1 (rank-nullity expansion): For
G
an undirected graph,n(G)
the number of vertices ofG
,E
the edge set ofG
,V
the vertex set ofG
, andc(A)
the number of connected components of the graph with vertex setV
and edge setA
[3]:\[T_G(x, y) = \sum_{A \in E} (x-1)^{c(A) - c(E)} (y-1)^{c(A) + |A| - n(G)}\]Def 2 (spanning tree expansion): Let
G
be an undirected graph,T
a spanning tree ofG
, andE
the edge set ofG
. LetE
have an arbitrary strict linear orderL
. LetB_e
be the unique minimal nonempty edge cut of \(E \setminus T \cup {e}\). An edgee
is internally active with respect toT
andL
ife
is the least edge inB_e
according to the linear orderL
. The internal activity ofT
(denotedi(T)
) is the number of edges in \(E \setminus T\) that are internally active with respect toT
andL
. LetP_e
be the unique path in \(T \cup {e}\) whose source and target vertex are the same. An edgee
is externally active with respect toT
andL
ife
is the least edge inP_e
according to the linear orderL
. The external activity ofT
(denotede(T)
) is the number of edges in \(E \setminus T\) that are externally active with respect toT
andL
. Then [4] [5]:\[T_G(x, y) = \sum_{T \text{ a spanning tree of } G} x^{i(T)} y^{e(T)}\]Def 3 (deletion-contraction recurrence): For
G
an undirected graph,G-e
the graph obtained fromG
by deleting edgee
,G/e
the graph obtained fromG
by contracting edgee
,k(G)
the number of cut-edges ofG
, andl(G)
the number of self-loops ofG
:\[\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}\]- Parameters:
- GNetworkX graph
- Returns:
- instance of
sympy.core.add.Add
A Sympy expression representing the Tutte polynomial for
G
.
- instance of
Notes
Some specializations of the Tutte polynomial:
T_G(1, 1)
counts the number of spanning trees ofG
T_G(1, 2)
counts the number of connected spanning subgraphs ofG
T_G(2, 1)
counts the number of spanning forests inG
T_G(0, 2)
counts the number of strong orientations ofG
T_G(2, 0)
counts the number of acyclic orientations ofG
Edge contraction is defined and deletion-contraction is introduced in [6]. Combinatorial meaning of the coefficients is introduced in [7]. Universality, properties, and applications are discussed in [8].
Practically, up-front computation of the Tutte polynomial may be useful when users wish to repeatedly calculate edge-connectivity-related information about one or more graphs.
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]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