 GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/TuttePolynomial

GraphTheory

 TuttePolynomial
 ChromaticPolynomial
 FlowPolynomial
 RankPolynomial
 AcyclicPolynomial
 ReliabilityPolynomial

 Calling Sequence TuttePolynomial(H, x, y) ChromaticPolynomial(G, t) FlowPolynomial(G, x) RankPolynomial(G, x, y) AcyclicPolynomial(G, p) ReliabilityPolynomial(H, p)

Parameters

 H - undirected graph G - undirected unweighted graph t,x,y,p - variables or values

Description

TuttePolynomial

 • 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.

ChromaticPolynomial

 • 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\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)

Notes

 • 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.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $\mathrm{with}\left(\mathrm{RandomGraphs}\right):$

TuttePolynomial

 > $G≔\mathrm{CompleteGraph}\left(4\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 4 vertices and 6 edge\left(s\right)}}$ (1)
 > $\mathrm{TuttePolynomial}\left(G,'x','y'\right)$
 ${{x}}^{{3}}{+}{{y}}^{{3}}{+}{3}{}{{x}}^{{2}}{+}{4}{}{x}{}{y}{+}{3}{}{{y}}^{{2}}{+}{2}{}{x}{+}{2}{}{y}$ (2)
 > $\mathrm{TuttePolynomial}\left(G,'x',1\right)$
 ${{x}}^{{3}}{+}{3}{}{{x}}^{{2}}{+}{6}{}{x}{+}{6}$ (3)

We can verify the recurrence relation

 > $G≔\mathrm{PetersenGraph}\left(\right)$
 ${G}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 10 vertices and 15 edge\left(s\right)}}$ (4)
 > $f≔\mathrm{TuttePolynomial}\left(G,'x','y'\right)$
 ${f}{≔}{{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}$ (5)
 > $e≔\mathrm{Edges}\left(G\right)\left[1\right]$
 ${e}{≔}\left\{{1}{,}{2}\right\}$ (6)
 > $\mathrm{Gminuse}≔\mathrm{DeleteEdge}\left(G,e,'\mathrm{inplace}'=\mathrm{false}\right)$
 ${\mathrm{Gminuse}}{≔}{\mathrm{Graph 3: an undirected unweighted graph with 10 vertices and 14 edge\left(s\right)}}$ (7)
 > $\mathrm{Gcontracte}≔\mathrm{Contract}\left(G,e,'\mathrm{inplace}'=\mathrm{false}\right)$
 ${\mathrm{Gcontracte}}{≔}{\mathrm{Graph 4: an undirected unweighted graph with 9 vertices and 14 edge\left(s\right)}}$ (8)
 > $\mathrm{expand}\left(f-\left(\mathrm{TuttePolynomial}\left(\mathrm{Gminuse},'x','y'\right)+\mathrm{TuttePolynomial}\left(\mathrm{Gcontracte},'x','y'\right)\right)\right)$
 ${0}$ (9)

ChromaticPolynomial

 > $P≔\mathrm{ChromaticPolynomial}\left(G,'x'\right)$
 ${P}{≔}{x}{}\left({x}{-}{1}\right){}\left({x}{-}{2}\right){}\left({{x}}^{{7}}{-}{12}{}{{x}}^{{6}}{+}{67}{}{{x}}^{{5}}{-}{230}{}{{x}}^{{4}}{+}{529}{}{{x}}^{{3}}{-}{814}{}{{x}}^{{2}}{+}{775}{}{x}{-}{352}\right)$ (10)
 • This must be zero since the Petersen graph is not 2-colorable
 > $\mathrm{eval}\left(P,x=2\right)$
 ${0}$ (11)
 > $\mathrm{eval}\left(P,x=3\right)$
 ${120}$ (12)
 • 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}$ (13)
 > $K≔\mathrm{CompleteGraph}\left(10\right)$
 ${K}{≔}{\mathrm{Graph 5: an undirected unweighted graph with 10 vertices and 45 edge\left(s\right)}}$ (14)
 • 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)$ (15)
 > $\mathrm{ChromaticPolynomial}\left(K,10\right)-10!$
 ${0}$ (16)
 > $\mathrm{ChromaticPolynomial}\left(\mathrm{RandomTree}\left(100\right),'t'\right)$
 ${t}{}{\left({t}{-}{1}\right)}^{{99}}$ (17)

