劉 瑩，唐曉清

（1.邵陽學(xué)院理學(xué)與信息科學(xué)系，湖南邵陽422000；2.上海立信會計(jì)學(xué)院數(shù)學(xué)與信息學(xué)院，上海201620）

正則q－樹根圖的可靠性研究

劉 瑩1，唐曉清2

（1.邵陽學(xué)院理學(xué)與信息科學(xué)系，湖南邵陽422000；2.上海立信會計(jì)學(xué)院數(shù)學(xué)與信息學(xué)院，上海201620）

對根圖的頂點(diǎn)的幸存概率進(jìn)行了期望值研究，得出一個(gè)重要的定理，即減－縮邊公式.由此，得到一些特殊根圖的期望值計(jì)算公式及正則q－樹根圖和正則q－樹整子根圖的期望值計(jì)算公式.討論了根圖的均值和方差的后驗(yàn)計(jì)算公式，以及整體優(yōu)化的思路.

根圖；期望值；正則q－樹根圖；正則q－樹整子根圖；均值－方差優(yōu)化

生活中，很多網(wǎng)絡(luò)可以看做一個(gè)根圖.比如，供電網(wǎng)絡(luò)、供水網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)、有線電視網(wǎng)絡(luò)，等等.它們都有一個(gè)共同的特點(diǎn)，那就是終端用戶可以看做是圖的頂點(diǎn)，而連接它們的管道或線路，可以看做是圖的線，像電廠、發(fā)射臺等功能中心，就是這個(gè)圖的根.并且，一旦某頂點(diǎn)和根不連通，此頂點(diǎn)就失效了.根圖的可靠性，或者說恢復(fù)力，是一個(gè)很重要的研究目標(biāo).人們首先假設(shè)有關(guān)終端用戶設(shè)備是以一定的概率在災(zāi)難后幸存，這些設(shè)備在災(zāi)難后幸存的期望值，就是根圖可靠性的一個(gè)重要指標(biāo).因此該研究的重要性不言而喻.目前對于根圖的邊的幸存概率p，M.Aivaliotis和A.Bailey進(jìn)行了期望值研究，得到一些成果.［1－2］但對根圖的頂點(diǎn)幸存概率期望值的研究還未見報(bào)道.本文對根圖的頂點(diǎn)幸存概率期望值進(jìn)行了研究，得出一些結(jié)論.

1 定義及減－縮邊公式

1.1定義及定理

設(shè)圖G是一個(gè)連通根圖，根頂點(diǎn)表示為＊，并且，集合E是邊集，集合V是頂點(diǎn)集，子集A?V，r（A）表示包含根的子圖A中和根連通的邊的數(shù)目.設(shè)圖的每一個(gè)頂點(diǎn)（根頂點(diǎn)除外）在災(zāi)難事件發(fā)生后的幸存概率是p，并且任何兩個(gè)頂點(diǎn)是否幸存是獨(dú)立的.在這里，設(shè)邊總是不失效的.但是，在一個(gè)連接根的通路中，如果前面的頂點(diǎn)失效，則后面的邊不再考慮計(jì)數(shù)，即認(rèn)為失效.總之，本文是在概率環(huán)境中，研究和根連通的邊的期望值.

定義1 設(shè)G是一個(gè)簡單連通根圖（即此根圖沒有環(huán)和重邊），那么，它的邊數(shù)期望值

這里｜A｜表示集合A的階.

由此定義，不難算出任何根圖的邊的期望值.比如，三角形根圖（如圖1所示）的期望值是Eve（G；p）＝2p＋p2，當(dāng)p＝1時(shí)，Eve（G；1）＝3，完全符合所有頂點(diǎn)幸存時(shí)根圖的邊的數(shù)目.

定理1（減－縮邊公式） 設(shè)G是一個(gè)簡單連通根圖，邊e連接根＊，它的另一端頂點(diǎn)是v.那么

