Reliability Polynomial
المؤلف:
Brown, J. I. and Colbourn, C. J.
المصدر:
"Roots of the Reliability Polynomial." SIAM J. Disc. Math. 5
الجزء والصفحة:
...
20-4-2022
3734
Reliability Polynomial
Let 
be a graph, and suppose each edge of 
is independently deleted with fixed probability 
. Then the probability that no connected component of 
is disconnected as a result, denoted 
is known as the reliability polynomial of 
.
The reliability polynomial is directly expressible in terms of the Tutte polynomial of a given graph as
 |
(1)
|
where 
is the vertex count, 
the edge count, and 
the number of connected components (Godsil and Royle 2001, p. 358; error corrected). This is equivalent to the definition
 |
(2)
|
where 
is the number of subgraphs of the original graph 
having exactly 
edges and for which every pair of nodes in 
is joined by a path of edges lying in subgraph 
(i.e., 
is connected and 
), which is the definition due to Page and Perry (1994) after making the change 
.
For example, the reliability polynomial of the Petersen graph is given by
 |
(3)
|
(Godsil and Royle 2001, p. 355).
The following table summarizes simple classes of graphs having closed-form reliability polynomials. Here, 
.
| graph |
 |
| banana tree |
 |
cycle graph  |
![(1-p)^(n-1)[1+(n-1)p]](https://mathworld.wolfram.com/images/equations/ReliabilityPolynomial/Inline22.svg) |
| gear graph |
![((p-1)^(2n)[(-t+3p+1)^n+(t+3p+1)^n-2^(n+1)p^n])/(2^n)](https://mathworld.wolfram.com/images/equations/ReliabilityPolynomial/Inline23.svg) |
| ladder graph |
![((p-1)^(2n-1))/(2^nsqrt(p(9p+2)+1))[(3p-sqrt(p(9p+2)+1)+1)^n-(3p+sqrt(p(9p+2)+1)+1)^n]](https://mathworld.wolfram.com/images/equations/ReliabilityPolynomial/Inline24.svg) |
| pan graph |
![(1-p)^n[1+(n-1)p]](https://mathworld.wolfram.com/images/equations/ReliabilityPolynomial/Inline25.svg) |
path graph  |
 |
star graph  |
 |
sunlet graph  |
![(1-p)^(2n-1)[(1+(n-1)p]](https://mathworld.wolfram.com/images/equations/ReliabilityPolynomial/Inline31.svg) |
The following table summarizes the recurrence relations for reliability polynomials for some simple classes of graphs.
| graph |
order |
recurrence |
cycle graph  |
2 |
 |
| gear graph |
3 |
 |
ladder graph  |
2 |
 |
| pan graph |
2 |
 |
path graph  |
1 |
 |
star graph  |
1 |
 |
sunlet graph  |
2 |
 |
wheel graph  |
3 |
 |
Nonisomorphic graphs do not necessarily have distinct reliability polynomials. The following table summarizes some co-reliability graphs.
 |
reliability polynomial |
graphs |
| 4 |
 |
claw graph, path graph  |
| 5 |
 |
fork graph, path graph  , star graph  |
| 5 |
 |
bull graph, cricket graph,  -tadpole graph |
| 5 |
 |
dart graph, kite graph |
REFERENCES
Brown, J. I. and Colbourn, C. J. "Roots of the Reliability Polynomial." SIAM J. Disc. Math. 5, 571-585, 1992.
Chari, M. and Colbourn, C. "Reliability Polynomials: A Survey." J. Combin. Inform. System Sci. 22, 177-193, 1997.
Colbourn, C. J. The Combinatorics of Network Reliability. New York: Oxford University Press, 1987.
Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications I: The Tutte Polynomial." 28 Jun 2008. http://arxiv.org/abs/0803.3079.
Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, pp. 354-358, 2001.
Page, L. B. and Perry, J. E. "Reliability Polynomials and Link Importance in Networks." IEE Trans. Reliability 43, 51-58, 1994.
Royle, G.; Alan, A. D.; and Sokal, D. "The Brown-Colbourn Conjecture on Zeros of Reliability Polynomials Is False." J. Combin. Th., Ser. B 91, 345-360, 2004.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
