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:
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 |
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:
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.edges
[(0, 1), (1, 2), (2, 3)]
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.edges
[(0, 1), (1, 2), (2, 3)]
sage: E.vertices
[0, 1, 2, 3]
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
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
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]
Bases: object
x.__init__(...) initializes x; see help(type(x)) for signature
Bases: sage.graphs.tutte_polynomial.EdgeSelection
x.__init__(...) initializes x; see help(type(x)) for signature
Bases: sage.graphs.tutte_polynomial.EdgeSelection
x.__init__(...) initializes x; see help(type(x)) for signature
Bases: sage.graphs.tutte_polynomial.EdgeSelection
x.__init__(...) initializes x; see help(type(x)) for signature
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}
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')]
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)]
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)]
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')]
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),2) as Y:
....: G.edges()
[]
sage: G.edges()
[(0, 1, None), (0, 1, None)]
Return the Tutte polynomial of the graph .
INPUT:
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
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)]