Document

tutte_polynomial(G)

This function computes the Tutte polynomial via an iterative version of the deletion-contraction algorithm.

The Tutte polynomial :None:None:`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" . In fact, every deletion-contraction-expressible feature of a graph is a specialization of the Tutte polynomial (see Notes for examples).

There are several equivalent definitions; here are three:

Def 1 (rank-nullity expansion): For G an undirected graph, :None:None:`n(G)` the number of vertices of G, :None:None:`E` the edge set of G, :None:None:`V` the vertex set of G, and :None:None:`c(A)` the number of connected components of the graph with vertex set :None:None:`V` and edge set :None:None:`A` :

$$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, :None:None:`T` a spanning tree of G, and :None:None:`E` the edge set of G. Let :None:None:`E` have an arbitrary strict linear order :None:None:`L`. Let :None:None:`B_e` be the unique minimal nonempty edge cut of $E \setminus T \cup {e}$. An edge :None:None:`e` is internally active with respect to :None:None:`T` and :None:None:`L` if :None:None:`e` is the least edge in :None:None:`B_e` according to the linear order :None:None:`L`. The internal activity of :None:None:`T` (denoted :None:None:`i(T)`) is the number of edges in $E \setminus T$ that are internally active with respect to :None:None:`T` and :None:None:`L`. Let :None:None:`P_e` be the unique path in $T \cup {e}$ whose source and target vertex are the same. An edge :None:None:`e` is externally active with respect to :None:None:`T` and :None:None:`L` if :None:None:`e` is the least edge in :None:None:`P_e` according to the linear order :None:None:`L`. The external activity of :None:None:`T` (denoted :None:None:`e(T)`) is the number of edges in $E \setminus T$ that are externally active with respect to :None:None:`T` and :None:None:`L`. Then :

$$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, :None:None:`G-e` the graph obtained from G by deleting edge :None:None:`e`, :None:None:`G/e` the graph obtained from G by contracting edge :None:None:`e`, :None:None:`k(G)` the number of cut-edges of G, and :None:None:`l(G)` the number of self-loops of G:

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

Notes

Some specializations of the Tutte polynomial:

:None:None:`T_G(1, 1)` counts the number of spanning trees of G
:None:None:`T_G(1, 2)` counts the number of connected spanning subgraphs of G
:None:None:`T_G(2, 1)` counts the number of spanning forests in G
:None:None:`T_G(0, 2)` counts the number of strong orientations of G
:None:None:`T_G(2, 0)` counts the number of acyclic orientations of G

Edge contraction is defined and deletion-contraction is introduced in . Combinatorial meaning of the coefficients is introduced in . Universality, properties, and applications are discussed in .

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.

Parameters

G : NetworkX graph

Returns

instance of `sympy.core.add.Add`: A Sympy expression representing the Tutte polynomial for G.

Returns the Tutte polynomial of G

Examples

This example is valid syntax, but raise an exception at execution

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

This example is valid syntax, but raise an exception at execution

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

See :

Back References

The following pages refer to to this document either explicitly or contain code examples using this.

networkx.algorithms.polynomials.tutte_polynomial

Local connectivity graph

Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.

Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)

SVG is more flexible but power hungry; and does not scale well to 50 + nodes.

All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them

GitHub : /networkx/algorithms/polynomials.py#18
type: <class 'function'>
Commit: