compute Tutte polynomial
compute chromatic polynomial
compute flow polynomial
compute rank polynomial
compute acyclic polynomial
compute reliability polynomial
TuttePolynomial(H, x, y)
RankPolynomial(G, x, y)
undirected unweighted graph
variables or values
The TuttePolynomial command returns a bivariate polynomial in x and y when x and y are variables or the evaluation of the bivariate polynomial when x or y are values.
The Tutte polynomial, T(G;x,y), is a generalization of the chromatic polynomial and is defined as follows:
If G has no edges then T(G;x,y) = 1.
Let e be any edge in G and let G-e and G/e denote the graph G with e removed and with e contracted, respectively.
If e is a loop then T(G;x,y) = y*T(G-e;x,y)
If e is a bridge (cut-edge) then T(G;x,y) = x*T(G/e;x,y)
If e is not a bridge nor a loop then T(G;x,y) = T(G-e;x,y) + T(G/e;x,y)
The ChromaticPolynomial, FlowPolynomial, RankPolynomial, and ReliabilityPolynomial are functions of the Tutte polynomial. They are all NP-hard to compute in general.
The ChromaticPolynomial command returns a polynomial, P(G,t), which is the number of proper vertex colorings of G using no more than t colors, where t is a non-negative integer.
The chromatic polynomial, P(G;t), for a graph G with n vertices, and k connected components, can be expressed in terms of the Tutte polynomial T(G;x,y), as follows:
P(G;t) = (-1)^(n-k)*t^k*T(G;1-t,0)
P(G,t) has been determined for certain classes of graphs. Fast codes for the special cases for the complete graph, its complement, trees and cycles have been included in the command.
FlowPolynomial and RankPolynomial
The FlowPolynomial command returns a polynomial in x when x is a variable or the evaluation of the polynomial when x is a value. The value of this polynomial at a positive integer k gives the number of nowhere-zero flows on G with edge labels chosen from the integers modulo k.
The flow polynomial, Q(G;x), for a graph G with n vertices, m edges, and k connected components, can be expressed in terms of the Tutte polynomial, T(G;x,y), as follows:
Q(G;x) = (-1)^(m-n+k)*T(G;0,1-x)
The RankPolynomial command returns a bivariate polynomial in x and y when x and y are variables or the evaluation of the polynomial when x or y are values.
S(G;x,y) = T(G;x+1,y+1) where S(G;x,y) is the rank polynomial of G.
AcyclicPolynomial and ReliabilityPolynomial
The AcyclicPolynomial command returns a polynomial in p when p is a variable or the evaluation of the polynomial when p is a value. The value of this polynomial at a value 0≤p≤1 gives the probability that G is acyclic when each edge operates with probability p.
The ReliabilityPolynomial command returns a polynomial in p when p is a variable or the evaluation of the polynomial when p is a value. The value of this polynomial at a value 0≤p≤1 gives the probability that G is connected when each edge fails with probability p. For example, if G is a tree on n vertices, then if any edge fails G will become disconnected. Hence the reliability polynomial for a tree is (1-p)^(n-1). It can be computed as follows.
If the graph G is not connected, then its reliability polynomial is 0.
If e is a loop in G then R(G;p) = R(G-e;p)
If e is a bridge (isthmus) then R(G;p) = (1-p)*T(G/e;p)
If e is not a bridge nor a loop then R(G;p) = p*R(G-e;p) + (1-p)*R(G/e;p)
If G has n vertices and m edges, the reliability polynomial R(G;p) is related to the Tutte polynomial T(G;x,y) as follows
R(G;p) = T(G;1,1/p)*p^(n-1)*(1-p)^(m-n+1)
The TuttePolynomial and ReliabilityPolynomial commands accept a weighted graph H as input. The edge weights must be positive integers and they are interpreted as multiple edges.
The computation of the Tutte polynomial is NP-hard. We compute the Tutte polynomial using edge deletion and contraction and we remember the Tutte polynomial for each connected subgraph computed. By processing edges in a canonical ordering this enables us to identify subgraphs already seen without using a general graph isomorphism test. See references  and  Monagan in the References section.
G ≔ CompleteGraph⁡4
G≔Graph 1: an undirected graph with 4 vertices and 6 edge(s)
We can verify the recurrence relation
G ≔ PetersenGraph⁡
G≔Graph 2: an undirected graph with 10 vertices and 15 edge(s)
f ≔ TuttePolynomial⁡G,'x','y'
e ≔ Edges⁡G1
Gminuse ≔ DeleteEdge⁡G,e,'inplace'=false
Gminuse≔Graph 3: an undirected graph with 10 vertices and 14 edge(s)
Gcontracte ≔ Contract⁡G,e,'inplace'=false
Gcontracte≔Graph 4: an undirected graph with 9 vertices and 14 edge(s)
P ≔ ChromaticPolynomial⁡G,'x'
This must be zero since the Petersen graph is not 2-colorable
K ≔ CompleteGraph⁡10
K≔Graph 5: an undirected graph with 10 vertices and 45 edge(s)
We can convince ourselves that this graph needs 10 colors and can be colored 10! ways with 10 colors
Q ≔ FlowPolynomial⁡G,x
T ≔ TuttePolynomial⁡G,0,1−x
n ≔ NumberOfVertices⁡G
m ≔ NumberOfEdges⁡G
k ≔ nops⁡ConnectedComponents⁡G
K4 ≔ CompleteGraph⁡4
K4≔Graph 6: an undirected graph with 4 vertices and 6 edge(s)
S ≔ RankPolynomial⁡K4,x,y
The number of subgraphs
The number of acyclic subgraphs
The number of subgraphs whose rank = rank(G)
The number of maximum spanning forests
ReliabilityPolynomial and AcyclicPolynomial
P ≔ Graph⁡1,2,2,3
P≔Graph 7: an undirected graph with 3 vertices and 2 edge(s)
R ≔ ReliabilityPolynomial⁡P,p
The reliability of a connected network should increase if we add an edge. The difference Q-P below is positive for 0<p<1.
Graph 7: an undirected graph with 3 vertices and 3 edge(s)
Q ≔ ReliabilityPolynomial⁡P,p
Multiple edges may be specified as edge weights.
G ≔ Graph⁡1,2,2,2,3,1,3,1,1
G≔Graph 8: an undirected weighted graph with 3 vertices and 3 edge(s)
The following graph represents the Arpanet, the early internet, in late 1970.
V ≔ MIT,LINCOLN,CASE,CMU,HARVARD,BBN,UCSB,UCLA,STANFORD,SRI,RAND,UTAH,SDC:
Arpanet ≔ Graph⁡V,Trail⁡UCSB,UCLA,RAND,SDC,UTAH,SRI,STANFORD,UCLA,SRI,UCSB,UTAH,MIT,RAND,BBN,Trail⁡MIT,LINCOLN,CASE,CMU,HARVARD,BBN,MIT
Arpanet≔Graph 9: an undirected graph with 13 vertices and 17 edge(s)
R ≔ ReliabilityPolynomial⁡Arpanet,p
Which edge (link) should we add to the Arpanet to improve the reliability the most? Let's try adding the edge from Stanford to CMU.
H ≔ AddEdge⁡Arpanet,STANFORD,CMU,inplace=false
H≔Graph 10: an undirected graph with 13 vertices and 18 edge(s)
S ≔ ReliabilityPolynomial⁡H,p
We can compare the reliability polynomials visually for 0≤p≤1 then compute the improvement by computing the area of the enclosed curves as an integral.
improvement ≔ ∫01S−Rⅆp
 Bollobás, Béla. Modern Graph Theory. Graduate Texts in Mathematics, 184, Springer-Verlag, New York, 1998.
 Farr, Khatarinejad, Khodadad, and Monagan. A Graph Theory Package for Maple. Proceedings of the 2005 Maple Conference, Maplesoft, July 2005: 260-271.
 Haggard, Pearce, and Royle. "Computing Tutte Polynomials." TOMS. Vol. 37(24). (2010): 1-17.
 Monagan. "A new edge selection heuristic for computing Tutte polynomials." Proceedings of FPSAC 2012.
The GraphTheory[ReliabilityPolynomial] command was introduced in Maple 17.
For more information on Maple 17 changes, see Updates in Maple 17.
Download Help Document