Online Help

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.

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.

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\le p\le 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\le p\le 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 [2] and [4] Monagan in the References section.

$G≔\mathrm{CompleteGraph}\left(4\right)$

$G≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 4\; vertices\; and\; 6\; edges}$

$\mathrm{TuttePolynomial}\left(G\,'x'\,'y'\right)$

$x^3+y^3+3x^2+4xy+3y^2+2x+2y$

$\mathrm{TuttePolynomial}\left(G\,'x'\,1\right)$

$x^3+3x^2+6x+6$

$G≔\mathrm{PetersenGraph}\left(\right)$

$G≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 15\; edges}$

$f≔\mathrm{TuttePolynomial}\left(G\,'x'\,'y'\right)$

$f≔x^9+6x^8+21x^7+56x^6+12x^{5}y+y^6+114x^5+70x^{4}y+30x^3{y}^2+15x^2{y}^3+10x{y}^4+9y^5+170x^4+170x^{3}y+105x^2{y}^2+65x{y}^3+35y^4+180x^3+240x^{2}y+171x{y}^2+75y^3+120x^2+168xy+84y^2+36x+36y$

$e≔\mathrm{Edges}\left(G\right)\left[1\right]$

$e≔\left\{1\,2\right\}$

$\mathrm{Gminuse}≔\mathrm{DeleteEdge}\left(G\,e\,'\mathrm{inplace}'=\mathrm{false}\right)$

$\mathrm{Gminuse}≔\mathrm{Graph\; 3:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 14\; edges}$

$\mathrm{Gcontracte}≔\mathrm{Contract}\left(G\,e\,'\mathrm{inplace}'=\mathrm{false}\right)$

$\mathrm{Gcontracte}≔\mathrm{Graph\; 4:\; an\; undirected\; graph\; with\; 9\; vertices\; and\; 14\; edges}$

$\mathrm{expand}\left(f-\left(\mathrm{TuttePolynomial}\left(\mathrm{Gminuse}\,'x'\,'y'\right)+\mathrm{TuttePolynomial}\left(\mathrm{Gcontracte}\,'x'\,'y'\right)\right)\right)$

$0$

$P≔\mathrm{ChromaticPolynomial}\left(G\,'x'\right)$

$P≔x\left(x-1\right)\left(x-2\right)\left(x^7-12x^6+67x^5-230x^4+529x^3-814x^2+775x-352\right)$

This must be zero since the Petersen graph is not 2-colorable

$\mathrm{eval}\left(P\,x=2\right)$

$0$

$\mathrm{eval}\left(P\,x=3\right)$

$120$

We can verify the recurrence relation

$\mathrm{expand}\left(P-\left(\mathrm{ChromaticPolynomial}\left(\mathrm{Gminuse}\,'x'\right)-\mathrm{ChromaticPolynomial}\left(\mathrm{Gcontracte}\,'x'\right)\right)\right)$

$0$

$K≔\mathrm{CompleteGraph}\left(10\right)$

$K≔\mathrm{Graph\; 5:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 45\; edges}$

We can convince ourselves that this graph needs 10 colors and can be colored 10! ways with 10 colors

$\mathrm{ChromaticPolynomial}\left(K\,'t'\right)$

$t\left(t-1\right)\left(t-2\right)\left(t-3\right)\left(t-4\right)\left(t-5\right)\left(t-6\right)\left(t-7\right)\left(t-8\right)\left(t-9\right)$

$\mathrm{ChromaticPolynomial}\left(K\,10\right)-10!$

$0$

$\mathrm{ChromaticPolynomial}\left(\mathrm{RandomTree}\left(100\right)\,'t'\right)$

$t{\left(t-1\right)}^{99}$

$Q≔\mathrm{FlowPolynomial}\left(G\,x\right)$

$Q≔x^6-15x^5+95x^4-325x^3+624x^2-620x+240$

$\mathrm{eval}\left(Q\,x=4\right)$

