AcyclicPolynomial - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


GraphTheory

  

TuttePolynomial

  

compute Tutte polynomial

  

ChromaticPolynomial

  

compute chromatic polynomial

  

FlowPolynomial

  

compute flow polynomial

  

RankPolynomial

  

compute rank polynomial

  

AcyclicPolynomial

  

compute acyclic polynomial

  

ReliabilityPolynomial

  

compute reliability polynomial

 

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

TuttePolynomial

(1)

(2)

(3)

We can verify the recurrence relation

(4)

(5)

(6)

(7)

(8)

(9)

ChromaticPolynomial

(10)
• 

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

(11)

(12)
• 

We can verify the recurrence relation

(13)

(14)
• 

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

(15)

(16)

(17)

FlowPolynomial and RankPolynomial

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

(27)
• 

The number of subgraphs

(28)
• 

The number of acyclic subgraphs

(29)
• 

The number of subgraphs whose rank = rank(G)

(30)
• 

The number of maximum spanning forests

(31)

ReliabilityPolynomial and AcyclicPolynomial

(32)

(33)

(34)
• 

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

(35)

(36)

(37)

(38)
• 

Multiple edges may be specified as edge weights.

(39)

(40)
• 

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

(41)

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

(43)

(44)
• 

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

(45)

(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

 


Download Help Document