簡單根圖在縮邊后，可能出現(xiàn)環(huán)，或者重邊.所以本文把沒有環(huán)、不與任何邊相連的根，表示為φ＊；僅有一個(gè)環(huán)的根，表示為I＊.并且，令Eve（I＊；p）＝1，Eve（φ＊；p）＝0.

證明本文利用條件概率（參見文獻(xiàn)［3］）的方法給出證明.

設(shè)XG表示包含根的部分所連通根的邊數(shù)，這是一個(gè)隨機(jī)變量，則E（XG）＝p·E（XG｜v沒失效）＋（1－p）·E（XG｜v失效）.當(dāng)頂點(diǎn)v沒失效時(shí)，XG＝XG／e＋1；當(dāng)頂點(diǎn)v失效時(shí)，XG＝XG－｛v｝.

由以上分析可知，（2）式成立.

推論1 有n個(gè)頂點(diǎn)（不包括根頂點(diǎn)）的路根圖（表示為Pn）的期望值是

推論2 有n個(gè)頂點(diǎn)（不包括根頂點(diǎn)）的圈根圖（表示為Cn）的期望值

推論3（直和，即無交點(diǎn)的并） Eve（G1⊕G2；p）＝Eve（G1；p）＋Eve（G2；p）.

眾所周知，在圖的色多項(xiàng)式研究中［4－9］，減－縮邊公式在簡化計(jì)算方面，是非常重要的.定理1中的減－縮邊公式，同樣是非常有用而方便的，見例1.

例1 以三角形根圖（圖1所示）為例，反復(fù)利用公式（2）.

定理2 設(shè)T是一個(gè)樹根圖，則

這里d（＊，v）表示從根＊到頂點(diǎn)v的距離.

證明對任何一個(gè)非根頂點(diǎn)不失效的話，必須是它到根的路上前面所有頂點(diǎn)全部不失效，而每個(gè)頂點(diǎn)不失效的概率都是p，且彼此是獨(dú)立的，距離是d（＊，v）.所以，這個(gè)頂點(diǎn)不失效概率是pd（＊，v），即這個(gè)頂點(diǎn)前這個(gè)邊的不失效概率是這樣的.并且，這是非不失效即失效的二點(diǎn)分布，故它的期望即是概率.再把每條邊的期望加起來，就是整個(gè)根圖的期望值.

推論4 設(shè)T是有n個(gè)頂點(diǎn)（不含根頂點(diǎn)）的根樹，那么：

（1）Eve（T；p）的p的次數(shù)不超過n；

（2）Eve（T；0）＝0，Eve（T；1）＝n.

定理3 設(shè)G是有n條邊的根圖，那么，期望值多項(xiàng)式的系數(shù)之和是n.即

證明令p＝1，則Eve（G；p）＝Eve（G；1；而p＝1，意味著所有頂點(diǎn)全部不失效，期望值就是根圖的邊數(shù).

1.2減－縮邊公式的應(yīng)用

1.2.1 路根圖的期望值

設(shè)Pn是有n個(gè)頂點(diǎn)（不含根頂點(diǎn)）的路根圖，那么由前面的推論1知道

1.2.2 圈根圖的期望值

設(shè)Cn是有n個(gè)頂點(diǎn)（不含根頂點(diǎn)）的圈根圖，那么由前面的推論2可知

1.2.3 扇根圖的期望值

設(shè)Fn，n≥2是有n個(gè)頂點(diǎn)（不含根頂點(diǎn)）的扇根圖（即根頂點(diǎn)與路圖的每個(gè)頂點(diǎn)都連接起來，如圖2（a）所示），那么

證明選取連接根＊和頂點(diǎn)vn的邊e，應(yīng)用公式（2），有

又Eve（F2；p）＝2p＋p2.所以（7）式成立.

1.2.4 輪根圖的期望值

設(shè)Wn，n≥3是有n個(gè)頂點(diǎn)（不含根頂點(diǎn)）的輪根圖（即根頂點(diǎn)與圈圖的每個(gè)頂點(diǎn)都連接起來，如圖2（b）所示），那么

證明選取連接根＊和頂點(diǎn)vn的邊e，應(yīng)用公式（2），有

