论文部分内容阅读
设G是含有n≥2个顶点和m≥1条边的连通图,正整数k≥1.假设火在图G的某一个顶点v处开始燃烧,消防员选择一些顶点开始保护.在每一步中,消防员选择k个未燃烧的顶点进行保护,然后,火向已燃烧顶点的邻点(未被保护的)蔓延.设snk(v)表示当v为火源时,整个防火过程中消防员最多可救下的顶点数.可救下的顶点的平均比率称为G的k-存活率,记为ρk(G),即ρk(G)=∑v∈v(G)snk(v)/n2. 假设火在图G的某一条边uv的两个端点(相邻的两个顶点)处开始燃烧,消防员选择G中的一些顶点开始保护.在第一步中,消防员选择k个未燃烧的顶点进行保护,在接下去的每一步中,消防员选择l个未燃烧的顶点进行保护.在每一步的最后,火向已燃烧顶点的邻点(未被保护的)蔓延.依次下去,火和消防员交替地在图G上移动.当火无法再蔓延时,整个防火过程结束.设sn(k,l)(uv)表示当uv为火源时,整个防火过程中消防员最多可以救下的顶点数.图G的(k,l)-边存活率,ρ(k,l)(G)定义为ρ(k,l)(G)=∑uv∈E(G) sn(k,l)(uv)/nm. 本论文主要研究了平面图的存活率和边存活率,共分为三章. 第一章介绍图的一些基本概念,简述存活率的部分研究结果,并给出了本文的主要结果. 第二章研究平面图的2-存活率,证明了下面一些结果: (1)无5-圈平面图的2-存活率ρ2(G)>1/363; (2)无7-圈平面图的2-存活率ρ2(G)>1/783; (3)无6-圈平面图的2-存活率ρ2(G)>1/41. 第三章研究平面图的边存活率,设G是最小度δ(G)≥3的平面图,证明了下面一些结果: (1)ρ(5,2)(G)>11/3753; (2)若G不含3-圈,则ρ(4,2)(G)≥1/24; (3)若G不含3,4-圈,则ρ(3,2)(G)≥1/6.