GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

TuttePolynomial

  

ChromaticPolynomial

  

FlowPolynomial

  

RankPolynomial

  

AcyclicPolynomial

  

ReliabilityPolynomial

 

Calling Sequence

Parameters

Description

Examples

References

Compatibility

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 0p1 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 0p1 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 [2] and [4] Monagan in the References section.

Examples

withGraphTheory:

withSpecialGraphs:

withRandomGraphs:

TuttePolynomial

GCompleteGraph4

GGraph 1: an undirected unweighted graph with 4 vertices and 6 edge(s)

(1)

TuttePolynomialG,x,y

x3+y3+3x2+4xy+3y2+2x+2y

(2)

TuttePolynomialG,x,1

x3+3x2+6x+6

(3)

We can verify the recurrence relation

GPetersenGraph

GGraph 2: an undirected unweighted graph with 10 vertices and 15 edge(s)

(4)

fTuttePolynomialG,x,y

fx9+6x8+21x7+56x6+12x5y+y6+114x5+70x4y+30x3y2+15x2y3+10xy4+9y5+170x4+170x3y+105x2y2+65xy3+35y4+180x3+240x2y+171xy2+75y3+120x2+168xy+84y2+36x+36y

(5)

eEdgesG1

e1,2

(6)

GminuseDeleteEdgeG,e,inplace=false

GminuseGraph 3: an undirected unweighted graph with 10 vertices and 14 edge(s)

(7)

GcontracteContractG,e,inplace=false

GcontracteGraph 4: an undirected unweighted graph with 9 vertices and 14 edge(s)

(8)

expandfTuttePolynomialGminuse,x,y+TuttePolynomialGcontracte,x,y

0

(9)

ChromaticPolynomial

PChromaticPolynomialG,x

Pxx1x2x712x6+67x5230x4+529x3814x2+775x352

(10)
• 

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

evalP,x=2

0

(11)

evalP,x=3

120

(12)
• 

We can verify the recurrence relation

expandPChromaticPolynomialGminuse,xChromaticPolynomialGcontracte,x

0

(13)

KCompleteGraph10

KGraph 5: an undirected unweighted graph with 10 vertices and 45 edge(s)

(14)
• 

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

ChromaticPolynomialK,t

tt1t2t3t4t5t6t7t8t9

(15)

ChromaticPolynomialK,1010!

0

(16)

ChromaticPolynomialRandomTree100,t

tt199

(17)

FlowPolynomial and RankPolynomial

QFlowPolynomialG,x

Qx615x5+95x4325x3+624x2620x+240

(18)

evalQ,x=4

0

(19)

evalQ,x=5

240

(20)

TTuttePolynomialG,0,1x

Tx615x5+95x4325x3+624x2620x+240

(21)

nNumberOfVerticesG

n10

(22)

mNumberOfEdgesG

m15

(23)

knopsConnectedComponentsG

k1

(24)

expandQ1mn+kT

0

(25)

K4CompleteGraph4

K4Graph 6: an undirected unweighted graph with 4 vertices and 6 edge(s)

(26)

SRankPolynomialK4,x,y

Sx3+y3+6x2+4xy+6y2+15x+15y+16

(27)
• 

The number of subgraphs

evalS,x=1,y=1

64

(28)
• 

The number of acyclic subgraphs

evalS,x=1,y=0

38

(29)
• 

The number of subgraphs whose rank = rank(G)

evalS,x=0,y=1

38

(30)
• 

The number of maximum spanning forests

evalS,x=0,y=0

16

(31)

ReliabilityPolynomial and AcyclicPolynomial

PGraph1,2,2,3

PGraph 7: an undirected unweighted graph with 3 vertices and 2 edge(s)

(32)

RReliabilityPolynomialP,p

R1p2

(33)

AcyclicPolynomialP,p

1

(34)
• 

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

AddEdgeP&comma;1&comma;3

Graph 7: an undirected unweighted graph with 3 vertices and 3 edge(s)

(35)

QReliabilityPolynomialP&comma;p

Q2p+11p2

(36)

factorQR

21+p2p

(37)

expandAcyclicPolynomialP&comma;p

p3+1

(38)
• 

Multiple edges may be specified as edge weights.

GGraph1&comma;2&comma;2&comma;1&comma;3&comma;1&comma;2&comma;3&comma;1

GGraph 8: an undirected weighted graph with 3 vertices and 3 edge(s)

(39)

ReliabilityPolynomialG&comma;p

2p2+2p+11p2

(40)
• 

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

VMIT&comma;LINCOLN&comma;CASE&comma;CMU&comma;HARVARD&comma;BBN&comma;UCSB&comma;UCLA&comma;STANFORD&comma;SRI&comma;RAND&comma;UTAH&comma;SDC&colon;

ArpanetGraphV&comma;TrailUCSB&comma;UCLA&comma;RAND&comma;SDC&comma;UTAH&comma;SRI&comma;STANFORD&comma;UCLA&comma;SRI&comma;UCSB&comma;BBN&comma;RAND&comma;MIT&comma;UTAH&comma;TrailMIT&comma;LINCOLN&comma;CASE&comma;CMU&comma;HARVARD&comma;BBN&comma;MIT

ArpanetGraph 9: an undirected unweighted graph with 13 vertices and 17 edge(s)

(41)

SetVertexPositionsArpanet&comma;1.0&comma;1.0&comma;0.9&comma;1.2&comma;0.5&comma;1.1&comma;0.6&comma;0.8&comma;1.0&comma;0.6&comma;1.0&comma;0.8&comma;1.1&comma;0.1&comma;0.8&comma;0.3&comma;0.6&comma;0.5&comma;0.8&comma;0.7&comma;0.8&comma;0.1&comma;0.3&comma;0.9&comma;0.5&comma;0.2

DrawGraphArpanet

RReliabilityPolynomialArpanet&comma;p

R280p5+310p4+186p3+63p2+12p+11p12

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

HAddEdgeArpanet&comma;CMU&comma;STANFORD&comma;inplace=false

HGraph 10: an undirected unweighted graph with 13 vertices and 18 edge(s)

(43)

SReliabilityPolynomialH&comma;p

S976p6+1118p5+703p4+276p3+72p2+12p+11p12

(44)
• 

We can compare the reliability polynomials visually for 0p1 then compute the improvement by computing the area of the enclosed curves as an integral.

plotR&comma;S&comma;p=0..1&comma;color=blue&comma;red

improvementintSR&comma;p=0..1

improvement44387910581480

(45)

evalfimprovement

0.04194866881

(46)

References

  

[1]  Bollobás, Béla. Modern Graph Theory. Graduate Texts in Mathematics, 184, Springer-Verlag, New York, 1998.

  

[2] Farr, Khatarinejad, Khodadad, and Monagan.  A Graph Theory Package for Maple. Proceedings of the 2005 Maple Conference, Maplesoft, July 2005: 260-271.

  

[3] Haggard, Pearce, and Royle. "Computing Tutte Polynomials." TOMS. Vol. 37(24). (2010): 1-17.

  

[4] Monagan.  "A new edge selection heuristic for computing Tutte polynomials." Proceedings of FPSAC 2012.

Compatibility

• 

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

• 

For more information on Maple 17 changes, see Updates in Maple 17.

See Also

ChromaticNumber

Contract

IsAcyclic

IsVertexColorable