1.2.5 完全圖根圖的期望值

設(shè)Kn是有n個(gè)頂點(diǎn)（不含根頂點(diǎn)）的完全圖根圖（即根頂點(diǎn)與完全圖的每個(gè)頂點(diǎn)都連接起來），那么

證明選取連接根＊和頂點(diǎn)vn的邊e，應(yīng)用公式（2），有

而Eve（K1；p）＝p.所以，（9）式成立.

2 正則q－樹根圖和正則q－樹整子根圖

定義2 如果簡單根圖G由一個(gè)完全圖根圖Kq的各個(gè)頂點(diǎn)和另外的n－q個(gè)互不相鄰的頂點(diǎn)相連接而成，則稱之為正則q－樹根圖（regular rootedq－tree）.記為

定理4 有n（n≥q＋2）個(gè)頂點(diǎn)的正則q－樹根圖的期望值迭代公式為

證明選取連接根＊和頂點(diǎn)vn的邊e，應(yīng)用公式（2），有

性質(zhì)1 設(shè)簡單根圖G是有n（n≥q）個(gè)頂點(diǎn)的正則q－樹根圖Tnq，則：

定義3 如果去掉n（n≥q＋1）個(gè)頂點(diǎn)的正則q－樹根圖中恰好含q個(gè)三角形中的一條邊而得到的簡單根圖，則稱之為正則q－樹整子根圖（integral subgraph of regular rootedq－tree）.記為Inq.

定理5 有n（n≥q＋1）個(gè)頂點(diǎn)的正則q－樹整子根圖的期望值迭代公式為

證明選取連接根＊和頂點(diǎn)vn的邊e，應(yīng)用公式（2），有

性質(zhì)2 設(shè)簡單根圖G是有n（n≥q＋1）個(gè)頂點(diǎn)的正則q－樹整子根圖Inq，則：

3 均值－方差優(yōu)化根圖

如果把頂點(diǎn)幸存概率p看做一個(gè)未知變量，而且事先知道它有某個(gè)特定的先驗(yàn)分布，那么，根據(jù)Bayesian理論，就可以得出它更精確的后驗(yàn)分布；如果對它的先驗(yàn)分布不清楚，那么，假設(shè)它的先驗(yàn)分布是（0，1）上的均勻分布，就是很合理的.

定義4 設(shè)G是一個(gè)簡單根圖，它的期望值是Eve（G；p），那么，它的后驗(yàn)均值

性質(zhì)3 設(shè)Tn是一個(gè)有n個(gè)頂點(diǎn)（不含根頂點(diǎn)）的簡單根樹，

（1）當(dāng)參數(shù)p服從（0，1）上的均勻分布，那么它的后驗(yàn)均值

方差計(jì)算公式是Var（X）＝E（X2）－E2（X），所以有下面的結(jié)論：

性質(zhì)4 設(shè)Tn是一個(gè)有n個(gè)頂點(diǎn)（不含根頂點(diǎn)）的簡單根樹，參數(shù)p服從（0，1）上的均勻分布，那么它的方差是

例2 設(shè)Tn是一個(gè)有n個(gè)頂點(diǎn)（不含根頂點(diǎn)）的簡單根樹，可以看到，當(dāng)根頂點(diǎn)在不同位置時(shí)，盡管頂點(diǎn)數(shù)相同，比如n＝4，但是它的均值和方差都不同.

（1）當(dāng)T是一個(gè)星根圖

（2）當(dāng)T是一個(gè)路根圖

則

比較上面兩個(gè)極端的例子，可以發(fā)現(xiàn)：如果追求均值大，可以取星根圖；但是，如果希望方差小，就要取路根圖.

4 討論

