平面图和定向平面图的存活率

作     者：裘霞霜 

作者单位：浙江师范大学 

学位级别：硕士

导师姓名：王维凡

授予年度：2017年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：防火问题 存活率 三角形 弦 定向平面图 圈 平面图 

摘      要：设G是含有n≥ 2个顶点的连通图,正整数k ≥ 1.假设火在图G的某个顶点v处开始燃烧,消防员选择k个未燃烧的顶点进行防护,消防员和火在图G上依次交替移动.一旦某个顶点被消防员防护下来了,就称这个顶点在接下来的防火过程中一直都是受防护的.在消防员移动后,火继续向已燃烧顶点的其他邻点(未被防护的)蔓延.当火无法再继续蔓延时,就称整个防火过程结束了.设点v是着火点.在整个防火过程中,称消防员最多能防护下来的顶点数为v的存活数,记为snk(v).当火随机地在G的某个顶点处燃起时,称消防员最多能防护下来的顶点数的平均比例为图G的k-存活率,记为ρk(G),公式表示为假设有向图D上的某一个顶点v开始起火(规定火是沿着弧的方向传播的),消防员选择一些未被燃烧的顶点进行防护,消防员和火在图上依次交替移动.类似地,用snk(v)表示v的存活数,于是有向图D的k-存活率定义为本学位论文主要研究了平面图的存活率和一类定向平面图的存活率,共分为三章.在第一章,我们介绍了图的一些基本概念,简述了存活率的部分研究现状,并呈现了本文的主要研究结果.在第二章,我们研究了平面图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的一个定向,则ρi(?)7/(207).