K_(n,n)的局部最优可靠性

假设n点m边的简单无向图G=(V,E)的每个顶点完全可靠,各边相互独立地以同一概率q(0q1)发生故障,则用G不连通的概率P(G,q)作为衡量网不可靠程度的指标.如果对于充分接近q0的所有q都有P(G,q)P(H,q),则称在边故障概率q～q0时,网络G比H可靠.证明了当q～0时,Kn,n(n4)是2n点n2边图中局部最优可靠的.