從例2可清楚地看到，同時(shí)要求均值大和方差小，是很難做到的.如果我們追求根圖整體的優(yōu)化，勢必要在大的均值和小的方差之中找到一個(gè)平衡點(diǎn).一個(gè)自然的想法是根據(jù)具體的要求，給它們適當(dāng)?shù)臋?quán)重.比如，給均值的權(quán)重是γ（0≤γ≤1），給方差的權(quán)重是1－γ，那么，讓u（G）＝max［γ·m（G）－（1－γ）· Var（G）］取最大值就可達(dá)到目標(biāo).或者，控制方差在一定范圍內(nèi)，追求均值最大［10－12］；反之，控制均值在一定范圍內(nèi)，追求方差最小.這個(gè)問題有待進(jìn)一步討論.

［1］ AIVALIOTIS M，GORDON G，GRAVEMAN W.When bad things happen to good trees［J］.Graph Theory，2001，37：79－99.

［2］ BAILY A，GORDON G，PATTON M，et al.Expected value expansions in rooted graphs［J］.Discrete Applied Mathematics，2003，128：555－571.

［3］ TANG X，TAN M.Estimation of simple constrained parameters with EM method［J］.J Hunan Institute of Engineering，2010，20（1）：61－64.

［4］ 唐曉清，劉念祖，王漢興，等.圖的一類新雙變量色多項(xiàng)式［J］.蘭州大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，48（2）：106－112.

［5］ 唐曉清，劉念祖，王漢興，等.正則樹的雙變量色多項(xiàng)式研究［J］.應(yīng)用數(shù)學(xué)學(xué)報(bào)，2013，36（4）：761－768.

［6］ 劉瑩，唐曉清.圖的雙變量色多項(xiàng)式比較研究［J］.湖南師范大學(xué)自然科學(xué)學(xué)報(bào)，2014，37（6）：67－72.

［7］ 唐曉清，白延琴，劉念祖，等.基于隨機(jī)矩陣?yán)碚摰腗arkowitz組合投資模型［J］.上海大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，19（3）：293－297.

［8］ TANG X.New expected value expansions of rooted graphs［J］.Acta Mathematicae Applicatae Sinica：English Series，2015，31（1）：1－8.

［9］ 劉念祖，唐曉清，王漢興.正則q－樹根圖的雙概率可靠性探究［J］.西南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，38（12）：24－27.

［10］ 王漢興，劉念祖，唐曉清，等.基于數(shù)學(xué)模型的混凝土泵在液壓系統(tǒng)的Simulink動態(tài)仿真［J］.重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，26（9）：1－7.

［11］ COLBOURN C.Network resilience［J］.SIAM J Algebraic Discrete Methods，1987，8：404－409.

［12］ 馬海成，李生剛.圖的多項(xiàng)式與Hosoya指標(biāo)［J］.東北師大學(xué)報(bào)：自然科學(xué)版，2013，45（4）：41－44.

Reliability study of regular rooted q－tree

LIU Ying1，TANG Xiao－qing2

（1.Department of Science and Information，Shaoyang University，Shaoyang 422000，China；2.School of Mathematics ＆Information，Shanghai Lixin University of Commerce，Shanghai 201620，China）

Expected value is a key index of rooted graph reliability.We propose a new vertex surviving rooted graph，that is，when Gis a rooted graph where each vertex may independently succeed with probability p when catastrophic thing happens，we consider the expected number of edges in the operational component of Gcontaining the root.And we get a very important and useful compute formula which is deletion－contraction formula.By using this formula，we get some specific graphs’expected value calculate formulas.Then，we study regular rooted q－tree and integral subgraph of regular rooted q－tree，we get the compute formulas of them.Later，we discuss the mean and variance of expected value when the parameter p has prior distribution.Finally，we discuss the optimality of rooted graph，that is，we propose mean－variance optimality idea for further discussion.

rooted graph；expected value；regular rooted q－tree；integral subgraph of regular rooted qtree；mean－variance optimality

O 157.5 ［學(xué)科代碼］ 110·7470 ［

］ A

（責(zé)任編輯：陶理）

1000－1832（2015）01－017－05

10.16163／j.cnki.22－1123／n.2015.01.004

2013－09－09

國家自然科學(xué)基金資助項(xiàng)目（60872060）.

劉瑩（1980—），女，講師，碩士研究生，主要從事圖論與概率研究。