Tutte polynomial#
This module implements a deletion-contraction algorithm for computing the Tutte polynomial as described in the paper [HPR2010].
Computes the Tutte polynomial of the input graph |
Authors:
Mike Hansen (06-2013), Implemented the algorithm.
Jernej Azarija (06-2013), Tweaked the code, added documentation
Definition#
Given a graph \(G\), with \(n\) vertices and \(m\) edges and \(k(G)\) connected components we define the Tutte polynomial of \(G\) as
where the sum ranges over all induced subgraphs \(H\) of \(G\).
Functions#
- class sage.graphs.tutte_polynomial.Ear(graph, end_points, interior, is_cycle)#
Bases:
object
An ear is a sequence of vertices
Here is the definition from [HPR2010]:
An ear in a graph is a path \(v_1 - v_2 - \dots - v_n - v_{n+1}\) where \(d(v_1) > 2\), \(d(v_{n+1}) > 2\) and \(d(v_2) = d(v_3) = \dots = d(v_n) = 2\).
A cycle is viewed as a special ear where \(v_1 = v_{n+1}\) and the restriction on the degree of this vertex is lifted.
INPUT:
- static find_ear(g)#
Finds the first ear in a graph.
EXAMPLES:
sage: G = graphs.PathGraph(4) sage: G.add_edges([(0,4),(0,5),(3,6),(3,7)]) sage: from sage.graphs.tutte_polynomial import Ear sage: E = Ear.find_ear(G) sage: E.s 3 sage: E.unlabeled_edges [(0, 1), (1, 2), (2, 3)] sage: E.vertices [0, 1, 2, 3]
- removed_from(*args, **kwds)#
A context manager which removes the ear from the graph \(G\).
EXAMPLES:
sage: G = graphs.PathGraph(4) sage: G.add_edges([(0,4),(0,5),(3,6),(3,7)]) sage: len(G.edges(sort=True)) 7 sage: from sage.graphs.tutte_polynomial import Ear sage: E = Ear.find_ear(G) sage: with E.removed_from(G) as Y: ....: G.edges(sort=True) [(0, 4, None), (0, 5, None), (3, 6, None), (3, 7, None)] sage: len(G.edges(sort=True)) 7
- s#
Returns the number of distinct edges in this ear.
EXAMPLES:
sage: G = graphs.PathGraph(4) sage: G.add_edges([(0,4),(0,5),(3,6),(3,7)]) sage: from sage.graphs.tutte_polynomial import Ear sage: E = Ear(G,[0,3],[1,2],False) sage: E.s 3
- unlabeled_edges()#
Returns the edges in this ear.
EXAMPLES:
sage: G = graphs.PathGraph(4) sage: G.add_edges([(0,4),(0,5),(3,6),(3,7)]) sage: from sage.graphs.tutte_polynomial import Ear sage: E = Ear(G,[0,3],[1,2],False) sage: E.unlabeled_edges [(0, 1), (1, 2), (2, 3)]
- vertices#
Returns the vertices of this ear.
EXAMPLES:
sage: G = graphs.PathGraph(4) sage: G.add_edges([(0,4),(0,5),(3,6),(3,7)]) sage: from sage.graphs.tutte_polynomial import Ear sage: E = Ear(G,[0,3],[1,2],False) sage: E.vertices [0, 1, 2, 3]
- class sage.graphs.tutte_polynomial.EdgeSelection#
Bases:
object
- class sage.graphs.tutte_polynomial.MaximizeDegree#
- class sage.graphs.tutte_polynomial.MinimizeDegree#
- class sage.graphs.tutte_polynomial.MinimizeSingleDegree#
- class sage.graphs.tutte_polynomial.VertexOrder(order)#
Bases:
sage.graphs.tutte_polynomial.EdgeSelection
EXAMPLES:
sage: from sage.graphs.tutte_polynomial import VertexOrder sage: A = VertexOrder([4,6,3,2,1,7]) sage: A.order [4, 6, 3, 2, 1, 7] sage: A.inverse_order {1: 4, 2: 3, 3: 2, 4: 0, 6: 1, 7: 5}
- sage.graphs.tutte_polynomial.contracted_edge(*args, **kwds)#
Delete the first vertex in the edge, and make all the edges that went from it go to the second vertex.
EXAMPLES:
sage: from sage.graphs.tutte_polynomial import contracted_edge sage: G = Graph(multiedges=True) sage: G.add_edges([(0,1,'a'),(1,2,'b'),(0,3,'c')]) sage: G.edges(sort=True) [(0, 1, 'a'), (0, 3, 'c'), (1, 2, 'b')] sage: with contracted_edge(G,(0,1)) as Y: ....: G.edges(sort=True); G.vertices(sort=True) [(1, 2, 'b'), (1, 3, 'c')] [1, 2, 3] sage: G.edges(sort=True) [(0, 1, 'a'), (0, 3, 'c'), (1, 2, 'b')]
- sage.graphs.tutte_polynomial.edge_multiplicities(G)#
Return the dictionary of multiplicities of the edges in the graph \(G\).
EXAMPLES:
sage: from sage.graphs.tutte_polynomial import edge_multiplicities sage: G = Graph({1: [2,2,3], 2: [2], 3: [4,4], 4: [2,2,2]}) sage: sorted(edge_multiplicities(G).items()) [((1, 2), 2), ((1, 3), 1), ((2, 2), 1), ((2, 4), 3), ((3, 4), 2)]
- sage.graphs.tutte_polynomial.removed_edge(*args, **kwds)#
A context manager which removes an edge from the graph \(G\) and restores it upon exiting.
EXAMPLES:
sage: from sage.graphs.tutte_polynomial import removed_edge sage: G = Graph() sage: G.add_edge(0,1) sage: G.edges(sort=True) [(0, 1, None)] sage: with removed_edge(G,(0,1)) as Y: ....: G.edges(sort=True); G.vertices(sort=True) [] [0, 1] sage: G.edges(sort=True) [(0, 1, None)]
- sage.graphs.tutte_polynomial.removed_loops(*args, **kwds)#
A context manager which removes all the loops in the graph \(G\). It yields a list of the loops, and restores the loops upon exiting.
EXAMPLES:
sage: from sage.graphs.tutte_polynomial import removed_loops sage: G = Graph(multiedges=True, loops=True) sage: G.add_edges([(0,1,'a'),(1,2,'b'),(0,0,'c')]) sage: G.edges(sort=True) [(0, 0, 'c'), (0, 1, 'a'), (1, 2, 'b')] sage: with removed_loops(G) as Y: ....: G.edges(sort=True); G.vertices(sort=True); Y [(0, 1, 'a'), (1, 2, 'b')] [0, 1, 2] [(0, 0, 'c')] sage: G.edges(sort=True) [(0, 0, 'c'), (0, 1, 'a'), (1, 2, 'b')]
- sage.graphs.tutte_polynomial.removed_multiedge(*args, **kwds)#
A context manager which removes an edge with multiplicity from the graph \(G\) and restores it upon exiting.
EXAMPLES:
sage: from sage.graphs.tutte_polynomial import removed_multiedge sage: G = Graph(multiedges=True) sage: G.add_edges([(0,1,'a'),(0,1,'b')]) sage: G.edges(sort=True) [(0, 1, 'a'), (0, 1, 'b')] sage: with removed_multiedge(G,(0,1)) as Y: ....: G.edges(sort=True) [] sage: G.edges(sort=True) [(0, 1, 'a'), (0, 1, 'b')]
- sage.graphs.tutte_polynomial.tutte_polynomial(G, edge_selector=None, cache=None)#
Return the Tutte polynomial of the graph \(G\).
INPUT:
edge_selector
(optional; method) this argument allows the user to specify his own heuristic for selecting edges used in the deletion contraction recurrencecache
– (optional; dict) a dictionary to cache the Tutte polynomials generated in the recursive process. One will be created automatically if not provided.
EXAMPLES:
The Tutte polynomial of any tree of order \(n\) is \(x^{n-1}\):
sage: all(T.tutte_polynomial() == x**9 for T in graphs.trees(10)) True
The Tutte polynomial of the Petersen graph is:
sage: P = graphs.PetersenGraph() sage: P.tutte_polynomial() x^9 + 6*x^8 + 21*x^7 + 56*x^6 + 12*x^5*y + y^6 + 114*x^5 + 70*x^4*y + 30*x^3*y^2 + 15*x^2*y^3 + 10*x*y^4 + 9*y^5 + 170*x^4 + 170*x^3*y + 105*x^2*y^2 + 65*x*y^3 + 35*y^4 + 180*x^3 + 240*x^2*y + 171*x*y^2 + 75*y^3 + 120*x^2 + 168*x*y + 84*y^2 + 36*x + 36*y
The Tutte polynomial of a connected graph \(G\) evaluated at (1,1) is the number of spanning trees of \(G\):
sage: G = graphs.RandomGNP(10,0.6) sage: while not G.is_connected(): ....: G = graphs.RandomGNP(10,0.6) sage: G.tutte_polynomial()(1,1) == G.spanning_trees_count() True
Given that \(T(x,y)\) is the Tutte polynomial of a graph \(G\) with \(n\) vertices and \(c\) connected components, then \((-1)^{n-c} x^k T(1-x,0)\) is the chromatic polynomial of \(G\).
sage: G = graphs.OctahedralGraph() sage: T = G.tutte_polynomial() sage: R = PolynomialRing(ZZ, 'x') sage: R((-1)^5*x*T(1-x,0)).factor() (x - 2) * (x - 1) * x * (x^3 - 9*x^2 + 29*x - 32) sage: G.chromatic_polynomial().factor() (x - 2) * (x - 1) * x * (x^3 - 9*x^2 + 29*x - 32)
- sage.graphs.tutte_polynomial.underlying_graph(G)#
Given a graph \(G\) with multi-edges, returns a graph where all the multi-edges are replaced with a single edge.
EXAMPLES:
sage: from sage.graphs.tutte_polynomial import underlying_graph sage: G = Graph(multiedges=True) sage: G.add_edges([(0,1,'a'),(0,1,'b')]) sage: G.edges(sort=True) [(0, 1, 'a'), (0, 1, 'b')] sage: underlying_graph(G).edges(sort=True) [(0, 1, None)]