$0$

$\mathrm{eval}\left(Q\,x=5\right)$

$240$

$T≔\mathrm{TuttePolynomial}\left(G\,0\,1-x\right)$

$T≔x^6-15x^5+95x^4-325x^3+624x^2-620x+240$

$n≔\mathrm{NumberOfVertices}\left(G\right)$

$n≔10$

$m≔\mathrm{NumberOfEdges}\left(G\right)$

$m≔15$

$k≔\mathrm{nops}\left(\mathrm{ConnectedComponents}\left(G\right)\right)$

$k≔1$

$\mathrm{expand}\left(Q-{\left(-1\right)}^{m-n+k}T\right)$

$0$

$\mathrm{K4}≔\mathrm{CompleteGraph}\left(4\right)$

$\mathrm{K4}≔\mathrm{Graph\; 6:\; an\; undirected\; graph\; with\; 4\; vertices\; and\; 6\; edges}$

$S≔\mathrm{RankPolynomial}\left(\mathrm{K4}\,x\,y\right)$

$S≔x^3+y^3+6x^2+4xy+6y^2+15x+15y+16$

The number of subgraphs

$\mathrm{eval}\left(S\,\left\{x=1\,y=1\right\}\right)$

$64$

The number of acyclic subgraphs

$\mathrm{eval}\left(S\,\left\{x=1\,y=0\right\}\right)$

$38$

The number of subgraphs whose rank = rank(G)

$\mathrm{eval}\left(S\,\left\{x=0\,y=1\right\}\right)$

$38$

The number of maximum spanning forests

$\mathrm{eval}\left(S\,\left\{x=0\,y=0\right\}\right)$

$16$

$P≔\mathrm{Graph}\left(\left\{\left\{1\,2\right\}\,\left\{2\,3\right\}\right\}\right)$

$P≔\mathrm{Graph\; 7:\; an\; undirected\; graph\; with\; 3\; vertices\; and\; 2\; edges}$

$R≔\mathrm{ReliabilityPolynomial}\left(P\,p\right)$

$R≔{\left(1-p\right)}^2$

$\mathrm{AcyclicPolynomial}\left(P\,p\right)$

$1$

The reliability of a connected network should increase if we add an edge. The difference Q-P below is positive for $0<p<1$.

$\mathrm{AddEdge}\left(P\&comma;\left\{1\&comma;3\right\}\right)$

$\mathrm{Graph\; 7:\; an\; undirected\; graph\; with\; 3\; vertices\; and\; 3\; edges}$

$Q≔\mathrm{ReliabilityPolynomial}\left(P\&comma;p\right)$

$Q≔\left(2p+1\right){\left(1-p\right)}^2$

$\mathrm{factor}\left(Q-R\right)$

$2{\left(-1+p\right)}^{2}p$

$\mathrm{expand}\left(\mathrm{AcyclicPolynomial}\left(P\&comma;p\right)\right)$

$-p^3+1$

Multiple edges may be specified as edge weights.

$G≔\mathrm{Graph}\left(\left\{\left[\left\{1\&comma;2\right\}\&comma;2\right]\&comma;\left[\left\{1\&comma;3\right\}\&comma;1\right]\&comma;\left[\left\{2\&comma;3\right\}\&comma;1\right]\right\}\right)$

$G≔\mathrm{Graph\; 8:\; an\; undirected\; weighted\; graph\; with\; 3\; vertices\; and\; 3\; edges}$

$\mathrm{ReliabilityPolynomial}\left(G\&comma;p\right)$

$\left(2p^2+2p+1\right){\left(1-p\right)}^2$

The following graph represents the Arpanet, the early internet, in late 1970.