FlowPolynomial and RankPolynomial

 > $Q≔\mathrm{FlowPolynomial}\left(G,x\right)$
 ${Q}{≔}{{x}}^{{6}}{-}{15}{}{{x}}^{{5}}{+}{95}{}{{x}}^{{4}}{-}{325}{}{{x}}^{{3}}{+}{624}{}{{x}}^{{2}}{-}{620}{}{x}{+}{240}$ (18)
 > $\mathrm{eval}\left(Q,x=4\right)$
 ${0}$ (19)
 > $\mathrm{eval}\left(Q,x=5\right)$
 ${240}$ (20)
 > $T≔\mathrm{TuttePolynomial}\left(G,0,1-x\right)$
 ${T}{≔}{{x}}^{{6}}{-}{15}{}{{x}}^{{5}}{+}{95}{}{{x}}^{{4}}{-}{325}{}{{x}}^{{3}}{+}{624}{}{{x}}^{{2}}{-}{620}{}{x}{+}{240}$ (21)
 > $n≔\mathrm{NumberOfVertices}\left(G\right)$
 ${n}{≔}{10}$ (22)
 > $m≔\mathrm{NumberOfEdges}\left(G\right)$
 ${m}{≔}{15}$ (23)
 > $k≔\mathrm{nops}\left(\mathrm{ConnectedComponents}\left(G\right)\right)$
 ${k}{≔}{1}$ (24)
 > $\mathrm{expand}\left(Q-{\left(-1\right)}^{m-n+k}T\right)$
 ${0}$ (25)
 > $\mathrm{K4}≔\mathrm{CompleteGraph}\left(4\right)$
 ${\mathrm{K4}}{≔}{\mathrm{Graph 6: an undirected unweighted graph with 4 vertices and 6 edge\left(s\right)}}$ (26)
 > $S≔\mathrm{RankPolynomial}\left(\mathrm{K4},x,y\right)$
 ${S}{≔}{{x}}^{{3}}{+}{{y}}^{{3}}{+}{6}{}{{x}}^{{2}}{+}{4}{}{x}{}{y}{+}{6}{}{{y}}^{{2}}{+}{15}{}{x}{+}{15}{}{y}{+}{16}$ (27)
 • The number of subgraphs
 > $\mathrm{eval}\left(S,\left\{x=1,y=1\right\}\right)$
 ${64}$ (28)
 • The number of acyclic subgraphs
 > $\mathrm{eval}\left(S,\left\{x=1,y=0\right\}\right)$
 ${38}$ (29)
 • The number of subgraphs whose rank = rank(G)
 > $\mathrm{eval}\left(S,\left\{x=0,y=1\right\}\right)$
 ${38}$ (30)
 • The number of maximum spanning forests
 > $\mathrm{eval}\left(S,\left\{x=0,y=0\right\}\right)$
 ${16}$ (31)

