根图的稳定性及其优化

设灾难发生时,根图G的边以概率p独立幸存,则含根连通子图的顶点数的期望值EV(G;p)是根图的可靠性的合适指标.定义了子图的顶点数的平方期望值E2(G;p)后,则方差D(G;p)=E2(G;p)-EV(G;p)]~2是根图稳定性的合适指标.推导得到了E2(G;p)的减-缩边公式,从而得到方差的一个递归计算方法.进而研究了一些特殊图的方差的计算公式.最后,结合期望和方差,讨论了根图的优化问题.

On Stability of Rooted Graph and Its Optimality

When G is a rooted graph where each edge may independently succeed with probability p when catastrophic thing happens, we consider the expected number of vertices in the operational component of G containing the root.Then the expected value of edges number EV(G;p) is a proper index of reliability to rooted graph.Later, we give the definition E2(G;p), which is the expect of vertices number square, then variance D(G;p)=E2(G;p)-EV(G;p)]2.Especially, we get the deletion-contraction edge formula of E2(G;p).So we obtain a recursive computing variance method.And D(G;p) is a proper stability index to the rooted graph.With this formula, we get some variance computational formulas of specific rooted graphs.Finally, we propose expect-variance optimality of rooted graph.