|
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
|
|
We can verify the recurrence relation
|
|
ChromaticPolynomial
|
|
•
|
This must be zero since the Petersen graph is not 2-colorable
|
•
|
We can verify the recurrence relation
|
•
|
We can convince ourselves that this graph needs 10 colors and can be colored 10! ways with 10 colors
|
|
|
FlowPolynomial and RankPolynomial
|
|
•
|
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
|
|
•
|
The reliability of a connected network should increase if we add an edge. The difference Q-P below is positive for .
|
•
|
Multiple edges may be specified as edge weights.
|
•
|
The following graph represents the Arpanet, the early internet, in late 1970.
|
•
|
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.
|
•
|
We can compare the reliability polynomials visually for then compute the improvement by computing the area of the enclosed curves as an integral.
|
|
|
|
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.
|
|
|
|