Tutte polynomial¶
This module implements a deletion-contraction algorithm for computing the Tutte polynomial as described in the paper [Gordon10].
tutte_polynomial() |
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 , with
vertices and
edges and
connected components we define the Tutte polynomial of
as
where the sum ranges over all induced subgraphs of
.
REFERENCES:
[Gordon10] | (1, 2) Computing Tutte Polynomials. Gary Haggard, David J. Pearce and Gordon Royle. In ACM Transactions on Mathematical Software, Volume 37(3), article 24, 2010. Preprint: http://homepages.ecs.vuw.ac.nz/~djp/files/TOMS10.pdf |
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 [Gordon10]:
An ear in a graph is a path
where
,
and
.
A cycle is viewed as a special ear where
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
.
EXAMPLES:
sage: G = graphs.PathGraph(4) sage: G.add_edges([(0,4),(0,5),(3,6),(3,7)]) sage: len(G.edges()) 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() [(0, 4, None), (0, 5, None), (3, 6, None), (3, 7, None)] sage: len(G.edges()) 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]
-
static
-
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() [(0, 1, 'a'), (0, 3, 'c'), (1, 2, 'b')] sage: with contracted_edge(G,(0,1)) as Y: ....: G.edges(); G.vertices() [(1, 2, 'b'), (1, 3, 'c')] [1, 2, 3] sage: G.edges() [(0, 1, 'a'), (0, 3, 'c'), (1, 2, 'b')]
-
sage.graphs.tutte_polynomial.
edge_multiplicities
(G)¶ Returns the a dictionary of multiplicities of the edges in the graph
.
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).iteritems()) [((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
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() [(0, 1, None)] sage: with removed_edge(G,(0,1)) as Y: ....: G.edges(); G.vertices() [] [0, 1] sage: G.edges() [(0, 1, None)]
-
sage.graphs.tutte_polynomial.
removed_loops
(*args, **kwds)¶ A context manager which removes all the loops in the graph
. It yields a list of the 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() [(0, 0, 'c'), (0, 1, 'a'), (1, 2, 'b')] sage: with removed_loops(G) as Y: ....: G.edges(); G.vertices(); Y [(0, 1, 'a'), (1, 2, 'b')] [0, 1, 2] [(0, 0, 'c')] sage: G.edges() [(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
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() [(0, 1, 'a'), (0, 1, 'b')] sage: with removed_multiedge(G,(0,1)) as Y: ....: G.edges() [] sage: G.edges() [(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
.
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
is
:
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
evaluated at (1,1) is the number of spanning trees of
:
sage: G = graphs.RandomGNP(10,0.6) sage: G.tutte_polynomial()(1,1) == G.spanning_trees_count() True
Given that
is the Tutte polynomial of a graph
with
vertices and
connected components, then
is the chromatic polynomial of
.
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)
TESTS:
Providing an external cache:
sage: cache = {} sage: _ = graphs.RandomGNP(7,.5).tutte_polynomial(cache=cache) sage: len(cache) > 0 True
Verify that #18366 is fixed:
sage: g = Graph(multiedges=True) sage: g.add_edges([(0,1,1),(1,5,2),(5,3,3),(5,2,4),(2,4,5),(0,2,6),(0,3,7),(0,4,8),(0,5,9)]); sage: g.tutte_polynomial()(1,1) 52 sage: g.spanning_trees_count() 52
-
sage.graphs.tutte_polynomial.
underlying_graph
(G)¶ Given a graph
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() [(0, 1, 'a'), (0, 1, 'b')] sage: underlying_graph(G).edges() [(0, 1, None)]