$V≔\left[\mathrm{MIT}\&comma;\mathrm{LINCOLN}\&comma;\mathrm{CASE}\&comma;\mathrm{CMU}\&comma;\mathrm{HARVARD}\&comma;\mathrm{BBN}\&comma;\mathrm{UCSB}\&comma;\mathrm{UCLA}\&comma;\mathrm{STANFORD}\&comma;\mathrm{SRI}\&comma;\mathrm{RAND}\&comma;\mathrm{UTAH}\&comma;\mathrm{SDC}\right]\&colon;$

$\mathrm{Arpanet}≔\mathrm{Graph}\left(V\&comma;\mathrm{Trail}\left(\mathrm{UCSB}\&comma;\mathrm{UCLA}\&comma;\mathrm{RAND}\&comma;\mathrm{SDC}\&comma;\mathrm{UTAH}\&comma;\mathrm{SRI}\&comma;\mathrm{STANFORD}\&comma;\mathrm{UCLA}\&comma;\mathrm{SRI}\&comma;\mathrm{UCSB}\right)\&comma;\left\{\left\{\mathrm{BBN}\&comma;\mathrm{RAND}\right\}\&comma;\left\{\mathrm{MIT}\&comma;\mathrm{UTAH}\right\}\right\}\&comma;\mathrm{Trail}\left(\mathrm{MIT}\&comma;\mathrm{LINCOLN}\&comma;\mathrm{CASE}\&comma;\mathrm{CMU}\&comma;\mathrm{HARVARD}\&comma;\mathrm{BBN}\&comma;\mathrm{MIT}\right)\right)$

$\mathrm{Arpanet}≔\mathrm{Graph\; 9:\; an\; undirected\; graph\; with\; 13\; vertices\; and\; 17\; edges}$

$\mathrm{SetVertexPositions}\left(\mathrm{Arpanet}\&comma;\left[\left[1.0\&comma;1.0\right]\&comma;\left[0.9\&comma;1.2\right]\&comma;\left[0.5\&comma;1.1\right]\&comma;\left[0.6\&comma;0.8\right]\&comma;\left[1.0\&comma;0.6\right]\&comma;\left[1.0\&comma;0.8\right]\&comma;\left[-1.1\&comma;0.1\right]\&comma;\left[-0.8\&comma;0.3\right]\&comma;\left[-0.6\&comma;0.5\right]\&comma;\left[-0.8\&comma;0.7\right]\&comma;\left[-0.8\&comma;-0.1\right]\&comma;\left[-0.3\&comma;0.9\right]\&comma;\left[-0.5\&comma;0.2\right]\right]\right)$

$\mathrm{DrawGraph}\left(\mathrm{Arpanet}\right)$

$R≔\mathrm{ReliabilityPolynomial}\left(\mathrm{Arpanet}\&comma;p\right)$

$R≔\left(280p^5+310p^4+186p^3+63p^2+12p+1\right){\left(1-p\right)}^{12}$

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≔\mathrm{AddEdge}\left(\mathrm{Arpanet}\&comma;\left\{\mathrm{CMU}\&comma;\mathrm{STANFORD}\right\}\&comma;\mathrm{inplace}=\mathrm{false}\right)$

$H≔\mathrm{Graph\; 10:\; an\; undirected\; graph\; with\; 13\; vertices\; and\; 18\; edges}$

$S≔\mathrm{ReliabilityPolynomial}\left(H\&comma;p\right)$

$S≔\left(976p^6+1118p^5+703p^4+276p^3+72p^2+12p+1\right){\left(1-p\right)}^{12}$

We can compare the reliability polynomials visually for $0\le p\le 1$ then compute the improvement by computing the area of the enclosed curves as an integral.

$\mathrm{plot}\left(\left[R\&comma;S\right]\&comma;p=0..1\&comma;\mathrm{color}=\left[\mathrm{blue}\&comma;\mathrm{red}\right]\right)$

$\mathrm{improvement}≔\mathrm{int}\left(S-R\&comma;p=0..1\right)$

$\mathrm{improvement}≔\frac{443879}{10581480}$

$\mathrm{evalf}\left(\mathrm{improvement}\right)$

$0.04194866881$