ReliabilityPolynomial and AcyclicPolynomial

 > $P≔\mathrm{Graph}\left(\left\{\left\{1,2\right\},\left\{2,3\right\}\right\}\right)$
 ${P}{≔}{\mathrm{Graph 7: an undirected unweighted graph with 3 vertices and 2 edge\left(s\right)}}$ (32)
 > $R≔\mathrm{ReliabilityPolynomial}\left(P,p\right)$
 ${R}{≔}{\left({1}{-}{p}\right)}^{{2}}$ (33)
 > $\mathrm{AcyclicPolynomial}\left(P,p\right)$
 ${1}$ (34)
 • The reliability of a connected network should increase if we add an edge. The difference Q-P below is positive for $0.
 > $\mathrm{AddEdge}\left(P,\left\{1,3\right\}\right)$
 ${\mathrm{Graph 7: an undirected unweighted graph with 3 vertices and 3 edge\left(s\right)}}$ (35)
 > $Q≔\mathrm{ReliabilityPolynomial}\left(P,p\right)$
 ${Q}{≔}\left({2}{}{p}{+}{1}\right){}{\left({1}{-}{p}\right)}^{{2}}$ (36)
 > $\mathrm{factor}\left(Q-R\right)$
 ${2}{}{\left({-}{1}{+}{p}\right)}^{{2}}{}{p}$ (37)
 > $\mathrm{expand}\left(\mathrm{AcyclicPolynomial}\left(P,p\right)\right)$
 ${-}{{p}}^{{3}}{+}{1}$ (38)
 • Multiple edges may be specified as edge weights.
 > $G≔\mathrm{Graph}\left(\left\{\left[\left\{1,2\right\},2\right],\left[\left\{1,3\right\},1\right],\left[\left\{2,3\right\},1\right]\right\}\right)$
 ${G}{≔}{\mathrm{Graph 8: an undirected weighted graph with 3 vertices and 3 edge\left(s\right)}}$ (39)
 > $\mathrm{ReliabilityPolynomial}\left(G,p\right)$
 $\left({2}{}{{p}}^{{2}}{+}{2}{}{p}{+}{1}\right){}{\left({1}{-}{p}\right)}^{{2}}$ (40)
 • The following graph represents the Arpanet, the early internet, in late 1970.
 > $V≔\left[\mathrm{MIT},\mathrm{LINCOLN},\mathrm{CASE},\mathrm{CMU},\mathrm{HARVARD},\mathrm{BBN},\mathrm{UCSB},\mathrm{UCLA},\mathrm{STANFORD},\mathrm{SRI},\mathrm{RAND},\mathrm{UTAH},\mathrm{SDC}\right]:$
 > $\mathrm{Arpanet}≔\mathrm{Graph}\left(V,\mathrm{Trail}\left(\mathrm{UCSB},\mathrm{UCLA},\mathrm{RAND},\mathrm{SDC},\mathrm{UTAH},\mathrm{SRI},\mathrm{STANFORD},\mathrm{UCLA},\mathrm{SRI},\mathrm{UCSB}\right),\left\{\left\{\mathrm{BBN},\mathrm{RAND}\right\},\left\{\mathrm{MIT},\mathrm{UTAH}\right\}\right\},\mathrm{Trail}\left(\mathrm{MIT},\mathrm{LINCOLN},\mathrm{CASE},\mathrm{CMU},\mathrm{HARVARD},\mathrm{BBN},\mathrm{MIT}\right)\right)$
 ${\mathrm{Arpanet}}{≔}{\mathrm{Graph 9: an undirected unweighted graph with 13 vertices and 17 edge\left(s\right)}}$ (41)
 > $\mathrm{SetVertexPositions}\left(\mathrm{Arpanet},\left[\left[1.0,1.0\right],\left[0.9,1.2\right],\left[0.5,1.1\right],\left[0.6,0.8\right],\left[1.0,0.6\right],\left[1.0,0.8\right],\left[-1.1,0.1\right],\left[-0.8,0.3\right],\left[-0.6,0.5\right],\left[-0.8,0.7\right],\left[-0.8,-0.1\right],\left[-0.3,0.9\right],\left[-0.5,0.2\right]\right]\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{Arpanet}\right)$ > $R≔\mathrm{ReliabilityPolynomial}\left(\mathrm{Arpanet},p\right)$
 ${R}{≔}\left({280}{}{{p}}^{{5}}{+}{310}{}{{p}}^{{4}}{+}{186}{}{{p}}^{{3}}{+}{63}{}{{p}}^{{2}}{+}{12}{}{p}{+}{1}\right){}{\left({1}{-}{p}\right)}^{{12}}$ (42)
 • 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},\left\{\mathrm{CMU},\mathrm{STANFORD}\right\},\mathrm{inplace}=\mathrm{false}\right)$
 ${H}{≔}{\mathrm{Graph 10: an undirected unweighted graph with 13 vertices and 18 edge\left(s\right)}}$ (43)
 > $S≔\mathrm{ReliabilityPolynomial}\left(H,p\right)$
 ${S}{≔}\left({976}{}{{p}}^{{6}}{+}{1118}{}{{p}}^{{5}}{+}{703}{}{{p}}^{{4}}{+}{276}{}{{p}}^{{3}}{+}{72}{}{{p}}^{{2}}{+}{12}{}{p}{+}{1}\right){}{\left({1}{-}{p}\right)}^{{12}}$ (44)
 • 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,S\right],p=0..1,\mathrm{color}=\left[\mathrm{blue},\mathrm{red}\right]\right)$ > $\mathrm{improvement}≔\mathrm{int}\left(S-R,p=0..1\right)$
 ${\mathrm{improvement}}{≔}\frac{{443879}}{{10581480}}$ (45)
 > $\mathrm{evalf}\left(\mathrm{improvement}\right)$
 ${0.04194866881}$ (46)

References

   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.

Compatibility

 • The GraphTheory[ReliabilityPolynomial] command was introduced in Maple 17.