主题
Search

可靠性多项式

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

设 G 是一个图，假设 G 的每条边都以固定的概率 0<=p<=1 独立删除。那么，G 的任何连通分量都不因此断开连接的概率，记为 C(p)，被称为 G 的可靠性多项式。

可靠性多项式可以直接用给定图的 Tutte 多项式表示为

C(p)=(1-p)^(n-c)p^(m-n+c)T(1,p^(-1)),
(1)

其中 n 是顶点数，m 是边数，c 是连通分量的数量 (Godsil 和 Royle 2001, p. 358; 错误已更正)。这等价于以下定义

C(p)=sum_(j=1)^ma_j(1-p)^jp^(m-j),
(2)

其中 a_j 是原始图 G 中恰好有 j 条边的子图的数量，并且对于这些子图，G 中的每对节点都通过位于子图 S 中的边路径连接（即，S 是连通的且 |S|=n），这是 Page 和 Perry (1994) 在进行 p->1-p 更改后的定义。

例如，Petersen 图的可靠性多项式由下式给出

C(p)=(1-p)^9(704p^6+696p^5+390p^4+155p^3+45p^2+9p+1)
(3)

(Godsil 和 Royle 2001, p. 355)。

下表总结了具有闭式可靠性多项式的简单图类。其中，t=sqrt(1+2x+9x^2)。

图C(p)
香蕉树(x-1)^(nk)
圈图 C_n(1-p)^(n-1)[1+(n-1)p]
齿轮图((p-1)^(2n)[(-t+3p+1)^n+(t+3p+1)^n-2^(n+1)p^n])/(2^n)
梯形图((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]
平底锅图(1-p)^n[1+(n-1)p]
路径图 P_n(1-p)^(n-1)
星图 S_n(1-p)^(n-1)
日晒图 C_n circledot K_1(1-p)^(2n-1)[(1+(n-1)p]

下表总结了一些简单图类的可靠性多项式递推关系。

图阶数递推关系
圈图 C_n2p_n(x)=-2(x-1)p_(n-1)(x)-(x-1)^2p_(n-2)(x)
齿轮图3p_n(x)=(4x+1)(x-1)^2p_(n-1)(x)-x(3x+2)(x-1)^4p_(n-2)(x)+x^2(x-1)^6p_(n-3)(x)
梯形图 L_n2p_n(x)=(3x+1)p_(n-1)(x)-xp_(n-2)(x)
平底锅图2p_n(x)=-2(x-1)p_(n-1)-(x-1)^2p_(n-2)(x)
路径图 P_n1p_n(x)=(1-x)p_(n-1)(x)
星图 S_n1p_n(x)=(1-x)p_(n-1)(x)
日晒图 C_n circledot K_12p_n(x)=2(x-1)^2p_(n-1)(x)-(x-1)^4p_(n-2)(x)
轮图 W_n3p_n(x)=-(3x+1)(x-1)p_(n-1)(x)-2x(x+1)(x-1)^2p_(n-2)(x)-x^2(x-1)^3p_(n-3)(x)

非同构图不一定具有不同的可靠性多项式。下表总结了一些同可靠性图。

n可靠性多项式图
4-(-1+x)^3爪图, 路径图 P_4
5(-1+x)^4叉图, 路径图 P_5, 星图 S_5
5(-1+x)^4(1+2x)牛图, 板球图, (3,2)-蝌蚪图
5(-1+x)^4(1+3x+4x^2)飞镖图, 风筝图

另请参阅

秩多项式, Tutte 多项式

使用 探索

参考文献

Brown, J. I. 和 Colbourn, C. J. "可靠性多项式的根。" SIAM J. Disc. Math. 5, 571-585, 1992.Chari, M. 和 Colbourn, C. "可靠性多项式：综述。" J. Combin. Inform. System Sci. 22, 177-193, 1997.Colbourn, C. J. 网络可靠性的组合数学。 New York: Oxford University Press, 1987.Ellis-Monaghan, J. A. 和 Merino, C. "图多项式及其应用 I：Tutte 多项式。" 2008 年 6 月 28 日。 http://arxiv.org/abs/0803.3079.Godsil, C. 和 Royle, G. 代数图论。 New York: Springer-Verlag, pp. 354-358, 2001.Page, L. B. 和 Perry, J. E. "网络中的可靠性多项式和链路重要性。" IEE Trans. Reliability 43, 51-58, 1994.Royle, G.; Alan, A. D.; 和 Sokal, D. "关于可靠性多项式零点的 Brown-Colbourn 猜想是错误的。" J. Combin. Th., Ser. B 91, 345-360, 2004.

在 中被引用

可靠性多项式

请引用为

Weisstein, Eric W. “可靠性多项式。” 来自 Web 资源。 https://mathworld.net.cn/ReliabilityPolynomial.html

主题分类