论文部分内容阅读
设G是含有n≥2个顶点的连通图,正整数k≥1.假设火在图G的某个顶点v处开始燃烧,消防员选择k个未燃烧的顶点进行防护,消防员和火在图G上依次交替移动.一旦某个顶点被消防员防护下来了,就称这个顶点在接下来的防火过程中一直都是受防护的.在消防员移动后,火继续向已燃烧顶点的其他邻点(未被防护的)蔓延.当火无法再继续蔓延时,就称整个防火过程结束了.设点v是着火点.在整个防火过程中,称消防员最多能防护下来的顶点数为v的存活数,记为snk(v).当火随机地在G的某个顶点处燃起时,称消防员最多能防护下来的顶点数的平均比例为图G的k-存活率,记为ρk(G),公式表示为ρk(G)=∑v∈V(G)snk(v)/n2. 假设有向图D上的某一个顶点v开始起火(规定火是沿着弧的方向传播的),消防员选择一些未被燃烧的顶点进行防护,消防员和火在图上依次交替移动.类似地,用snk(v)表示v的存活数,于是有向图D的k-存活率定义为ρk(D)=∑v∈V(D)snk(v)/n2. 本学位论文主要研究了平面图的存活率和一类定向平面图的存活率,共分为三章. 在第一章,我们介绍了图的一些基本概念,简述了存活率的部分研究现状,并呈现了本文的主要研究结果. 在第二章,我们研究了平面图G的2-存活率,证明了下面两个结果: (1)三角形距离大于等于9的平面图的2-存活率ρ2(G)>1/15228; (2)不含弦6-圈的平面图的2-存活率ρ2(G)>1/1299. 在第三章,我们研究了一类定向平面图的1-存活率,证明了: (3)设平面图G不含相邻的i-圈和j-圈,其中3≤i,j≤4,且→G是G的一个定向,则ρ1(→G)>7/207.