主題
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.tw/ReliabilityPolynomial.html

主題分類