正则q－树根图的可靠性研究

刘 莹，唐晓清

（1.邵阳学院理学与信息科学系，湖南邵阳422000；2.上海立信会计学院数学与信息学院，上海201620）

正则q－树根图的可靠性研究

刘 莹1，唐晓清2

（1.邵阳学院理学与信息科学系，湖南邵阳422000；2.上海立信会计学院数学与信息学院，上海201620）

对根图的顶点的幸存概率进行了期望值研究，得出一个重要的定理，即减－缩边公式.由此，得到一些特殊根图的期望值计算公式及正则q－树根图和正则q－树整子根图的期望值计算公式.讨论了根图的均值和方差的后验计算公式，以及整体优化的思路.

根图；期望值；正则q－树根图；正则q－树整子根图；均值－方差优化

生活中，很多网络可以看做一个根图.比如，供电网络、供水网络、计算机网络、有线电视网络，等等.它们都有一个共同的特点，那就是终端用户可以看做是图的顶点，而连接它们的管道或线路，可以看做是图的线，像电厂、发射台等功能中心，就是这个图的根.并且，一旦某顶点和根不连通，此顶点就失效了.根图的可靠性，或者说恢复力，是一个很重要的研究目标.人们首先假设有关终端用户设备是以一定的概率在灾难后幸存，这些设备在灾难后幸存的期望值，就是根图可靠性的一个重要指标.因此该研究的重要性不言而喻.目前对于根图的边的幸存概率p，M.Aivaliotis和A.Bailey进行了期望值研究，得到一些成果.［1－2］但对根图的顶点幸存概率期望值的研究还未见报道.本文对根图的顶点幸存概率期望值进行了研究，得出一些结论.

1 定义及减－缩边公式

1.1定义及定理

设图G是一个连通根图，根顶点表示为＊，并且，集合E是边集，集合V是顶点集，子集A⊆V，r（A）表示包含根的子图A中和根连通的边的数目.设图的每一个顶点（根顶点除外）在灾难事件发生后的幸存概率是p，并且任何两个顶点是否幸存是独立的.在这里，设边总是不失效的.但是，在一个连接根的通路中，如果前面的顶点失效，则后面的边不再考虑计数，即认为失效.总之，本文是在概率环境中，研究和根连通的边的期望值.

定义1 设G是一个简单连通根图（即此根图没有环和重边），那么，它的边数期望值

这里｜A｜表示集合A的阶.

由此定义，不难算出任何根图的边的期望值.比如，三角形根图（如图1所示）的期望值是Eve（G；p）＝2p＋p2，当p＝1时，Eve（G；1）＝3，完全符合所有顶点幸存时根图的边的数目.

定理1（减－缩边公式） 设G是一个简单连通根图，边e连接根＊，它的另一端顶点是v.那么

简单根图在缩边后，可能出现环，或者重边.所以本文把没有环、不与任何边相连的根，表示为φ＊；仅有一个环的根，表示为I＊.并且，令Eve（I＊；p）＝1，Eve（φ＊；p）＝0.

证明本文利用条件概率（参见文献［3］）的方法给出证明.

设XG表示包含根的部分所连通根的边数，这是一个随机变量，则E（XG）＝p·E（XG｜v没失效）＋（1－p）·E（XG｜v失效）.当顶点v没失效时，XG＝XG／e＋1；当顶点v失效时，XG＝XG－｛v｝.

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

推论1 有n个顶点（不包括根顶点）的路根图（表示为Pn）的期望值是

推论2 有n个顶点（不包括根顶点）的圈根图（表示为Cn）的期望值

推论3（直和，即无交点的并） Eve（G1⊕G2；p）＝Eve（G1；p）＋Eve（G2；p）.

众所周知，在图的色多项式研究中［4－9］，减－缩边公式在简化计算方面，是非常重要的.定理1中的减－缩边公式，同样是非常有用而方便的，见例1.

例1 以三角形根图（图1所示）为例，反复利用公式（2）.

定理2 设T是一个树根图，则

这里d（＊，v）表示从根＊到顶点v的距离.

证明对任何一个非根顶点不失效的话，必须是它到根的路上前面所有顶点全部不失效，而每个顶点不失效的概率都是p，且彼此是独立的，距离是d（＊，v）.所以，这个顶点不失效概率是pd（＊，v），即这个顶点前这个边的不失效概率是这样的.并且，这是非不失效即失效的二点分布，故它的期望即是概率.再把每条边的期望加起来，就是整个根图的期望值.

推论4 设T是有n个顶点（不含根顶点）的根树，那么：

（1）Eve（T；p）的p的次数不超过n；

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

定理3 设G是有n条边的根图，那么，期望值多项式的系数之和是n.即

证明令p＝1，则Eve（G；p）＝Eve（G；1；而p＝1，意味着所有顶点全部不失效，期望值就是根图的边数.

1.2减－缩边公式的应用

1.2.1 路根图的期望值

设Pn是有n个顶点（不含根顶点）的路根图，那么由前面的推论1知道

