论文部分内容阅读
目的:研究最小度为2且平均度有界的连通图的边存活率。方法:利用图染色理论中的经典方法权转移进行推导证明。结果:得到了如果G是一个有n个点m条边且最小度为2的连通图,满足m≤(6/5-ε)n,其中0<ε≤1/5,那么图G的边存活率ρ′(G)>5ε/6-5ε。并由此推得如果G是一个最小度为2且围长至少为13的连通平面图,那么图G的边存活率ρ′(G)>1/65。结论:若图G是一个最小度为2且平均度小于2.4的连通图,当火随机地在图G的任意两个相邻的顶点燃起时,1个消防员最多能保护的顶点数的平均