论文部分内容阅读
设G是一个连通图,V(G)表示G的顶点集合,令n表示图G的顶点数.本学位论文研究的防火问题是由Hartnell在1995年提出的:设G是一个连通图且v∈V(G),火开始在顶点v处燃起,一个消防员可以选择一个没有起火的顶点加以防护,消防员和火源在图G上交替移动.假设一旦一个顶点已经被消防员防护下来,那么在接下来火源的传播过程中,它一直是受保护的.当消防员移动后,起火的顶点将使那些没有被防护的邻点起火.当火源没法再传播时,整个过程就结束了.
存活数sn(v)表示当v为火源时,防火过程中消防员最多地救下的顶点个数.图G的存活率ρ(G)定义为G的顶点随机起火时防火过程可救下的顶点的平均存活率,即p(G)=∑v∈v(G)/n2.
本学位论文把防火问题推广到k-防火问题,主要围绕k-存活率,对一些平而图类展开研究.
在第二章中,得到了n-点哈林图H满足limn→∞ ρ2(日)=1.
在第三章中,对有n≥2个顶点的外可平面图G,证明了以下两个结果:
(1)limn→∞ ρ5(G)=1;
(2)当n≥8时,ρ1(G)≥43/81-5/3n+3/n2;当n≥2时,ρ1(G)≥1/3.
在第四章中,对格子图Pn×n,得到了以下两个结果:
(1)当n充分大时,ρ1(Pn×n)至少是5/8;
(2)limn→∞ ρ2(Pn×n)=1.
对三角格子图Tn×n,证明了:
(3)当n充分大时,ρ1(Tn×n)至少是41/96;
(4)limn→∞ ρs(Tn×n)=1.