1.2.2 圈根图的期望值

设Cn是有n个顶点（不含根顶点）的圈根图，那么由前面的推论2可知

1.2.3 扇根图的期望值

设Fn，n≥2是有n个顶点（不含根顶点）的扇根图（即根顶点与路图的每个顶点都连接起来，如图2（a）所示），那么

证明选取连接根＊和顶点vn的边e，应用公式（2），有

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

1.2.4 轮根图的期望值

设Wn，n≥3是有n个顶点（不含根顶点）的轮根图（即根顶点与圈图的每个顶点都连接起来，如图2（b）所示），那么

证明选取连接根＊和顶点vn的边e，应用公式（2），有

1.2.5 完全图根图的期望值

设Kn是有n个顶点（不含根顶点）的完全图根图（即根顶点与完全图的每个顶点都连接起来），那么

证明选取连接根＊和顶点vn的边e，应用公式（2），有

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

2 正则q－树根图和正则q－树整子根图

定义2 如果简单根图G由一个完全图根图Kq的各个顶点和另外的n－q个互不相邻的顶点相连接而成，则称之为正则q－树根图（regular rootedq－tree）.记为

定理4 有n（n≥q＋2）个顶点的正则q－树根图的期望值迭代公式为

证明选取连接根＊和顶点vn的边e，应用公式（2），有

性质1 设简单根图G是有n（n≥q）个顶点的正则q－树根图Tnq，则：

定义3 如果去掉n（n≥q＋1）个顶点的正则q－树根图中恰好含q个三角形中的一条边而得到的简单根图，则称之为正则q－树整子根图（integral subgraph of regular rootedq－tree）.记为Inq.

定理5 有n（n≥q＋1）个顶点的正则q－树整子根图的期望值迭代公式为

证明选取连接根＊和顶点vn的边e，应用公式（2），有

性质2 设简单根图G是有n（n≥q＋1）个顶点的正则q－树整子根图Inq，则：

3 均值－方差优化根图

如果把顶点幸存概率p看做一个未知变量，而且事先知道它有某个特定的先验分布，那么，根据Bayesian理论，就可以得出它更精确的后验分布；如果对它的先验分布不清楚，那么，假设它的先验分布是（0，1）上的均匀分布，就是很合理的.

定义4 设G是一个简单根图，它的期望值是Eve（G；p），那么，它的后验均值

性质3 设Tn是一个有n个顶点（不含根顶点）的简单根树，

（1）当参数p服从（0，1）上的均匀分布，那么它的后验均值

方差计算公式是Var（X）＝E（X2）－E2（X），所以有下面的结论：

性质4 设Tn是一个有n个顶点（不含根顶点）的简单根树，参数p服从（0，1）上的均匀分布，那么它的方差是

例2 设Tn是一个有n个顶点（不含根顶点）的简单根树，可以看到，当根顶点在不同位置时，尽管顶点数相同，比如n＝4，但是它的均值和方差都不同.

（1）当T是一个星根图

（2）当T是一个路根图

则

比较上面两个极端的例子，可以发现：如果追求均值大，可以取星根图；但是，如果希望方差小，就要取路根图.

4 讨论

从例2可清楚地看到，同时要求均值大和方差小，是很难做到的.如果我们追求根图整体的优化，势必要在大的均值和小的方差之中找到一个平衡点.一个自然的想法是根据具体的要求，给它们适当的权重.比如，给均值的权重是γ（0≤γ≤1），给方差的权重是1－γ，那么，让u（G）＝max［γ·m（G）－（1－γ）· Var（G）］取最大值就可达到目标.或者，控制方差在一定范围内，追求均值最大［10－12］；反之，控制均值在一定范围内，追求方差最小.这个问题有待进一步讨论.

［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］ 唐晓清，刘念祖，王汉兴，等.图的一类新双变量色多项式［J］.兰州大学学报：自然科学版，2012，48（2）：106－112.

［5］ 唐晓清，刘念祖，王汉兴，等.正则树的双变量色多项式研究［J］.应用数学学报，2013，36（4）：761－768.

［6］ 刘莹，唐晓清.图的双变量色多项式比较研究［J］.湖南师范大学自然科学学报，2014，37（6）：67－72.

［7］ 唐晓清，白延琴，刘念祖，等.基于随机矩阵理论的Markowitz组合投资模型［J］.上海大学学报：自然科学版，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］.西南师范大学学报：自然科学版，2013，38（12）：24－27.

［10］ 王汉兴，刘念祖，唐晓清，等.基于数学模型的混凝土泵在液压系统的Simulink动态仿真［J］.重庆理工大学学报：自然科学版，2012，26（9）：1－7.

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

［12］ 马海成，李生刚.图的多项式与Hosoya指标［J］.东北师大学报：自然科学版，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 ［学科代码］ 110·7470 ［

］ A

（责任编辑：陶理）

1000－1832（2015）01－017－05

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

2013－09－09

国家自然科学基金资助项目（60872060）.

刘莹（1980—），女，讲师，硕士研究生，主要从事图论与概率研究。