论文部分内容阅读
图的防火问题是由Hartnell于1995年在一个国际会议上引入的.设G是一个连通的n-点图,k≥1.假设火在G的某个顶点v处燃起,一个消防员选择k个没有起火的顶点进行防卫,(等价于,有k个消防员,每个消防员防卫一个顶点),然后火蔓延到v的其它(未加防卫且没着火)的邻点.依次下去,火和消防员交替在图G上移动.当火没法再传播时,整个过程结束.设snk(v)表示当火在v处燃起时k个消防员最多能防卫的顶点数.图G的k-存活率pk(G)定义为当火随机地在G的一个顶点处燃起时,k个消防员最多能防卫的顶点数的平均率,即
pk(G)=∑v∈V(G)snk(v)/n2
存活率的概念是由L.Cai和W.Wang提出的.它与森林防火、疫情防控、计算机防毒等实际问题密切相关.W.Wang等人运用概率方法证明了:对任意的ε>0,几乎所有图的k-存活率小于ε.因此,探寻存活率大于某个常数的图类具有重要的意义.
本学位论文在前人工作的基础上,围绕平面图的k-存活率展开研究,共分4章.
在第一章,我们给出所用到的基本概念,简述了相关领域的研究现状并呈现了本文的主要研究结果.
在第二章,我们研究了平面图G的存活率,证明了:平面图G满足p4(G)>3/11.
在第三章,我们研究了围长至少为8的平面图的存活率,证明了:每个围长至少为8的平面图G有p1(G)>2/47.
在第四章,我们研究了不含4-圈的平面图的存活率,证明了:每个不含4-圈的平面图G满足p2(G)>1/76.